184
правки
Изменения
→Монотонный метод
Рассмотрим самую верхнюю — максимальную по оси <tex>y</tex> вершину. Будем идти вниз по рёбрам до самой нижней — соотвественно минимальной по <tex>y</tex> вершине, то есть таким образом, что для некоторой вершины <tex>j</tex>: <tex>y_j > y_{j+1}</tex>. '''Поворотной''' назовём вершину <tex>i</tex>, на которой направление обхода будет меняется: <tex>y_{i-1} > y_i</tex> и <tex>y_i < y_{i+1}</tex>. Опишем более подробно этот тип вершин.
Уточним понятния ''выше'' и ''ниже'': точка <tex>p</tex> лежит ''ниже'' точки <tex>q</tex>, если <tex>p_y \leqslant < q_y</tex> или если <tex>p_y < q_y</tex> и <tex>p_x > q_x</tex>, соответственно точка <tex>p</tex> лежит ''выше'' точки <tex>q</tex>, если <tex>p_y \geqslant > q_y</tex> или если <tex>p_y = q_y</tex> и <tex>p_x < q_x</tex>. Это было сделано для того, чтобы избежать неопределённых ситуаций с вершинами, у которых <tex>y</tex>-координаты равны.
[[Файл:Split-merge.png|560px|thumb||Пять типов вершин]]
Определим далее пять типов вершин, четыре из которых являются поворотными:
* '''start-вершина''' — два её соседа лежат ниже её самой и внутренний угол в ней меньше <tex> \pi </tex>
* '''split-вершина''' — два её соседа лежат ниже её самой и внутренний угол в ней больше <tex> \pi </tex>
* '''end-вершина''' — два её соседа лежат выше её самой и внутренний угол в ней меньше <tex> \pi </tex>
* '''merge-вершина''' — два её соседа лежат выше её самой и внутренний угол в ней больше <tex> \pi </tex>
=== Ушной метод ===
Более эффективным я
