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>.
=== Ушной метод ===
Более эффективным я
