Принадлежность точки выпуклому и невыпуклому многоугольникам — различия между версиями
Yulya3102 (обсуждение | вклад) м (→Выпуклый многоугольник) |
Yulya3102 (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | {{ | + | {{ready}} |
== Выпуклый многоугольник == | == Выпуклый многоугольник == | ||
Начнём с того, что выпуклый многоугольник нам задан как замкнутая полилиния. Поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. За логарифм можно пройтись бинпоиском по углам и {{Acronym|понять, в каком из них лежит точка|для альтернативно одарённых: повороты должны различаться}}. Когда мы нашли угол, за константное время {{Acronym|проверяем, с какой стороны от противолежащего первой точке ребра многоугольника лежит точка|для альтернативно одарённых: это проверяется поворотом}}. Итоговое время работы: <tex>O(\log n)</tex>. | Начнём с того, что выпуклый многоугольник нам задан как замкнутая полилиния. Поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. За логарифм можно пройтись бинпоиском по углам и {{Acronym|понять, в каком из них лежит точка|для альтернативно одарённых: повороты должны различаться}}. Когда мы нашли угол, за константное время {{Acronym|проверяем, с какой стороны от противолежащего первой точке ребра многоугольника лежит точка|для альтернативно одарённых: это проверяется поворотом}}. Итоговое время работы: <tex>O(\log n)</tex>. | ||
== Невыпуклый многоугольник == | == Невыпуклый многоугольник == | ||
| + | Очевидно, что, если пустить из точки луч, то по чётности числа пересечений с рёбрами многоугольника можно определить, внутри точка лежит или снаружи. | ||
| + | |||
| + | Пустим луч, например, по иксу и за <tex>O(n)</tex> переберём все рёбра и проверим их на пересечение с лучом. Как проверять: сначала проверим, что ордината точки лежит между ординатами концов ребра, затем {{Acronym|посмотрим, до ребра или после него начался луч|для альтернативно одарённых: это делается тоже поворотом}}. | ||
| + | |||
| + | [[Категория: Вычислительная геометрия]] | ||
Версия 08:00, 14 января 2014
| Конспект готов к прочтению. |
Выпуклый многоугольник
Начнём с того, что выпуклый многоугольник нам задан как замкнутая полилиния. Поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. За логарифм можно пройтись бинпоиском по углам и понять, в каком из них лежит точка. Когда мы нашли угол, за константное время проверяем, с какой стороны от противолежащего первой точке ребра многоугольника лежит точка. Итоговое время работы: .
Невыпуклый многоугольник
Очевидно, что, если пустить из точки луч, то по чётности числа пересечений с рёбрами многоугольника можно определить, внутри точка лежит или снаружи.
Пустим луч, например, по иксу и за переберём все рёбра и проверим их на пересечение с лучом. Как проверять: сначала проверим, что ордината точки лежит между ординатами концов ребра, затем посмотрим, до ребра или после него начался луч.
