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

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

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

Содержание

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

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

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

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

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

Учёт числа оборотов [ править | править код ]

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

Читайте также:  Почему кисти в фотошопе тормозят

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

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

Метод суммирования углов [ править | править код ]

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

∑ i = 1 n ϕ i , <displaystyle sum _^phi _,>

где ϕ i <displaystyle phi _> — угол (в радианах и со знаком) между лучами PVi − 1 и PVi , то есть:

ϕ i = arccos ⁡ ( P V i − 1 ⋅ P V i | P V i − 1 | ⋅ | P V i | ) sign ⁡ ( det ( P V i − 1 P V i ) ) . <displaystyle phi _=arccos left(<frac cdot PV_><|PV_|cdot |PV_|>>
ight)operatorname left(det <eginPV_\PV_
end>
ight).>

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

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

Алгоритмы c предобработкой [ править | править код ]

Выпуклые и звёздные многоугольники [ править | править код ]

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

Читайте также:  После обновления айфон перестал заряжаться

Произвольный многоугольник [ править | править код ]

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

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

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

Алгоритм определяет точки границ многоугольника как точки, ему принадлежащие.

Содержание

Описание [ править ]

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

Аргументами функции, реализующей проверку принадлежности данной точки данному многоугольнику произвольного вида, являются

  • указатель на массив пар целочисленных координат вершин многоугольника, а именно, на массив структур вида
  • число вершин многоугольника;
  • целочисленное значение координаты X заданной точки;
  • целочисленное значение координаты Y заданной точки.

Функция возвращает 1, если точка принадлежит многоугольнику, иначе — 0.

Функция имеет следующий вид.

Очень быстрый алгоритм [ править ]

В основе алгоритма лежит идея подсчёта количества пересечений луча, исходящего из данной точки в направлении горизонтальной оси, со сторонами многоугольника. Если оно чётное, точка не принадлежит многоугольнику. В данном алгоритме луч направлен влево.

Замечание: Так как умножение быстрее деления, условие можно записать так:

Однако, стоит заметить, что данный алгоритм не эквивалентен предыдущему, поэтому его использование может привести к неправильным результатам.

Perl [ править ]

Delphi (Object Pascal) [ править ]

JavaScript [ править ]

Python 3 [ править ]

На Python программа несколько отличается от других языков в сторону компактности из-за особенностей адресации элементов массива. Не нужны дополнительные переменные. Не работает с многоугольниками вогнутого типа

Быстрый алгоритм для случая, когда луч пересекает одну или несколько вершин [ править ]

Функция Cross определяет, пересекает ли луч j-ое ребро многоугольника:

Фрагмент основной программы:

Читайте также:  Самый хороший смартфон за 5000 рублей

Если переменная count примет нечетное значение, то точка лежит внутри многоугольника. В противном случает точка лежит вне заданого многоугольника.

Замечание: В данной реализации алгоритма луч направлен вниз.

Конспект готов к прочтению.

Выпуклый многоугольник [ править ]

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

  • если искомая точка [math]q[/math] лежит левее самой левой грани или правее самой правой, сразу возвращаем false
  • бинпоиском ищем такое ребро [math]a_i a_[/math] , не инцидентное самой первой точке [math]a_0[/math] заданного многоугольника, что повороты точек [math]a_0, a_i, q[/math] и [math]a_0, a_, q[/math] различаются
  • проверяем поворот точек [math]a_i, a_, q[/math] , если он левый — точка лежит внутри, если правый — снаружи

Итоговое время работы: [math]O(log n)[/math] .

Невыпуклый многоугольник [ править ]

Очевидно, что если пустить из точки луч, то по чётности числа пересечений с рёбрами многоугольника можно определить, внутри точка лежит или снаружи.

Пустим луч, например, по иксу, переберём все рёбра и проверим их на пересечение с лучом.

Луч может попасть в точку, при этом прохождение через точку учтётся два раза (по разу для каждого отрезка, к которым принадлежит точка). Иногда это и есть то, чего нам хочется (когда фигура находится выше или ниже луча), но иногда нам хочется учесть только один раз. Для этого для каждого отрезка учитываем только верхнюю точку. Все случаи попадания луча в точку показаны на рисунке.

  • заведём счётчик пересечений и проинициализируем его нулём (либо просто заведём переменную типа bool, показывающую чётность числа пересечений)
  • для каждого ребра [math]ab[/math] многоугольника:
  • если точка запроса [math]q[/math] лежит на этом ребре, то сразу возвращаем true
  • если [math]a_y=b_y[/math] , пропускаем этот отрезок, он не влияет на чётность числа пересечений
  • если [math]q_y=max(a_y, b_y)[/math] и [math]q_x lt min(a_x, b_x)[/math] , увеличим счётчик пересечений
  • если [math]q_y=min(a_y, b_y)[/math] , пропустим это ребро
  • если [math]q_y[/math] лежит между [math]a_y[/math] и [math]b_y[/math] и поворот точек [math]a,b,q[/math] левый, то увеличим счётчик пересечений
  • если число пересечений чётно, вернём false, иначе вернём true
  • Время работы алгоритма составляет [math]O(n)[/math] .

    Leave a Reply

    Ваш адрес email не будет опубликован. Обязательные поля помечены *

    You may use these HTML tags and attributes:

    <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>