Точка в многоугольнике

В вычислительной геометрии задача « точка в многоугольнике » ( PIP ) спрашивает, находится ли данная точка плоскости внутри, снаружи или на границе многоугольника . Это особый случай проблем с расположением точек , который находит применение в областях, связанных с обработкой геометрических данных, таких как компьютерная графика , компьютерное зрение , географические информационные системы (ГИС), планирование движения и автоматизированное проектирование (САПР).

Раннее описание проблемы компьютерной графики показывает, что два распространенных подхода ( распределение лучей и суммирование углов) использовались еще в 1974 году. ^[1]

Попытку ветеранов компьютерной графики проследить историю проблемы и некоторые хитрости ее решения можно найти в выпуске Ray Tracing News . ^[2]

Алгоритм приведения лучей

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

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

Этот алгоритм иногда также называют алгоритмом числа пересечений или правила четно-нечетных чисел алгоритмом , и он был известен еще в 1962 году. ^[3] Алгоритм основан на простом наблюдении, что если точка движется по лучу от бесконечности к контрольной точке и если она пересекает границу многоугольника, возможно, несколько раз, то она попеременно идет то снаружи внутрь, то изнутри. наружу и т. д. В результате после каждых двух «переходов границы» движущаяся точка выходит наружу. Это наблюдение может быть математически доказано с помощью теоремы Жордана о кривой .

Ограниченная точность

При реализации на компьютере с арифметикой конечной точности результаты могут быть неверными, если точка находится очень близко к этой границе из-за ошибок округления. Для некоторых приложений, таких как видеоигры или другие развлекательные продукты, это не является большой проблемой, поскольку они часто предпочитают скорость точности. Однако для формально корректной компьютерной программы пришлось бы ввести числовой допуск ε и проверить по линии, находится ли P (точка) в пределах ε от L (линии), и в этом случае алгоритм должен остановиться и сообщить: « P лежит в пределах ε от L (линии). очень близко к границе».

Большинство реализаций алгоритма приведения лучей последовательно проверяют пересечения луча со всеми сторонами многоугольника по очереди. В этом случае необходимо решить следующую проблему. Если луч проходит точно через вершину многоугольника, то он пересечет 2 отрезка в их конечных точках. Хотя это нормально для случая самой верхней вершины в примере или вершины между пересечениями 4 и 5, случай самой правой вершины (в примере) требует, чтобы мы посчитали одно пересечение, чтобы алгоритм работал правильно. Аналогичная проблема возникает с горизонтальными отрезками, случайно попавшими на луч. Задача решается следующим образом: Если точка пересечения является вершиной проверяемой стороны многоугольника, то пересечение засчитывается только в том случае, если другая вершина стороны лежит ниже луча. Фактически это эквивалентно тому, что вершины луча рассматриваются как лежащие немного выше луча.

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

Алгоритм числа витков

Другой метод, используемый для проверки того, находится ли точка внутри многоугольника, заключается в вычислении числа витков данной точки относительно многоугольника. Если номер витка не равен нулю, точка лежит внутри многоугольника. Этот алгоритм иногда также называют ненулевого правила алгоритмом .

Один из способов вычисления числа витков — просуммировать углы, образующие каждую сторону многоугольника. ^[4] Однако при этом используются дорогостоящие обратные тригонометрические функции , что обычно делает этот алгоритм неэффективным (более медленным) по сравнению с алгоритмом преобразования лучей. К счастью, эти обратные тригонометрические функции не нужно вычислять. Поскольку результат, сумма всех углов, может в сумме составлять 0 или $2\pi$ (или кратное $2\pi$ ) только достаточно проследить, через какие квадранты вьется многоугольник, ^[5] при повороте вокруг контрольной точки, что делает алгоритм числа обмоток сравнимым по скорости с подсчетом пересечений границы.

Улучшенный алгоритм расчета числа витков был разработан Дэном Сандей в 2001 году. ^[6] Он не использует ни углы в расчетах, ни какую-либо тригонометрию и функционирует точно так же, как алгоритмы распределения лучей, описанные выше. Алгоритм Санди работает, рассматривая бесконечный горизонтальный луч, исходящий из проверяемой точки. Всякий раз, когда этот луч пересекает край многоугольника, алгоритм пересечения ребер Хуана Пинеды (1988) ^[7] используется для определения того, как пересечение повлияет на номер обмотки. Как описывает это Санди, если ребро пересекает луч, идущий «вверх», номер витка увеличивается; если он пересекает луч «вниз», число уменьшается. Алгоритм воскресенья дает правильный ответ для непростых многоугольников, тогда как алгоритм пересечения границ в этом случае дает сбой. ^[6]

Реализации

SVG

Подобные методы используются в SVG для определения способа заливки цветом различных фигур (таких как путь, ломаная линия, многоугольник, текст и т. д.). ^[8] На алгоритм заполнения влияет атрибут fill-rule. Значение может быть либо nonzero или evenodd. Например, в пентаграмме есть центральное «отверстие» (видимый фон) с evenodd, и ни один с nonzero атрибут. ^[9]

Для простых многоугольников алгоритмы дадут тот же результат. Однако для сложных многоугольников алгоритмы могут давать разные результаты для точек в областях пересечения многоугольника сам с собой, где многоугольник не имеет четко выраженной внутренней и внешней части. Одним из решений, использующих правило чет-нечет, является преобразование (сложных) многоугольников в более простые, эквивалентные чет-нечету, перед проверкой пересечения. ^[10] Однако это требует больших вычислительных затрат. Дешевле использовать быстрый алгоритм ненулевого числа витков, который дает правильный результат, даже когда многоугольник перекрывается сам собой.

