Изменения

==== Разбиение многоугольника на монотонные части ====

===== Основные понятия =====

Рассмотрим самую верхнюю — максимальную по оси <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>y</tex>-монотонный. Тогда докажем, что <tex>P</tex> содержит split и merge вершины. Поскольку <tex>P</tex> не <tex>y</tex>-монотонный, горизонтальная прямая <tex>l</tex> пересекает его стороны более двух раз. Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения <tex>l</tex> и <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате в некоторой точке <tex>r</tex>, где <tex>r \neq p</tex> (случай '''(a)''' на рисунке), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам <tex>P</tex>, будет split вершиной.

Если же <tex>r = p</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам <tex>P</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка <tex>r'</tex>, которая будет результатом пересечения <tex>l</tex> и <tex>P</tex>. При этом <tex>r' \neq p</tex>, в противном случае <tex>l</tex> будет пересекать <tex>P</tex> только два раза, то есть <tex>P</tex> будет <tex>y</tex>-монотонным, что противоречит нашему предположению. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.