Точка внутри многоугольника
Допустим есть многоугольник из N (и это главное) вершин. И есть точка в произвольном месте. Необходимо определить принадлежит она ему или нет. Точки представлены в виде структуры:
struct point< unsigned int x; unsigned int y;>; Все решения и алгоритмы которые я находил были написаны для четырехугольников и для треугольников. Главное уточнение многоугольник может быть выпуклый и не выпуклый. Я остановился на идеи подсчитать сколько сторон луч выпущенный из точки пройдет. если четное число — не в многоугольнике. если не четное — в многоугольнике. То есть нам надо указывать вершины по часовой стрелке. Сделать структуру сторон. Но как проверять? Как расчитать эти стороны и сделать пересечение?
Отслеживать
задан 8 ноя 2015 в 16:53
Peter Lavreniuk Peter Lavreniuk
2,941 7 7 золотых знаков 28 28 серебряных знаков 55 55 бронзовых знаков
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
bool result = false; int j = size - 1; for (int i = 0; i < size; i++) < if ( (p[i].Y < point.Y && p[j].Y >= point.Y || p[j].Y < point.Y && p[i].Y >= point.Y) && (p[i].X + (point.Y - p[i].Y) / (p[j].Y - p[i].Y) * (p[j].X - p[i].X)
- p — список точек
- size — количество точек
- result — входит ли точка в многоугольник
Первая строка условия проверяет попадание point.Y между значениями p[i].Y и p[j].Y , контролирует направление прохода вершины и обеспечивает ненулевой знаменатель основной формулы.
Вторая строка проверяет нахождение стороны p[i]p[j] слева от точки point .
Третья строка формирует отрицательный ответ при чётном количестве сторон слева и положительный — при нечётном.
Отслеживать
ответ дан 8 ноя 2015 в 17:19
32.1k 19 19 золотых знаков 79 79 серебряных знаков 106 106 бронзовых знаков
А есть какой либо еще способ?
8 ноя 2015 в 17:20
@ParanoidPanda Вроде, всегда этот используют. Можно оптимизировать, заранее вычислив описывающую фигуру (прямоугольник), тогда большинство проверок будет быстрыми.
8 ноя 2015 в 17:23
данный способ основывается не на «выпуске луча» на сколько я понимаю
8 ноя 2015 в 17:24
@ParanoidPanda Горизонтальный луч же, если мне не изменяет зрение.
8 ноя 2015 в 17:34
18 ноя 2017 в 13:49
Пусть луч направлен горизонтально вправо.
Для каждой пары смежных точек:
- Сначала проверяете, лежит ли пара точек (краев отрезка) по одну сторону луча. Если по одну сторону — то луч не пересекает сторону.
- Если по разные стороны — нужно найти точку пересечения луча и прямой, проходящей через две данные точки. Это аналитическая геометрия, по сути, решение приводить не буду. Если точка пересечения правее точки, откуда исходит луч — значит пересечение есть.
Нужно учитывать специальный случай, когда луч проходит через вершину многоугольника:
- Если вторые точки обоих отрезков, которым принадлежит данная вершина находятся по одну сторону от луча, то считать это двумя пересечениями (или отсутствием пресечения — четность будет та же)
- Если вторые точки по разные стороны луча — считать одним пересечением.
Можно избежать необходимости проверки прохождения через точки, если точки многоугольника находятся в узлах сетки (например если координаты всегда целые, или заданы с фиксированной точностью): достаточно сместить точку, откуда исходит луч, вверх или вниз на небольшую величину (например на машинный эпсилон) тогда луч практически гарантированно не пройдет ни через одну из точек многоугольника.
Взаимное расположение точки и многоугольника
В вычислительной геометрии широко известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник с \(N\) вершинами без самопересечений и произвольная точка \(P\), и требуется определить, лежит ли точка внутри многоугольника, причем многоугольник может быть как выпуклым, так и невыпуклым. На рисунке 1 мы можем видеть 3 варианта расположения точки относительно многоугольника: снаружи (точка \(P_\)), внутри (точка \(P_\)) и на границе (точка \(P_\)). Две последние точки ему принадлежат, первая – нет.
Общий случай. Метод трассировки луча.
Идея решения задачи в случае произвольного многоугольника заключается в использовании так называемого «метода трассировки луча». Будем считать количество пересечений со сторонами многоугольника луча, который имеет начало в точке P и параллелен одной из осей координат (для удобства определим, что луч параллелен оси O1.
Заметим, что если количество пересечений четное, то точка лежит вне многоугольника, если же нечетное – внутри (см. рис. 2). Это основано на достаточно очевидном факте: при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи заданного многоугольника.
Однако, у такого способа есть недостаток: случаи при пересечении луча с вершиной многоугольника или совпадением с его стороной нами не учитываются, а значит их придется разбирать отдельно. Всего может возникнуть 6 разных проблемных ситуаций, представленных на рисунке 3. В случае а) мы должны засчитать пересечение границы лишь раз, в случаях б) и в) количество пересечений не изменяется. В ситуациях же г), д) и е) ребро, которое лежит на луче, можно считать безразличным, то есть его пересечение мы не засчитываем. Поэтому случаи г), д) и е) обрабатываются нами так же, как а), б) и в) соответственно. Таким образом, кроме проверки на пересечение с каждой из сторон многоугольника, нам нужно проверить для каждой вершины и стороны принадлежность к заданному лучу и, если принадлежность выполняется, по одну ли сторону от луча лежат соседние элементу стороны многоугольника.
Приведенный метод позволяет решить задачу за \(O(n)\), где \(n\) – количество углов многоугольника.
Случай выпуклого многоугольника. Бинарный поиск по углу.
Решение данной задачи становится быстрее, если нам изначально дано, что многоугольник выпуклый. Сразу отсортируем вершины в порядке обхода против часовой стрелки, если изначально они были заданы в другой последовательности.
Обозначим за \(C\) точку многоугольника с наименьшей координатой по оси \(O_\) (если таких несколько, то из них берем самую нижнюю, то есть с наименьшей координатой по оси \(O_\)) и заметим, что все остальные точки многоугольника лежат относительно нее в правой полуплоскости. Затем проведем лучи из \(C\) через все оставшиеся вершины многоугольника и воспользуемся бинарным поиском для нахождения сектора, в котором лежит точка \(P\).
Для тех, кто не знает, как строить бинарный поиск в данном случае, поясню. Изначально мы пронумеруем вершины многоугольника от \(0\) до \(N — 1\), начиная в точке \(C\). Далее введем переменные \(L\) и \(R\), которые будут отвечать за верхнюю и нижнюю границы нашего сектора соответственно. То есть изначально \(L = 1\), а \(R = N — 1\) (см. на рисунок 4). Теперь постоянно будем брать между вершинами, номера которых задаются \(L\) и \(R\), среднюю (обозначим ее \(S\), \(S = \)) и смотреть, какому из двух углов – \(\angle\) или \(\angle\) – принадлежит точка \(P\). Если она принадлежит углу \(\angle\), то нижнюю границу мы можем сдвинуть выше в точку \(S\), то есть теперь \(R = S\), иначе же мы сдвигаем верхнюю границу, то есть теперь \(L = S\). Будем сдвигать границы таким образом до тех пор, пока \(L\) и \(R\) не станут соседними, то есть пока их разность не станет равна 1, тем самым мы найдем сектор, которому принадлежит нужная нам точка \(P\) (на рисунке 4 получившиеся \(L\) и \(R\) обозначены как \(L_\) и \(R_\) соответственно).
Теперь, когда мы знаем сектор, в котором лежит точка \(P\), мы можем с легкостью определить, принадлежит ли точка многоугольнику. Для этого мы проверяем, пересекаются ли \(\overrightarrow\) и сторона \(LR\). Если нет, то точка \(P\) лежит внутри многоугольника, если да – то снаружи.
Благодаря использованию бинарного поиска по углу, данный алгоритм работает быстрее, чем тот, что был приведен для общего случая, а именно, за \(O(\log n)\), однако он не подходит для невыпуклых многоугольников.
Расстояние от точки до многоугольника.
После того, как мы узнали, принадлежит ли точка многоугольнику, мы можем без труда определить расстояние до него от нее: если точка лежит принадлежит многоугольнику, то оно будет равняться 0, если же нет, то его значение будет равно наименьшему из расстояний от данной точки до каждой из сторон многоугольника. Например, на рисунке 5 отмечены наименьшие расстояния от точки \(P\) до сторон многоугольника. Наименьшим из них является перпендикуляр к стороне \(AB\), значит, именно его длина является расстоянием от точки \(P\) до данного многоугольника.
Принадлежность точки выпуклому и невыпуклому многоугольникам
Выпуклый многоугольник задан как замкнутая полилиния, поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. Бинпоиском за логарифм можно пройтись по углам и понять, в каком из них лежит точка. Когда найден угол, за константное время можно проверить, с какой стороны от противолежащего первой точке ребра многоугольника лежит точка.
- если искомая точка [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] левый, то увеличим счётчик пересечений
Время работы алгоритма составляет [math]O(n)[/math] .
Принадлежность точки многоугольнику
Пусть в многоугольнике $n$ вершин. Рассмотрим алгоритм за $O(\log n)$.
Рассмотрим самую левую, а из таких самую нижнюю точку многоугольника — $O$. Если наша точка $P$ лежит левее или ниже нее, то сразу можем сказать, что она не принадлежит многоугольнику.
Проведем из $O$ диагонали ко всем вершинам многоугольника, получим, что он разбит на треугольники, одновременно соседние диагонали образуют последовательные углы. Давайте бинарным поиском найдем угол, в котором лежит точка $P$. Если бинарный поиск попал в один из крайних треугольников, то можно проверить руками, лежит ли точка внутри угла (для этого достаточно рассмотреть три векторных произведения), если это не так, то возвращаем FALSE.
После того как угол установлен, надо проверить принадлежность нужному треугольнику. Можно, например, проверить, не лежит ли точка на одной из сторон этого треугольника, если нет, то проверить принадлежность точки одновременно любым двум из трех углов треугольника.
Произвольный многоугольник
Предыдущий способ нельзя применить в данном случае, так как принадлежность треугольнику не будет означать принадлежность фигуре (в невыпуклом многоугольнике если $A$ и $B$ лежат в многоугольнике, то весь отрезок $AB$ может не лежать в нем целиком). Рассмотрим два способа за $O(n)$.
Подсчет углов
Мы считаем, что вершины даны в порядке обхода. Будем последовательно рассматривать углы с вершиной в точке $P$ (для которой определяем положение) и лучами, проходящими через соседние вершины многоугольника. Теперь, если просуммировать все эти углы по порядку (как ориентированные углы), то получится некоторая величина $\psi$.
В том случае, если точка лежит внутри многоугольника, $\psi = \pm 2\pi$. Иначе $\psi = 0$.
Если из произвольной точки пустить горизонтальный луч и если этот луч пересечет многоугольник, то он рано или поздно выйдет из этого многоугольника. Допустим, луч проходил строго через внутренние точки каких-то сторон, не задевая вершины. Если посчитать число пересечений с многоугольником, то для точки, находящейся внутри, это число будет нечетным («наружу-внутрь-наружу», 3 пересечения), в противном случае — четным. Отдельно стоит обработать случай, когда точка находится на границе.
Но как учесть прохождение через вершины? Во-первых, если луч на каком-то отрезке пути совпал со стороной многоугольника (то есть она была ему параллельна и они совпали), то это пересечение можно игнорировать, такую сторону можно сжать в одну точку и объединить концы ее соседних сторон.
Для остальных сторон будем рассматривать только нижнюю вершину и засчитатывать пересечение тольки при прохождении через внутреннюю точку или через нижнюю вершину.
Горизонтальные лучи
Заметим, что каждый отрезок рассматривается независимо, поэтому при прохождении луча через вершину, он пройдет как бы через две вершины — для одной стороны и для другой.
Посмотрим на пример. Луч, выпущенный из $G$, пройдет через два нижних конца отрезков — $ID$ и $CD$. То есть число пересечений четное, точка вне многоугольника.
Луч, выпущенный из $F$ наберет только одно пересечение, так как он пересекает одну верхнюю и одну нижнюю вершину отрезков. Поэтому точка внутри многоугольника.
Луч, выпущенный из $J$, проходит через две верхних и две нижних вершины, засчитывается два пересечения, точка вне многоугольника.
Луч выпущенный из $H$, проходит через два верхних конца, поэтому засчитывается ноль пересечений, точка вне многоугольника.
Решение удобно реализовывать, работая со списком сторон, при этом нам не важен порядок их рассмотрения. Решение работает за $O(n)$, так как надо просмотреть каждый отрезок.
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko