184
правки
Изменения
→Монотонный метод
Идея данного метода заключается в том, чтобы разбить многоугольник на монотонные части, а затем триангулировать каждую из них.
[[Файл:Split-merge.png|560px|thumb||Пять типов вершин]]
Рассмотрим самую верхнюю — максимальную по оси <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 < 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>* '''end-вершина''' — два её соседа лежат выше её самой и <tex> \phi < \pi </tex>* '''merge-вершина''' — два её соседа лежат выше её самой и <tex> \phi > \pi </tex>* '''regular-вершина''' — не является поворотной, в отличие от остальных, другими словами один её сосед находится выше, а другой ниже её самой.
{{Лемма
|lemma=
Многоугольник, монотонный относительно <tex>y</tex>-оси называется '''является <tex>y</tex>-монотонным''', когда в нём отсутствуют split и merge вершины.
}}
=== Ушной метод ===
Более эффективным я