Точка в полигональных запросах

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

Особые случаи

Более простые алгоритмы возможны для монотонных многоугольников , звездообразных многоугольников , выпуклых многоугольников и треугольников .

Случай треугольника можно легко решить, используя барицентрическую систему координат , параметрическое уравнение или скалярное произведение . ^[11] Метод скалярного произведения естественным образом распространяется на любой выпуклый многоугольник.

Ссылки

^ Иван Сазерленд и др., «Характеристика десяти алгоритмов скрытой поверхности» 1974, ACM Computing Surveys vol. 6 нет. 1.
^ «Точка в полигоне, еще раз ...». Архивировано 24 мая 2018 г. в Wayback Machine , Ray Tracing News , vol. 3 нет. 4, 1 октября 1990 г.
^ Шимрат, М., «Алгоритм 112: Положение точки относительно многоугольника», 1962 г., Сообщения ACM, том 5, выпуск 8, август 1962 г. https://dl.acm.org/doi/10.1145/368637.368653
^ Хорманн, К.; Агатос, А. (2001). «Точка в задаче о многоугольниках для произвольных многоугольников» . Вычислительная геометрия . 20 (3): 131. doi : 10.1016/S0925-7721(01)00012-8 .
^ Вейлер, Кевин (1994), «Точка с приращением угла в многоугольном тесте», в Хекберте, Поле С. (редактор), Graphics Gems IV , Сан-Диего, Калифорния, США: Academic Press Professional, Inc., стр. 16– 23, ISBN 0-12-336155-9
^ Перейти обратно: ^а ^б Воскресенье, Дэн (2001). «Включение точки в многоугольник» . Архивировано из оригинала 26 января 2013 года.
^ Пинеда, Хуан (август 1988 г.). Параллельный алгоритм растеризации полигонов (PDF) . СИГРАФ '88. Компьютерная графика . Том. 22, нет. 4. Атланта . Проверено 8 августа 2021 г.
^ «Рисование: заливка, обводка, цвета и серверы рисования – SVG Tiny 1.2» . www.w3.org . Проверено 24 июля 2021 г.
^ «Рисование: заливка, обводка, цвета и серверы рисования – SVG Tiny 1.2» . www.w3.org . Проверено 24 июля 2021 г.
^ Майкл Галецка, Патрик Глаунер (2017). Простой и правильный четно-нечетный алгоритм решения задачи «точка в многоугольнике» для сложных многоугольников . Материалы 12-й Международной совместной конференции по теории и приложениям компьютерного зрения, изображений и компьютерной графики ( VISIGRAPP 2017), Том 1: GRAPP.
^ Точная точка в тесте треугольника « ...самые известные методы его решения »

См. также

Пакет топологии Java (JTS)
Обсуждение: http://www.ics.uci.edu/~eppstein/161/960307.html.
Методы числа витков и числа пересечений: http://geomalgorithms.com/a03-_inclusion.html

[1] Иван Сазерленд и др., «Характеристика десяти алгоритмов скрытой поверхности» 1974, ACM Computing Surveys vol. 6 нет. 1.

[2] «Точка в полигоне, еще раз ...». Архивировано 24 мая 2018 г. в Wayback Machine , Ray Tracing News , vol. 3 нет. 4, 1 октября 1990 г.

[3] Шимрат, М., «Алгоритм 112: Положение точки относительно многоугольника», 1962 г., Сообщения ACM, том 5, выпуск 8, август 1962 г. https://dl.acm.org/doi/10.1145/368637.368653

[Hormann-4] Хорманн, К.; Агатос, А. (2001). «Точка в задаче о многоугольниках для произвольных многоугольников» . Вычислительная геометрия . 20 (3): 131. doi : 10.1016/S0925-7721(01)00012-8 .

[5] Вейлер, Кевин (1994), «Точка с приращением угла в многоугольном тесте», в Хекберте, Поле С. (редактор), Graphics Gems IV , Сан-Диего, Калифорния, США: Academic Press Professional, Inc., стр. 16– 23, ISBN 0-12-336155-9

[sunday-6] Перейти обратно: ^а ^б Воскресенье, Дэн (2001). «Включение точки в многоугольник» . Архивировано из оригинала 26 января 2013 года.

[7] Пинеда, Хуан (август 1988 г.). Параллельный алгоритм растеризации полигонов (PDF) . СИГРАФ '88. Компьютерная графика . Том. 22, нет. 4. Атланта . Проверено 8 августа 2021 г.

[8] «Рисование: заливка, обводка, цвета и серверы рисования – SVG Tiny 1.2» . www.w3.org . Проверено 24 июля 2021 г.

[9] «Рисование: заливка, обводка, цвета и серверы рисования – SVG Tiny 1.2» . www.w3.org . Проверено 24 июля 2021 г.

[10] Майкл Галецка, Патрик Глаунер (2017). Простой и правильный четно-нечетный алгоритм решения задачи «точка в многоугольнике» для сложных многоугольников . Материалы 12-й Международной совместной конференции по теории и приложениям компьютерного зрения, изображений и компьютерной графики ( VISIGRAPP 2017), Том 1: GRAPP.

[11] Точная точка в тесте треугольника « ...самые известные методы его решения »

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]