Принадлежность точки выпуклому и невыпуклому многоугольникам — различия между версиями
Yulya3102 (обсуждение | вклад) м (→Выпуклый многоугольник) |
Gromak (обсуждение | вклад) м |
||
| Строка 9: | Строка 9: | ||
Луч может попасть в точку, при этом прохождение через точку учтётся два раза (по разу для каждого отрезка, к которым принадлежит точка). Иногда это и есть то, чего нам хочется (когда фигура находится выше или ниже луча), но иногда нам хочется учесть только один раз. Для этого делаем такую штуку: для каждого отрезка учитываем {{Acronym|только верхнюю точку|А если отрезок горизонтальный, то забиваем на него, если точка не лежит на нём. После недолгих раздумий и разглядываний смежных отрезков станет очевидно, что на чётность числа пересечений он никак не влияет}}. Дальше {{Acronym|всё очевидно|Кому не очевидно, тот может порисовать картинки с лучом, попадающим в точку, и посчитать, сколько раз в каком случае учитывается пересечение}}. | Луч может попасть в точку, при этом прохождение через точку учтётся два раза (по разу для каждого отрезка, к которым принадлежит точка). Иногда это и есть то, чего нам хочется (когда фигура находится выше или ниже луча), но иногда нам хочется учесть только один раз. Для этого делаем такую штуку: для каждого отрезка учитываем {{Acronym|только верхнюю точку|А если отрезок горизонтальный, то забиваем на него, если точка не лежит на нём. После недолгих раздумий и разглядываний смежных отрезков станет очевидно, что на чётность числа пересечений он никак не влияет}}. Дальше {{Acronym|всё очевидно|Кому не очевидно, тот может порисовать картинки с лучом, попадающим в точку, и посчитать, сколько раз в каком случае учитывается пересечение}}. | ||
| + | |||
| + | [https://github.com/BorisMinaev/cg/blob/master/include/cg/algo/point_inside_polygon.h Реализация] | ||
[[Категория: Вычислительная геометрия]] | [[Категория: Вычислительная геометрия]] | ||
Версия 21:10, 18 января 2014
| Конспект готов к прочтению. |
Выпуклый многоугольник
Начнём с того, что выпуклый многоугольник нам задан как замкнутая полилиния. Поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. За логарифм можно пройтись бинпоиском по углам и понять, в каком из них лежит точка. Когда мы нашли угол, за константное время проверяем, с какой стороны от противолежащего первой точке ребра многоугольника лежит точка. Итоговое время работы: .
Невыпуклый многоугольник
Очевидно, что, если пустить из точки луч, то по чётности числа пересечений с рёбрами многоугольника можно определить, внутри точка лежит или снаружи.
Пустим луч, например, по иксу и за переберём все рёбра и проверим их на пересечение с лучом. Как проверять: сначала проверим, что ордината точки лежит между ординатами концов ребра, затем посмотрим, до ребра или после него начался луч.
Луч может попасть в точку, при этом прохождение через точку учтётся два раза (по разу для каждого отрезка, к которым принадлежит точка). Иногда это и есть то, чего нам хочется (когда фигура находится выше или ниже луча), но иногда нам хочется учесть только один раз. Для этого делаем такую штуку: для каждого отрезка учитываем только верхнюю точку. Дальше всё очевидно.
