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_x > q_x</tex>, соответственно точка <tex>p</tex> лежит ''выше'' точки <tex>q</tex>, если <tex>p_y \geqslant q_y</tex> и <tex>p_x < q_x</tex>.[[Файл:pic1.jpg|right|560|thumb|Пример результата работы алгоритма]]
=== Ушной метод ===
Более эффективным я