184
правки
Изменения
→Монотонный метод
Уточним понятния ''выше'' и ''ниже'': точка <tex>p</tex> лежит ''ниже'' точки <tex>q</tex>, если <tex>p_y < q_y</tex> или если <tex>p_y < q_y</tex> и <tex>p_x > q_x</tex>, соответственно точка <tex>p</tex> лежит ''выше'' точки <tex>q</tex>, если <tex>p_y > q_y</tex> или если <tex>p_y = q_y</tex> и <tex>p_x < q_x</tex>. Это было сделано для того, чтобы избежать неопределённых ситуаций с вершинами, у которых <tex>y</tex>-координаты равны.
Обозначим за <tex>\phi</tex> внутренний угол при некоторой вершине вершине и определим далее пять типов вершин, четыре из которых являются поворотными:
* '''start вершина''' — два её соседа лежат ниже её самой и <tex> \phi < \pi </tex>
* '''split вершина''' — два её соседа лежат ниже её самой и <tex> \phi > \pi </tex>
