В вычислительной геометрии задача « точка в многоугольнике » ( PIP ) задаёт вопрос о том, лежит ли заданная точка на плоскости внутри, снаружи или на границе многоугольника . Это особый случай задач определения местоположения точек , который находит применение в областях, связанных с обработкой геометрических данных, таких как компьютерная графика , компьютерное зрение , географические информационные системы (ГИС), планирование движения и автоматизированное проектирование (САПР).
Раннее описание проблемы в компьютерной графике показывает два распространенных подхода ( распределение лучей и суммирование углов), которые использовались еще в 1974 году. [1]
Попытку ветеранов компьютерной графики проследить историю проблемы и некоторые приемы ее решения можно найти в выпуске Ray Tracing News . [2]
Один из простых способов узнать, находится ли точка внутри или снаружи простого многоугольника, — это проверить, сколько раз луч , исходящий из точки и идущий в любом фиксированном направлении, пересекает края многоугольника. Если точка находится снаружи многоугольника, луч пересечет его край четное число раз. Если точка находится внутри многоугольника, луч пересечет край нечетное число раз. Статус точки на краю многоугольника зависит от деталей алгоритма пересечения лучей.
Этот алгоритм иногда также называют алгоритмом числа пересечений или алгоритмом правила четности–нечетности , и он был известен еще в 1962 году. [3] Алгоритм основан на простом наблюдении, что если точка движется по лучу от бесконечности до точки зонда и если она пересекает границу многоугольника, возможно, несколько раз, то она попеременно идет снаружи внутрь, затем изнутри наружу и т. д. В результате после каждых двух «пересечений границы» движущаяся точка выходит наружу. Это наблюдение можно математически доказать с помощью теоремы о кривой Жордана .
Если реализовать на компьютере с арифметикой конечной точности , результаты могут быть неверными, если точка лежит очень близко к этой границе, из-за ошибок округления. Для некоторых приложений, таких как видеоигры или другие развлекательные продукты, это не является большой проблемой, поскольку они часто отдают предпочтение скорости, а не точности. Однако для формально правильной компьютерной программы нужно было бы ввести числовой допуск ε и проверить в строке, находится ли P (точка) в пределах ε от L (линии), в этом случае алгоритм должен остановиться и сообщить « P лежит очень близко к границе».
Большинство реализаций алгоритма ray casting последовательно проверяют пересечения луча со всеми сторонами многоугольника по очереди. В этом случае необходимо решить следующую проблему. Если луч проходит точно через вершину многоугольника, то он пересечет 2 сегмента в их конечных точках. Хотя это нормально для случая самой верхней вершины в примере или вершины между пересечением 4 и 5, случай самой правой вершины (в примере) требует, чтобы мы посчитали одно пересечение для правильной работы алгоритма. Похожая проблема возникает с горизонтальными сегментами, которые случайно попадают на луч. Проблема решается следующим образом: если точка пересечения является вершиной проверяемой стороны многоугольника, то пересечение учитывается только в том случае, если другая вершина стороны лежит под лучом. Это фактически эквивалентно рассмотрению вершин на луче как лежащих немного выше луча.
Опять же, случай луча, проходящего через вершину, может вызывать численные проблемы в арифметике конечной точности : для двух сторон, смежных с одной и той же вершиной, прямое вычисление пересечения с лучом может не дать вершину в обоих случаях. Если многоугольник задан его вершинами, то эта проблема устраняется проверкой y-координат луча и концов проверяемой стороны многоугольника перед фактическим вычислением пересечения. В других случаях, когда стороны многоугольника вычисляются из других типов данных, должны применяться другие приемы для численной надежности алгоритма.
Другой метод, используемый для проверки того, находится ли точка внутри многоугольника, заключается в вычислении числа оборотов данной точки относительно многоугольника. Если число оборотов не равно нулю, точка лежит внутри многоугольника. Этот алгоритм иногда также называют алгоритмом ненулевого правила .
Чтобы проверить, находится ли заданная точка внутри или снаружи многоугольника:
Один из способов вычисления числа оборотов — суммирование углов, образуемых каждой стороной многоугольника. [5] Однако это требует затратных обратных тригонометрических функций , что обычно делает этот алгоритм неэффективным с точки зрения производительности (более медленным) по сравнению с алгоритмом ray casting. К счастью, эти обратные тригонометрические функции не нужно вычислять. Поскольку результат, сумма всех углов, может составлять только 0 или (или кратные ), достаточно отслеживать, через какие квадранты проходит многоугольник, [6] когда он поворачивается вокруг контрольной точки, что делает алгоритм числа оборотов сопоставимым по скорости с подсчетом пересечений границ.
Улучшенный алгоритм для вычисления числа оборотов был разработан Дэном Сандеем в 2001 году. [7] Он не использует углы в вычислениях, ни какую-либо тригонометрию и функционирует точно так же, как описанные выше алгоритмы луча, отбрасываемого. Алгоритм Сандея работает, рассматривая бесконечный горизонтальный луч, отбрасываемый из проверяемой точки. Всякий раз, когда этот луч пересекает ребро многоугольника, алгоритм пересечения ребер Хуана Пинеды (1988) [8] используется для определения того, как пересечение повлияет на число оборотов. Как описывает Сандей, если ребро пересекает луч, идущий «вверх», число оборотов увеличивается; если оно пересекает луч «вниз», число уменьшается. Алгоритм Сандея дает правильный ответ для непростых многоугольников, тогда как алгоритм пересечения границ в этом случае не работает. [7]
Похожие методы используются в SVG для определения способа заполнения цветом различных фигур (таких как путь, полилиния, многоугольник, текст и т. д.). [9] На алгоритм заполнения влияет атрибут fill-rule. Значение может быть либо , nonzeroлибо evenodd. Например, в пентаграмме есть центральное «отверстие» (видимый фон) с evenodd, и нет с nonzeroатрибутом. [10]
Для простых многоугольников алгоритмы дадут тот же результат. Однако для сложных многоугольников алгоритмы могут давать разные результаты для точек в областях, где многоугольник пересекает себя, где многоугольник не имеет четко определенных внутренней и внешней части. Одним из решений, использующих правило четно-нечетного, является преобразование (сложных) многоугольников в более простые, которые являются четно-нечетно-эквивалентными перед проверкой пересечения. [11] Это, однако, требует больших вычислительных затрат. Менее затратно использовать быстрый алгоритм ненулевого числа витков, который дает правильный результат, даже когда многоугольник перекрывает себя.
Проблема точки в многоугольнике может рассматриваться в общем повторяющемся геометрическом запросе : имея один многоугольник и последовательность точек запроса, быстро найти ответы для каждой точки запроса. Очевидно, что можно использовать любой из общих подходов для определения местоположения точки на плоскости . Для некоторых специальных многоугольников доступны более простые решения.
Более простые алгоритмы возможны для монотонных многоугольников , звездчатых многоугольников , выпуклых многоугольников и треугольников .
Случай треугольника можно легко решить с помощью барицентрической системы координат , параметрического уравнения или скалярного произведения . [12] Метод скалярного произведения естественным образом распространяется на любой выпуклый многоугольник.
