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

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

Версия 07:08, 14 января 2014

Конспект написан не до конца, но основные вещи уже есть.

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

Начнём с того, что выпуклый многоугольник нам задан как замкнутая полилиния. Поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. За логарифм можно пройтись бинпоиском по углам и понять, в каком из них лежит точка. Когда мы нашли угол, за константное время проверяем, с какой стороны от противолежащего первой точке ребра многоугольника лежит точка. Итоговое время работы: [math]O(\log n)[/math].

Невыпуклый многоугольник