рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Проверка принадлежности точки многоугольнику

Реферат Курсовая Конспект

Выберите учебное заведение

Проверка принадлежности точки многоугольнику

Проверка принадлежности точки многоугольнику - раздел Математика, АНАЛИТИЧЕСКАЯ ГЕОМЕТРИЯ Для Решен...

Для решения этой задачи выпустим из точки А(х,у) произвольный луч и найдем количество точек пересечения этого луча с границей многоугольника. Если отбросить случай, когда луч проходит через вершину многоугольника, то решение задачи тривиально - точка лежит внутри, если общее количество точек пересечения нечетнечетно, и снаружи, если четно.

Ясно, что для любого многоугольника всегда можно построить луч, не проходящий ни через одну из вершин. Однако построение такого луча связано с некоторыми трудностями и, кроме того, проверку пересечения границы многоугольника с произвольным лучом провести сложнее, чем с фиксированным, например горизонтальным.

Возьмем луч, выходящий из произвольной точки А, и рассмотрим, к чему может привести прохождение луча через вершину многоугольника. Основные возможные случаи изображены на рисунке.

В случае а, когда ребра, выходящие из соответствующей вершины, лежат по одну сторону от луча, четность количества пересечений не меняется.

Случай в, когда выходящие из вершины ребра лежат по разные стороны от луча, четность количества пересечений изменяется. К случаям б и г такой подход непосредственно неприменим. Несколько изменим его, заметив, что в случаях а и б вершины, лежащие на луче, являются экстремальными значениями в тройке вершин соответствующих отрезков. В других же случаях экстремума нет.

Исходя из этого, можно построить следующий алгоритм: выпускаем из точки А горизонтальный луч в направлении оси Ох и все ребра многоугольника, кроме горизонтальных, проверяем на пересечение с этим лучом. В случае, когда луч проходит через вершину, т.е. формально пересекает сразу два ребра, сходящихся в этой вершине, засчитаем это пересечение только для тех ребер, для которых эта вершина является верхней.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

АНАЛИТИЧЕСКАЯ ГЕОМЕТРИЯ

Федеральное государственное образовательное учреждение... Высшего профессионального образования... Сибирский федеральный университет...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Проверка принадлежности точки многоугольнику

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Аксиоматика Гильберта и векторная алгебра
Основные определения Вектор – упорядоченная пара точек А, В. Обозначаем вектор . При этом первую точк

Базис, координаты векторов
Основные определения Выражение вида будем называть линейной комбинацией векторов

Системы координат на плоскости и в пространстве
Основные определения Будем говорить, что задана декартова система координат (на плоскости или в пространстве), если з

Проекции. Скалярное произведение векторов
Основные определения Число, равное будем называть скалярным произведением ве

Векторное и смешанное произведение векторов
Основные определения Упорядоченная тройка некомпланарных векторов называется правой, если из конца третьего вектора кратчайший поворо

Замена декартовой системы координат
Основные утверждения Пусть в пространстве задана декартова система координат с началом в точке О и базисом

Общее понятие об уравнениях линий и поверхностей
Основные определения Уравнение

Уравнения прямых на плоскости
Основные типы уравнений прямой линии Векторно-параметрическое уравнение прямой линии:

Плоскость в пространстве
Основные типы уравнений плоскости Векторно-параметрическое уравнение плоскости:

Прямые в пространстве
Основные типы уравнений прямой линии Векторно-параметрическое уравнение прямой линии:

Основные типы нераспадающихся кривых второго порядка на плоскости
Основные определения Уравнение второго порядка в декартовой системе координат (x,y)

Канонические уравнения поверхностей второго порядка
Основные определения Эллипсоидом называется поверхность, которая в некоторой декартовой прямоугольной системе координат имеет уравнение

Преобразования плоскости
Основные определения Отображение множества X в множество У – это правил

Нахождение пересечения двух отрезков
Пусть А, В, С и D - точки на плоскости. Тогда направленные отрезки АВ и CD задаются следующими параметрическими уравнениями:

Построение выпуклой оболочки
Пусть S - конечный набор точек на плоскости. Выпуклой оболочкой набора S называется пересечение всех выпуклых многоугольников, содержащих S

Построение триангуляции Делоне
Рассмотрим задачу триангуляции набора точек S на плоскости. Все точки набора S можно разбить на граничные - точки, лежащие на границе выпуклой оболочки