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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Метод трассировки луча[править | править исходный текст]

Учёт числа пересечений[править | править исходный текст]

Методы работают по-разному для многоугольников с самопересекающейся границей. Слева: 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.

Ссылки[править | править исходный текст]