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

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

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

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

Содержание

Метод трассировки луча

Учёт числа пересечений

Методы работают по-разному для многоугольников с самопересекающейся границей. Слева: even-odd rule. Справа: nonzero winding rule.

Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например в положительном направлении горизонтальной оси), и посчитаем сколько раз луч пересекает рёбра многоугольника. Для этого достаточно пройтись в цикле по рёбрам многоугольника и определить, пересекает ли луч каждое ребро. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно — то снаружи. Это основано на том простом наблюдении, что при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи многоугольника. Алгоритм известен под такими названиями, как crossing number (count) algorithm или even-odd rule.

В алгоритме возникает затруднение в вырожденном случае, когда луч пересекает вершину многоугольника. Один из приёмов для его преодоления заключается в том, чтобы считать, что такие вершины многоугольника лежат на бесконечно малую величину выше (или ниже) прямой луча, и стало быть пересечения на самом деле и нет.[1] Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец — выше или лежит на луче.

Алгоритм работает за время O(N) для N-угольника.

Учёт числа оборотов

Кривая делает два оборота вокруг данной точки.

Рассмотрим число оборотов, которое делает ориентированная граница многоугольника вокруг данной точки P. В алгебраической топологии это число называется winding number.[2] Оно может быть вычислено следующим образом. Как и раньше, выпустим луч из P в произвольном направлении и рассмотрим рёбра, которые он пересекает. Каждому пересечению присвоим число +1 или -1, в зависимости от того, как ребро пересекает луч — по часовой (слева направо) или против часовой стрелки (справа налево). Эти два случая можно различить по знаку скалярного произведения между направляющим вектором ребра и нормалью к направляющему вектору луча.[3] Сумма полученных величин и есть winding number. Сумма будет положительной или отрицательной, в зависимости от ориентации границы. Если она не равна нулю, то будем считать, что точка лежит внутри многоугольника, иначе — снаружи.

Такой алгоритм известен под названием nonzero winding rule.[3]

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

Метод суммирования углов

Можно определить, что точка P находится внутри многоугольника c вершинами V0, V1, ..., Vn = V0, вычислив сумму:

\sum_{i=1}^n \phi_i,

где \phi_i — угол (в радианах и со знаком) между лучами PVi - 1 и PVi, т.е.:

\phi_i = \arccos\left(\frac{PV_{i-1} \cdot PV_i}{|PV_{i-1}| \cdot |PV_i|}\right).

Можно доказать, что эта сумма есть не что иное, как winding number точки P относительно границы многоугольника, с точностью до константного множителя 2 \pi. Поэтому можно считать, что точка лежит снаружи многоугольника, если сумма равна нулю (или достаточно близка к нему, если используется приближённая арифметика). Однако данный метод весьма непрактичен, так как требует вычисления дорогостоящих операций для каждого ребра (обратных тригонометрических функций, квадратных корней, деления), и был даже назван «худшим в мире алгоритмом» для данной задачи.[1]

К. Вейлером был предложен практичный вариант этого метода, избегающий дорогостоящих операций и приближенных вычислений.[4] Было показано, что сумму углов можно вычислить, используя лишь операцию классификации точки многоугольника по квадрантам относительно точки P. Алгоритм Вейлера и некоторые улучшения к нему описываются в [5].

Алгоритмы c предобработкой

Выпуклые и звёздчатые многоугольники

Принадлежность точки выпуклому или звёздному N-угольнику может быть определена при помощи двоичного поиска за время O(log N), при затрате O(N) памяти и O(N) времени на предварительную обработку.[6]

Произвольный многоугольник

Задачу об принадлежности точки произвольному простому многоугольнику можно рассматривать как частный случай задачи о локализации точки в планарном подразбиении. Для N-угольника эта задача может быть решена за время O(log2 N) с использованием O(N) памяти и O(N log N) времени на предобработку.[7]

Примечания

  1. 1 2 Eric Haines. Point in Polygon Strategies
  2. Может переводиться на русский язык как «индекс кривой относительно точки», «число кручения», «число намоток», «винтовое число» и т.п.
  3. 1 2 Foley J. D., et al. Computer Graphics: Principles and Practice. Addison-Wesley. 1990. P. 965.
  4. K. Weiler. An incremental angle point in polygon test, in: P. Heckbert (Ed.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16–23.
  5. Kai Hormann and Alexander Agathos. The point in polygon problem for arbitrary polygons. Comput. Geom. Theory Appl. 20 (2001), 131-144.
  6. Препарата, Шеймос. Стр. 60-61.
  7. Препарата, Шеймос. Стр. 74. Теорема 2.6.

Литература

  • Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. Раздел 2.2: Задачи локализации точек. М.: Мир, 1989.

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Задача о принадлежности точки многоугольнику" в других словарях:

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

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

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


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»