Из Википедии, бесплатной энциклопедии
  (Перенаправлено из алгоритма Ray casting )
Перейти к навигации Перейти к поиску
Пример простого многоугольника

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

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

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

Алгоритм Ray casting [ править ]

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

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

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

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

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

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

Алгоритм числа обмоток [ править ]

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

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

Имеется значительное ускорение (известное с 2001 года) алгоритма числа оборотов. Он использует переходы со знаком, в зависимости от того, выполняется ли каждое пересечение слева направо или справа налево. Подробности и код C ++ приведены по ссылке в следующей аннотации. [6] Углы не используются, и тригонометрия не используется. Код работает так же быстро, как и простой алгоритм пересечения границы. Кроме того, он дает правильный ответ для непростых многоугольников, тогда как алгоритм пересечения границы в этом случае не работает.

Сравнение [ править ]

Оба метода используются в SVG , где значение атрибута fill-rule либо « ненулевое », либо « четное нечетное ». Например, в невыпуклой правильной пятиугольной поверхности есть центральное отверстие с "четным нечетным" , без отверстия с "ненулевым" (веб-адрес: https://www.w3.org ).

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

Точка в запросах многоугольника [ править ]

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

Особые случаи [ править ]

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

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

Ссылки [ править ]

  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 г.
  4. ^ Hormann, K .; Агафос, А. (2001). «Проблема точки в многоугольнике для произвольных многоугольников». Вычислительная геометрия . 20 (3): 131. DOI : 10.1016 / S0925-7721 (01) 00012-8 .
  5. ^ Вейлер, Кевин (1994), «Точка возрастающего угла в тесте многоугольника», в Heckbert, Paul S. (ed.), Graphics Gems IV , Сан-Диего, Калифорния, США: Academic Press Professional, Inc., стр.  16 –23 , ISBN 0-12-336155-9.
  6. ^ Воскресенье, Дэн (2001), Включение точки в многоугольник.
  7. ^ Майкл Галецка, Патрик Глаунер (2017). Простой и правильный четно-нечетный алгоритм для задачи точки в многоугольнике для сложных многоугольников . Труды 12-й Международной совместной конференции по теории и приложениям компьютерного зрения, визуализации и компьютерной графики ( VISIGRAPP 2017), Том 1: GRAPP.
  8. ^ Точная точка в тесте на треугольник " ... самые известные методы ее решения "

См. Также [ править ]

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