Взаимное расположение точки и многоугольника
В вычислительной геометрии широко известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник с \(N\) вершинами без самопересечений и произвольная точка \(P\), и требуется определить, лежит ли точка внутри многоугольника, причем многоугольник может быть как выпуклым, так и невыпуклым. На рисунке 1 мы можем видеть 3 варианта расположения точки относительно многоугольника: снаружи (точка \(P_{1}\)), внутри (точка \(P_{2}\)) и на границе (точка \(P_{3}\)). Две последние точки ему принадлежат, первая – нет.
Общий случай. Метод трассировки луча.
Идея решения задачи в случае произвольного многоугольника заключается в использовании так называемого «метода трассировки луча». Будем считать количество пересечений со сторонами многоугольника луча, который имеет начало в точке P и параллелен одной из осей координат (для удобства определим, что луч параллелен оси O1.
Заметим, что если количество пересечений четное, то точка лежит вне многоугольника, если же нечетное – внутри (см. рис. 2). Это основано на достаточно очевидном факте: при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи заданного многоугольника.
Однако, у такого способа есть недостаток: случаи при пересечении луча с вершиной многоугольника или совпадением с его стороной нами не учитываются, а значит их придется разбирать отдельно. Всего может возникнуть 6 разных проблемных ситуаций, представленных на рисунке 3. В случае а) мы должны засчитать пересечение границы лишь раз, в случаях б) и в) количество пересечений не изменяется. В ситуациях же г), д) и е) ребро, которое лежит на луче, можно считать безразличным, то есть его пересечение мы не засчитываем. Поэтому случаи г), д) и е) обрабатываются нами так же, как а), б) и в) соответственно. Таким образом, кроме проверки на пересечение с каждой из сторон многоугольника, нам нужно проверить для каждой вершины и стороны принадлежность к заданному лучу и, если принадлежность выполняется, по одну ли сторону от луча лежат соседние элементу стороны многоугольника.
Приведенный метод позволяет решить задачу за \(O(n)\), где \(n\) – количество углов многоугольника.
Случай выпуклого многоугольника. Бинарный поиск по углу.
Решение данной задачи становится быстрее, если нам изначально дано, что многоугольник выпуклый. Сразу отсортируем вершины в порядке обхода против часовой стрелки, если изначально они были заданы в другой последовательности.
Обозначим за \(C\) точку многоугольника с наименьшей координатой по оси \(O_{x}\) (если таких несколько, то из них берем самую нижнюю, то есть с наименьшей координатой по оси \(O_{y}\)) и заметим, что все остальные точки многоугольника лежат относительно нее в правой полуплоскости. Затем проведем лучи из \(C\) через все оставшиеся вершины многоугольника и воспользуемся бинарным поиском для нахождения сектора, в котором лежит точка \(P\).
Для тех, кто не знает, как строить бинарный поиск в данном случае, поясню. Изначально мы пронумеруем вершины многоугольника от \(0\) до \(N - 1\), начиная в точке \(C\). Далее введем переменные \(L\) и \(R\), которые будут отвечать за верхнюю и нижнюю границы нашего сектора соответственно. То есть изначально \(L = 1\), а \(R = N - 1\) (см. на рисунок 4). Теперь постоянно будем брать между вершинами, номера которых задаются \(L\) и \(R\), среднюю (обозначим ее \(S\), \(S = {L + R \over 2}\)) и смотреть, какому из двух углов – \(\angle{LCS}\) или \(\angle{RCS}\) – принадлежит точка \(P\). Если она принадлежит углу \(\angle{LCS}\), то нижнюю границу мы можем сдвинуть выше в точку \(S\), то есть теперь \(R = S\), иначе же мы сдвигаем верхнюю границу, то есть теперь \(L = S\). Будем сдвигать границы таким образом до тех пор, пока \(L\) и \(R\) не станут соседними, то есть пока их разность не станет равна 1, тем самым мы найдем сектор, которому принадлежит нужная нам точка \(P\) (на рисунке 4 получившиеся \(L\) и \(R\) обозначены как \(L_{новое}\) и \(R_{новое}\) соответственно).
Теперь, когда мы знаем сектор, в котором лежит точка \(P\), мы можем с легкостью определить, принадлежит ли точка многоугольнику. Для этого мы проверяем, пересекаются ли \(\overrightarrow{CP}\) и сторона \(LR\). Если нет, то точка \(P\) лежит внутри многоугольника, если да – то снаружи.
Благодаря использованию бинарного поиска по углу, данный алгоритм работает быстрее, чем тот, что был приведен для общего случая, а именно, за \(O(\log n)\), однако он не подходит для невыпуклых многоугольников.
Расстояние от точки до многоугольника.
После того, как мы узнали, принадлежит ли точка многоугольнику, мы можем без труда определить расстояние до него от нее: если точка лежит принадлежит многоугольнику, то оно будет равняться 0, если же нет, то его значение будет равно наименьшему из расстояний от данной точки до каждой из сторон многоугольника. Например, на рисунке 5 отмечены наименьшие расстояния от точки \(P\) до сторон многоугольника. Наименьшим из них является перпендикуляр к стороне \(AB\), значит, именно его длина является расстоянием от точки \(P\) до данного многоугольника.
