184
правки
Изменения
→Идея
Обозначим за <tex>\phi</tex> внутренний угол при некоторой вершине вершине и определим далее пять типов вершин, четыре из которых являются поворотными:
* '''''start вершина''''' — два её соседа лежат ниже её самой и <tex> \phi < \pi </tex>* '''''split вершина''''' — два её соседа лежат ниже её самой и <tex> \phi > \pi </tex>* '''''end вершина''''' — два её соседа лежат выше её самой и <tex> \phi < \pi </tex>* '''''merge вершина''''' — два её соседа лежат выше её самой и <tex> \phi > \pi </tex>* '''''regular вершина''''' — не является поворотной, в отличие от остальных, другими словами один её сосед находится выше, а другой ниже её самой.
{{Лемма
}}
Таким образом, чтобы сделать многоугольник монотонным, нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершин.
===== Алгоритм =====
Рассмотрим заметающую прямую <tex>l</tex>, перпендукулярную <tex>y</tex>-оси, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. Создадим приоритетную очередь <tex>Q</tex> из вершин, в которой приоритетом будет <tex>y</tex>-координата вершины. Если две вершины имеют одинаковые <tex>y</tex>-координаты, больший приоритет у левой.
