Принадлежность точки выпуклому и невыпуклому многоугольникам — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 6 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
{{ready}}
 
{{ready}}
 
== Выпуклый многоугольник ==
 
== Выпуклый многоугольник ==
Начнём с того, что выпуклый многоугольник нам задан как замкнутая полилиния. Поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. За логарифм можно пройтись бинпоиском по углам и {{Acronym|понять, в каком из них лежит точка|Для альтернативно одарённых: повороты должны различаться. А ещё кому-то может показаться неочевидным тот факт, что точка может лежать левее самой левой грани или правее самой правой. Это тоже надо сразу проверить}}. Когда мы нашли угол, за константное время {{Acronym|проверяем, с какой стороны от противолежащего первой точке ребра многоугольника лежит точка|для альтернативно одарённых: это проверяется поворотом}}. Итоговое время работы: <tex>O(\log n)</tex>.
+
Выпуклый многоугольник задан как замкнутая полилиния, поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. Бинпоиском за логарифм можно пройтись по углам и понять, в каком из них лежит точка. Когда найден угол, за константное время можно проверить, с какой стороны от противолежащего первой точке ребра многоугольника лежит точка.
 +
 
 +
Итоговый алгоритм:
 +
 
 +
* если искомая точка <tex>q</tex> лежит левее самой левой грани или правее самой правой, сразу возвращаем false
 +
* бинпоиском ищем такое ребро <tex>a_i a_{i+1}</tex>, не инцидентное самой первой точке <tex>a_0</tex> заданного многоугольника, что повороты точек <tex>a_0, a_i, q</tex> и <tex>a_0, a_{i+1}, q</tex> различаются
 +
* проверяем поворот точек <tex>a_i, a_{i+1}, q</tex>, если он левый — точка лежит внутри, если правый — снаружи
 +
 
 +
Итоговое время работы: <tex>O(\log n)</tex>.
  
 
== Невыпуклый многоугольник ==
 
== Невыпуклый многоугольник ==
Если точка лежит на ребре, сразу вернём true.
+
[[Файл:Point in polygon.png|400px|thumb|right|Отмечены только те точки, которые являются верхними для какого-либо ребра]]
 +
Очевидно, что если пустить из точки луч, то по чётности числа пересечений с рёбрами многоугольника можно определить, внутри точка лежит или снаружи.
 +
 
 +
Пустим луч, например, по иксу, переберём все рёбра и проверим их на пересечение с лучом.
 +
 
 +
Луч может попасть в точку, при этом прохождение через точку учтётся два раза (по разу для каждого отрезка, к которым принадлежит точка). Иногда это и есть то, чего нам хочется (когда фигура находится выше или ниже луча), но иногда нам хочется учесть только один раз. Для этого для каждого отрезка учитываем только верхнюю точку. Все случаи попадания луча в точку показаны на рисунке.
  
Очевидно, что, если пустить из точки луч, то по чётности числа пересечений с рёбрами многоугольника можно определить, внутри точка лежит или снаружи.
+
Получившийся алгоритм:
  
Пустим луч, например, по иксу и за <tex>O(n)</tex> переберём все рёбра и проверим их на пересечение с лучом. Как проверять: сначала проверим, что ордината точки лежит между ординатами концов ребра, затем {{Acronym|посмотрим, до ребра или после него начался луч|для альтернативно одарённых: это делается тоже поворотом}}.
+
* заведём счётчик пересечений и проинициализируем его нулём (либо просто заведём переменную типа bool, показывающую чётность числа пересечений)
 +
* для каждого ребра <tex>ab</tex> многоугольника:
 +
** если точка запроса <tex>q</tex> лежит на этом ребре, то сразу возвращаем true
 +
** если <tex>a_y=b_y</tex>, пропускаем этот отрезок, он не влияет на чётность числа пересечений
 +
** если <tex>q_y=max(a_y, b_y)</tex> и <tex>q_x < min(a_x, b_x)</tex>, увеличим счётчик пересечений
 +
** если <tex>q_y=min(a_y, b_y)</tex>, пропустим это ребро
 +
** если <tex>q_y</tex> лежит между <tex>a_y</tex> и <tex>b_y</tex> и поворот точек <tex>a,b,q</tex> левый, то увеличим счётчик пересечений
 +
* если число пересечений чётно, вернём false, иначе вернём true
  
Луч может попасть в точку, при этом прохождение через точку учтётся два раза (по разу для каждого отрезка, к которым принадлежит точка). Иногда это и есть то, чего нам хочется (когда фигура находится выше или ниже луча), но иногда нам хочется учесть только один раз. Для этого делаем такую штуку: для каждого отрезка учитываем {{Acronym|только верхнюю точку|А если отрезок горизонтальный, то забиваем на него, если точка не лежит на нём. После недолгих раздумий и разглядываний смежных отрезков станет очевидно, что на чётность числа пересечений он никак не влияет}}. Дальше {{Acronym|всё очевидно|Кому не очевидно, тот может порисовать картинки с лучом, попадающим в точку, и посчитать, сколько раз в каком случае учитывается пересечение}}.
+
Время работы алгоритма составляет <tex>O(n)</tex>.
  
 
[https://github.com/BorisMinaev/cg/blob/master/include/cg/algo/point_inside_polygon.h Реализация]
 
[https://github.com/BorisMinaev/cg/blob/master/include/cg/algo/point_inside_polygon.h Реализация]
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]

Текущая версия на 19:13, 4 сентября 2022

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

Выпуклый многоугольник

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

Итоговый алгоритм:

  • если искомая точка [math]q[/math] лежит левее самой левой грани или правее самой правой, сразу возвращаем false
  • бинпоиском ищем такое ребро [math]a_i a_{i+1}[/math], не инцидентное самой первой точке [math]a_0[/math] заданного многоугольника, что повороты точек [math]a_0, a_i, q[/math] и [math]a_0, a_{i+1}, q[/math] различаются
  • проверяем поворот точек [math]a_i, a_{i+1}, 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].

Реализация