Точка в многоугольнике
-
Определение точки в многоугольнике
- Задача о точке в многоугольнике (PIP) решает, находится ли точка на плоскости внутри, снаружи или на границе многоугольника.
- Применяется в компьютерной графике, компьютерном зрении, ГИС, планировании движения и САПР.
-
Ранние подходы
- Два общих подхода, построение луча и суммирование углов, использовались в 1974 году.
-
Алгоритм формирования луча
- Проверяет количество пересечений луча с границами многоугольника для определения местоположения точки.
- Известен с 1962 года, основан на наблюдении о переходе точки через границу.
- Может давать неточные результаты из-за ошибок округления в арифметике конечной точности.
-
Алгоритм подсчета количества витков
- Вычисляет число витков точки относительно многоугольника, отличное от нуля указывает на нахождение внутри.
- Суммирует углы многоугольника, но может быть медленным из-за тригонометрических функций.
- Улучшенный алгоритм Дэна Санди (2001) не использует углы и тригонометрию, работает быстрее.
-
Применение в SVG
- Алгоритмы используются для определения способа заливки фигур в SVG, влияют на атрибут «fill-rule».
- Для простых полигонов дают одинаковый результат, но для сложных могут быть различия.
-
Точка в полигональных запросах
- Задача решается с использованием общих подходов к определению местоположения точки.
- Для некоторых специальных полигонов существуют более простые решения.
-
Особые случаи
- Монотонные, звездообразные, выпуклые многоугольники и треугольники имеют упрощенные алгоритмы.
-
Рекомендации
- Ссылки на Java Topology Suite (JTS), обсуждение и методы определения количества витков.