184
правки
Изменения
→Ушной метод
'''Триангуляция полигона ''' — декомпозиция многоугольника <tex>P</tex> на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет <tex>P</tex>. В строгом смысле слова, вершины этих треугольников должны совпадать с вершинами исходного многоугольника. Триангуляция любого многоугольника не единственна. В этом можно убедиться из примера на рисунке.[[Файл:2_examples_of_tringl.jpg|300px|thumb|right|Два способа триангуляции одной и той же фигуры]]
== Постановка задачи ==
|statement =
У любого простого <tex>n</tex>-вершинного многоугольника <tex>P</tex> всегда существует триангуляция, причём количество треугольников в ней <tex>n - 2</tex> независимо от самой триангуляции.
|proof=
[[Файл:Proof theorem.jpg|200px|thumb|right|Два случая в доказательстве теоремы]]
Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. Возьмём самую левую по оси <tex>x</tex> вершину <tex>v</tex> многоугольника <tex>P</tex> и две смежных с ней вершины <tex>u</tex> и <tex>w</tex>. Если отрезок <tex>uw</tex> принадлежит внутренней области <tex>P</tex> — мы нашли диагональ. В противном случае, во внутренней области треугольника <tex>\Delta uwv</tex> или на самом отрезке <tex>uw</tex> содержится одна или несколько вершин <tex>P</tex>. Выберем самую наиболее далеко отстоящую от <tex>uw</tex> вершину <tex>v'</tex>. Отрезок, соединяющий <tex>v</tex> и <tex>v'</tex> не может пересекать сторон <tex>P</tex>, поскольку в противном случае одна из вершин это отрезка будет располагаться дальше от <tex>uw</tex>, чем <tex>v'</tex>. Это противоречит условию выбора <tex>v'</tex>. В итоге получаем, что <tex>v'v</tex> — диагональ.
Любая диагональ делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>. За <tex>m_1</tex> и <tex>m_2</tex> обозначим количество вершин в <tex>P_1</tex> и <tex>P_2</tex> соответственно. <tex>m_1 < n</tex> и <tex>m_2 < n</tex>, поэтому по предположению индукции у <tex>P_1</tex> и <tex>P_2</tex> существует триангуляция, следовательно и у <tex>P</tex> она существует.
==== Разбиение многоугольника на монотонные части ====
===== Основные понятия =====
[[Файл:Split-merge.png|560px500px|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>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 вершиной.
[[Файл:Proof_lemma.jpg|500px450px]]
Если же <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 вершиной.
Рассмотрим заметающую прямую <tex>l</tex>, перпендукулярную <tex>y</tex>-оси, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l</tex>.
[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split '' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:
2) '''''Merge вершина'''''. В отличие от случая со split вершиной заранее вычислить указатель <tex>helper</tex> нельзя, поскольку merge вершина <tex>v_i</tex> должна быть соединена с вершиной, лежащей ниже заметающей прямой <tex>l</tex>. Для этого в <tex>helper</tex> левого относительно <tex>v_i</tex> ребра запишем саму <tex>v_i</tex>. Далее спускаем заметающую прямую вниз к следующей вершине <tex>v_m</tex>, обращаемся к <tex>helper</tex>'у её левого ребра. Проверяем, если там хранится merge вершина, строим диагональ <tex>v_{i}v_{m}</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.
[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''megre '' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]]
===== Структуры данных =====
В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <tex>T</tex>, в листьях которого будем хранить рёбра, пересекающие <tex>l</tex>, такие, что внутренняя область многоугольника будет лежать справа от них самих. С каждым таким ребром будем хранить его <tex>helper</tex>. Порядок следования листьев в дереве соответствует порядку следования рёбер в многоугольнике: слева направо. Дерево изменяется в зависимости от текущего состояния заметающей прямой. Создадим приоритетную очередь <tex>Q</tex> из вершин, в которой приоритетом будет <tex>y</tex>-координата вершины. Если две вершины имеют одинаковые <tex>y</tex>-координаты, больший приоритет у левой. Вершины будут добавляться на "остановках" заметающей прямой.
Многоугольник <tex>P</tex> и добавленные в процессе диагонали удобно хранить в виде двусвязного спика <tex>D</tex> рёбер и добавленных в процессе диагоналейс двойными связями (''DCEL — doubly-connected edge list''), так как потом это обеспечит эффективный доступ к каждой из частей, которые нужно будет триангулировать.
===== Псевдокод =====
MakeMonotone(P)
Construct(<tex>D</tex>); Construct(<tex>Q</tex>); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше. bst <tex>T</tex> = new bst(); while Q <tex> Q \neq \varnothing </tex>
Remove <tex>v_{max}</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex>
switch (Type_of_vertex(<tex>v_{max}</tex>)): //определение типа вершины
case 'regular':
HandleRegularVertex(<tex>v_{max}</tex>);
[[Файл:Split-merge - result.png|470px]]
Опишем теперь каждый метод из последнего switch:
HandleStartVertex(<tex>v_{i}</tex>)
Insert <tex>e_{i}</tex> in <tex>T</tex>
<tex>helper(e_{i}) \leftarrow v_i</tex>
HandleSplitVertex(<tex>v_{i}</tex>)
edge <tex>e_j</tex> = <tex>l \cap P</tex>
Search <tex>e_j</tex> in <tex>T</tex> Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i})</tex>) in <tex>D</tex>
<tex>helper(e_{j}) \leftarrow v_i</tex>
Insert <tex>e_{i}</tex> in <tex>T</tex>
<tex>helper(e_{i}) \leftarrow v_i</tex>
В последующих трех функциях обработки вершины <tex>v_i</tex> происходит обращение к смежному ребру <tex>e_{i-1}</tex>. Это сделано для вершин, относительно которых внутренняя область <tex>P</tex> лежит справа от них самих (вершина <tex>v_6</tex>), либо для двух подряд идущих merge вершин, таких как <tex>v_2</tex> и <tex>v_8</tex>.
HandleEndVertex(<tex>v_{i}</tex>)
if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in D
Delete <tex>e_{i-1}</tex> from T
HandleMergeVertex(<tex>v_{i}</tex>)
if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in <tex>D</tex> Delete <tex>e_{i-1}</tex> from <tex>T</tex>
edge <tex>e_j</tex> = <tex>l \cap P</tex>
Search <tex>e_j</tex> in <tex>T</tex>
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in <tex>D</tex>
<tex>helper(e_{j}) \leftarrow v_i</tex>
then
if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in <tex>D</tex> Delete <tex>e_{i-1}</tex> from <tex>T</tex> Insert <tex>e_{i}</tex> in <tex>T</tex>
<tex>helper(e_{i}) \leftarrow v_i</tex>
else
edge <tex>e_j</tex> = <tex>l \cap P</tex>
Search <tex>e_j</tex> in <tex>T</tex>
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in <tex>D</tex>
<tex>helper(e_{j}) \leftarrow v_i</tex>
Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, не попарно не пересекаются и не пересекают стороны <tex>P</tex>.
Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций. В (в них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной).
Допустим, что диагональ <tex>v_{i}v_{m}</tex> была построена с помощью ''HandleSplitVertex'' по достижению split вершины <tex>v_i</tex>. Рассмотрим четырёхугольник <tex>H</tex>, заключённый между <tex>e_j</tex> и <tex>e_k</tex> - левым и правым ребром относительно <tex>v_i</tex> и горизонтальными прямыми, проведёнными через <tex>v_i</tex> и <tex>v_m</tex>. Внутри <tex>H</tex>, не может находиться ни одной из вершин <tex>P</tex>, в противном случае <tex>helper(e_j)</tex> не равнялся бы <tex>v_m</tex>. Предположим теперь, что <tex>v_{i}v_{m}</tex> пересекает <tex>e_s</tex> одну из сторон <tex>P</tex>. Учитывая, что никаких вершин <tex>P</tex> не лежит внутри <tex>H</tex> и стороны <tex>P</tex> не пересекаются, то <tex>e_s</tex> должна пересечь либо отрезок, соединяющий <tex>e_j</tex> и <tex>v_m</tex>, либо <tex>e_j</tex> и <tex>v_i</tex>. [[Файл:Pic_of_correctness.jpg|400px|thumb|right|1) Вершин внутри <tex>H</tex> находиться не может; 2) <tex>v_{i}v_m</tex> может пересекать только рёбра, помеченные зелёным]] Такое возможно только в случае, когда точками пересечения будут являться <tex>v_i</tex> или <tex>v_m</tex>, что не противоречит условию. Отсюда <tex>v_{i}v_{m}</tex> не пересекает ни одну из сторон <tex>P</tex> в посторонних точках.
Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри <tex>QH</tex> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>, диагональ <tex>v_{i}v_m</tex> не может пересекать никакую из ранее добавленных диагоналей.
}}
===== Оценкка работы =====
Построение описанной выше приоритетной очереди <tex>Q</tex> происходит за линейное время. Когда заметающая прямая останавливается в вершине: операции с очередью занимают константу по времени, операции с деревом <tex>T</tex> на запросы и обновления требуют <tex>\mathcal{O}(\mathcal \log(n))</tex>. Добавление диагонали в <tex>D</tex> требует <tex>\mathcal{O}(1)</tex>. В итоге обработка каждой вершины требует <tex>\mathcal{O}(\log(n))</tex>, а весь алгоритм соответственно <tex>\mathcal{O}(n \log(n))</tex>. Что касается памяти, она очевидно составляет <tex>\mathcal{O}(n) </tex>. Очередь <tex>Q</tex> и дерево <tex>T</tex> занимают линейную память.
[[Файл:Triangulationg intro.jpg|170px|thumb|right|Зелёным помечена так называемая воронка, которая образуется, когда мы достигнем красной вершины]]
==== Триангуляция монотонного многоугольника ====
===== Идея =====
Будем проходить сверху вниз по вершинам многоугольника проводя диагонали где это возможно.
Отсортируем все вершины многоугольника <tex>P</tex> в порядке убывания их <tex>y</tex>-координаты. Заведём стек вершин <tex>S</tex>. В стеке будем хранить вершины в отсортированном порядке, которые были обработаны, но не были отрезаны от многоугольника, то есть находятся в той части многоугольника, которая ещё не была триангулирована. В момент обработки некоторой вершины, будем пытаться провести из неё как можно больше диагоналей к вершинам, содержащимся в стеке. Эти диагонали отрезают треугольники от <tex>P</tex>. На вершине стека будет храниться вершина, которая будет обрабатываться последней.
Часть многоугольника <tex>P</tex>, лежащая выше последней обработанной вершины <tex>v_i</tex> и которая ещё не была триангулирована имеет форму перевёрнутой воронки (см. рисунки). Одна сторона воронки состоит из одной из сторон <tex>P</tex>, а другая состоит из цепи вершин, которые лежат выше <tex>v_i</tex> и внутренние углы которых не меньше <tex>\pi</tex>. Несложно догадаться, что самая нижняя вершина стека является единственной выпуклой. Несложно также заметить, что при обработке следующей вершины свойство перевёрнутой воронки сохранится, то есть оно является инвариантом алгоритма.
[[Файл:Triang_alg_case1.jpg|200px|thumb|right|Первый случай. Синим помечены стороны воронки, зелёным — диагонали, а жёлтым границы новой ещё не протриангулированной области]]
===== Алгоритм =====
Рассмотрим процесс обработки вершины более подробно. Возможны два случая:
* Текущая вершина <tex>v_j</tex> является нижним концом стороны <tex>e</tex>, ограничивающего воронку. Вершины противоположной цепи уже были положены в стек. В этом случае можно просто построить диагонали, соединяющие <tex>v_j</tex> со всеми вершинами, находящимися в стеке, кроме последней. Последняя вершина в стеке уже соединена с <tex>v_j</tex> стороной <tex>e</tex>. Часть многоугольника <tex>P</tex>, лежащая выше <tex>v_j</tex>, которая не была триангулирована, ограничена диагональю, которая соединяет <tex>v_j</tex> с вершиной <tex>v_{s1}</tex>, которая была первой в стеке. Сторона многоугольника <tex>P</tex>, выходящая из <tex>v_{s1}</tex> направлена вниз. Снова образуется фигура c одним выпуклым углом, похожая на воронку — инвариант сохраняется. Вершины <tex>v_j</tex> и <tex>v_{s1}</tex> кладутся в стек, поскольку они были были обработаны, но по прежнему являются вершинами непротриангулированной части <tex>P</tex>.
* Вершина <tex>v_j</tex> принадлежит последовательной цепи вершин, добавленных в <tex>S</tex>. Вынем из стека верхнюю вершину <tex>v_{s1}</tex> — она уже соединена с <tex>v_{j}</tex> одной из сторон <tex>P</tex>. Затем будем пытаться выстраивать диагонали, соединяющие <tex>v_{j}</tex> c вынимаемыми из стека вершинами пока это возможно. Проверку на возможность построения диагонали <tex>v_{j}v_{k}</tex>, где <tex>v_{k}</tex> — текущая верхняя вершина стека, можно осуществлять посредством изучения взаимного расположения предыдущей вершины, вынутой из <tex>S</tex>, относительно <tex>v_{j}v_{k}</tex>. Когда мы достигнем вершины <tex>v_{k}</tex>, до которой невозможно провести диагональ, положим предыдущую вершину <tex>v_{k-1}</tex> обратно в стек. Вершина <tex>v_{k-1}</tex> является либо последней, до которой было возможно провести диагональ, либо, если ни одной диагонали из <tex>v_{j}</tex> провести не удалось, — соседом <tex>v_{j}</tex>. Далее положим <tex>v_{j}</tex> в стек. Опять же инвариант непротриангулированной части <tex>P</tex> сохраняется: одна сторона воронки ограничена частью стороны многоугольника, а другая цепью невыпуклых вершин.
[[Файл:Triang alg case2.jpg|500px|thumb|center|Второй случай. Синим помечена цепь из вершин, которая содержится в стеке <tex>S</tex> на момент достижения вершины <tex>v_j</tex>, рыжей помечена первая вершина, до которой невозможно провести диагональ, жёлтой помечена новая нетриангулированная область <tex>P</tex> в форме воронки]]
===== Псевдокод =====
Как ранее уже было отмечено, задаём <tex>P</tex> в виде рёберного списка c двойными связями <tex>D</tex>.
TriangulateMonotonePolygon(P)
vertex [n] V = new vertex(P); // массив вершин <tex>P</tex>, отсортированный по y-координате в порядке убывания.
stack S = new stack();
S.push(V[1]);
S.push(V[2]);
for j \leftarrow 3 to n - 1
if (V[j] = S.peek())
while (S <tex>\neq \varnothing </tex>)
if (S.size() <tex>\neq</tex> 1)
Insert edge(V[j], S.peek()) in D
S.pop()
S.push(V[j-1])
S.push(V[j]);
else
vertex last = S.peek();
S.pop();
while (IsValidDiagonal(edge(V[j], S.peek()), last)) //проверка возможности построения диагонали — предикат "левый поворот"
last = S.peek();
S.pop();
Insert edge(V[j], last) in D
S.push(last);
S.push(V[j]);
S.pop()
while (S <tex>\neq \varnothing </tex>)
if (S.size() <tex>\neq</tex> 1)
Insert edge(V[j], S.peek()) in D
S.pop()
===== Корректность =====
* Все построенные диагонали попарно не пересекаются. Это гарантируется тем, что при каждом просмотре определённой вершины рассматривается только та часть <tex>P'</tex> многоугольника <tex>P</tex>, которая не была протриангулирована, следовательно внутри этой области по определению не может лежать ни одной из уже построенных диагоналей. Несложно заметить, что в стеке <tex>S</tex> на каждой итерации главного цикла хранятся вершины, которые принадлежат именно <tex>P'</tex> и лежат выше рассматриваемой вершины.
* Количество построенных диагоналей всегда будет <tex>n-3</tex>, поэтому непротриангулированных частей в многоугольнике не останется.
===== Оценка работы =====
Построение массива вершин требует линейное время и занимает линейную память. Главный цикл ''for'' выполняется <tex>n-3</tex> раза. Каждая его итерация может потребовать линейное время. Однако заметим, что на каждой итерации главного цикла в стек кладутся максимум две вершины, следовательно общее число выполнения операции ''push'', включая первые две вершины, положенные в начале алгоритма, ограничено <tex>2n-4</tex>. Количество операций ''pop'' за время работы алгоритма не превысит количества операций ''push''. Отсюда общее время работы цикла ''for'' <tex>\mathcal{O}(n)</tex>. В итоге общее время работы <tex>\mathcal{O}(n)</tex>.
==== Общая оценка ====
Разбиение многоугольника на монотонные части занимает <tex>\mathcal{O}(n \log n)</tex> времени и <tex>\mathcal{O}(n)</tex> памяти. Триангуляция каждой из частей занимает линейную память и время. Учитывая то, что суммарное количество вершин во всех частях <tex>\mathcal{O}(n)</tex>, триангуляция всех частей займёт <tex>\mathcal{O}(n)</tex> по времени и по памяти.
В итоге общая оценка составляет <tex>\mathcal{O}(n \log n)</tex> по времени и <tex>\mathcal{O}(n)</tex> по памяти.
==== Прочие случаи ====
[[Файл:Monotone with holes.png|350px|thumb|right|Пример отверстия в форме монотонного многоугольника. У него обязательно будут существовать start и end вершина, если рассматривать его как обычный многоугольник. Однако, когда он станет полигональным отверстием, в силу определения start и end вершины обратятся в split и merge, которые соединятся с какими-то вершинами внешнего контура]]
Алгоритм так же работает и для частных случаев, например для многоугольника с полигональным отверстием. Такой многоугольник будет поделен на части без отверстий и будет успешно триангулирован. Это обуславливается тем, что хотя бы две вершины, принадлежащих отверстию будут split и merge (см. рисунок). Диагональ от таких вершин можно провести только до вершин внешнего контура, а поскольку у внутреннего отверстия хотя бы одна split и одна merge вершина весь многоугольник будет разделён как минимум на две части.
=== Ушной метод ===
