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