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

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

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

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

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

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

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

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

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

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

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

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

Можно определить, что точка P находится внутри многоугольника с вершинами V ₀ , V ₁ , ..., V _n = V ₀ , вычислив сумму:

${\displaystyle \sum _{i=1}^{n}\phi _{i},}$

где ${\displaystyle \phi _{i}}$ — угол (в радианах и со знаком) между лучами PV _{i − 1} и PV _i , то есть:

${\displaystyle \phi _{i}=\arccos \left({\frac {PV_{i-1}\cdot PV_{i}}{|PV_{i-1}|\cdot |PV_{i}|}}\right)\operatorname {sign} \left(\det {\begin{pmatrix}PV_{i-1}\\PV_{i}\end{pmatrix}}\right).}$

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

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

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

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

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

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

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

Примечания

Литература

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

Ссылки