Изменения

Простой многоугольник Прямая <tex>PL</tex> называется '''монотоннымопорной прямой''' (англ. ''line of support'' относительно прямой ) для многоугольника <tex>lP</tex>, если любая его внутренность лежит по одну сторону от <tex>l'L</tex>, такая что при этом <tex>l' \perp lL</tex>, пересекает стороны проходит хотя бы через одну из вершин <tex>P</tex> не более двух раз (результатом пересечения <tex>l'</tex> и <tex>P</tex> может быть только один отрезок или точка).

{|border=0 width="100%"|{Определение{Теорема|definitionstatement=МногоугольникПусть <tex>L_1</tex> и <tex>L_2</tex> {{---}} две параллельные опорные прямые фигуры <tex>\Phi</tex>, монотонный относительно расстояние между которыми имеет максимальное значение. <tex>A_1</tex> и <tex>yA_2</tex>{{-оси называется '--}} граничные точки фигуры <tex>\Phi</tex>, принадлежащие соответственно прямым <tex>L_1</tex> и <tex>L_2</tex>. Тогда отрезок <tex>A_1A_2</tex> перпендикулярен обеим прямым <tex>L_1</tex> и <tex>L_2</tex>.|proof=Предположим, что это не так. Тогда расстояние между прямыми <tex>L_1</tex> и <tex>L_2</tex> было бы меньше, чем отрезок <tex>A_1A_2</tex>, и тем более меньше, чем расстояние между двумя опорными прямыми <tex>L'_1</tex> и <tex>L'_2</tex> фигуры <tex>\Phi</tex>, перпендикулярными к отрезку <tex>yA_1A_2</tex>-монотонным''', что противоречит условию.

Суть данного метода заключается в том, чтобы разбить многоугольник на монотонные части, а затем триангулировать каждую из них.=== Разбиение многоугольника на монотонные части =={| border="0" width="100%"[[Файл:Split-merge.png|500px|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>q</tex>, если <tex>p_y < q_y</tex> или если <tex>p_y = q_y</tex> и <tex>p_x > q_x</tex>, соответственно точка <tex>p</tex> лежит ''выше'' точки <tex>q</tex>, если <tex>p_y > q_y</tex> или если <tex>p_y = q_y</tex> и <tex>p_x < q_x</tex>. Это было сделано для того, чтобы избежать неопределённых ситуаций с вершинами, у которых <tex>y</tex>-координаты равны. Обозначим за <tex>\phi</tex> внутренний угол при некоторой вершине и определим далее пять типов вершин, четыре из которых являются поворотными:* '''''start вершина''''' — два её соседа лежат ниже её самой и <tex> \phi < \pi </tex>* '''''split вершина''''' — два её соседа лежат ниже её самой и <tex> \phi > \pi </tex>* '''''end вершина''''' — два её соседа лежат выше её самой и <tex> \phi < \pi </tex>* '''''merge вершина''''' — два её соседа лежат выше её самой и <tex> \phi > \pi </tex>* '''''regular вершина''''' — не является поворотной, в отличие от остальных, другими словами один её сосед находится выше, а другой ниже её самой. {{ЛеммаТеорема

Многоугольник <tex>P</tex> является <tex>y</tex>-монотонным, если в нём отсутствуют split и merge вершиныДиаметр выпуклого многоугольника равен максимальному расстоянию между параллельными опорными прямыми.

ПредположимПусть <tex>\Phi</tex> {{---}} выпуклая фигура, что <tex>PL_1</tex> не и <tex>yL_2</tex>{{--монотонный. Тогда докажем-}} параллельные опорные прямые, что расстояние между которыми имеет наибольшее возможное значение <tex>Pd</tex> содержит split и merge вершины. Поскольку , <tex>PA_1</tex> не и <tex>yA_2</tex>{{---монотонный, существует горизонтальная прямая }} общие точки фигуры <tex>l\Phi</tex>, которая пересекает его стороны более двух раз. Выберем и прямых <tex>lL_1</tex> таким образом, чтобы самой левой компонентой пересечения и <tex>lL_2</tex> и соответственно. По предыдущей теореме <tex>PA_1A_2</tex> был бы отрезок перпендикулярен к прямым <tex>pqL_1</tex>. Далее будем двигаться наверх по сторонам , <tex>PL_2</tex>, начиная от точки следовательно, его длина равна <tex>qd</tex>. В результате в некоторой точке Докажем, что расстояние между любыми двумя точками фигуры <tex>r\Phi</tex>, где не преводходит <tex>r \neq pd</tex> (случай '''(a)''' на рисунке). Действительно, прямая если <tex>lB</tex> снова пересечёт одну из сторон и <tex>PC</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам {{---}} какие-либо две точки фигуры <tex>P\Phi</tex>, будет split вершиной. [[Файл:Proof_lemma.jpg|450px]] Если же а <tex>r = pm</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам и <tex>Pn</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка {{---}} опорные прямые, перпендикулярные к отрезку <tex>r'BC</tex>, которая будет результатом пересечения то отрезок <tex>lBC</tex> и не превосходит расстояния между прямыми <tex>Pm</tex>. При этом и <tex>r' \neq pn</tex>, которое в противном случае свою очередь не превосходит <tex>ld</tex> будет пересекать . Следовательно, длина <tex>PBC</tex> только два раза, что противоречит выбору не может быть больше <tex>ld</tex>. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.

Чтобы сделать многоугольник монотоннымЗаметим, нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершинчто параллельные опорные прямые можно провести не через любую пару точек.

Рассмотрим горизонтальную заметающую прямую <tex>l</tex>, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l</tex>.{{Определение[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:definition= # '''''Split вершина'''''. Пусть <tex>e_j</tex> и <tex>e_k</tex> — ближайшее левое и правое ребро относительно split вершины <tex>v_i</tex>Точки, через которые <tex>l</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между <tex>e_j</tex> и <tex>e_k</tex>, наиболее приближённую к <tex>l</tex>можно провести параллельные опорные прямые, либо если такой точки не существет выбрать минимальную из верхних вершин <tex>e_j</tex> и <tex>e_k</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра <tex>e_j</tex>, который можно заранее вычислить. Тип вершины, хранящийся в <tex>helper</tex> не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю <tex>helper(e_j)</tex> её левого ребра, которое <tex>l</tex> пересекает в данный момент.# называть '''противолежащими''Merge вершина'(англ. ''antipodal''. В отличие от случая со split вершиной заранее вычислить указатель <tex>helper</tex> нельзя, поскольку merge вершина <tex>v_i</tex> должна быть соединена с вершиной, лежащей ниже заметающей прямой <tex>l</tex>. Для этого в <tex>helper(e_j)</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|Обработка ''merge'' вершины <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'')том, так как потом это обеспечит эффективный доступ к каждой из частейчтобы рассмотреть их, которые нужно будет триангулироватьне перебирая все пары точек.

{|border="0" width== Псевдокод ==="100%" MakeMonotone(P) Construct(D); Construct(Q); // функция Construct создаёт объекты |Рассмотрим рисунок справа. <tex>DL</tex> и <tex>QM</tex> {{---}} опорные прямые, описанные выше. bst T = new bst(); while Q проходящие через вершины <tex> \neq \varnothing A</tex> Remove и <tex>v_{max}D</tex> from Q соответственно. Значит, <tex>\langle A,D \rangle<// удаление вершины с наивысшим приоритетом tex> {{---}} противолежащая пара точек. Если начать вращать прямые против часовой стрелки вокруг данных точек, они будут оставаться опорными прямыми, пока одна из прямых не станет накладываться на сторону многоугольника. В нашем примере, при вращении <tex>QM</tex> switch (Type_of_vertex(к позиции <tex>v_{max}M'</tex>)): // определение типа вершины case 'start': HandleStartVertex(, <tex>v_{max}M</tex>); case 'end': HandleEndVertex(коснётся точки <tex>v_{max}E</tex>); case 'split': HandleSplitVertex(раньше, чем <tex>v_{max}L</tex>); case 'merge': HandleMergeVertex(коснётся <tex>v_{max}B</tex>); case 'regular': HandleRegularVertex(, поэтому <tex>v_{max}\langle A,E \rangle</tex>);становится новой парой противолежащих точек.

[[Файл:Split-merge - result.png|470px|thumb|right]] Опишем теперь каждый метод из последнего switch:  HandleStartVertex(Теперь <tex>v_{i}M'</tex>) Insert будет вращаться вокруг <tex>e_{i}E</tex> in T , а <tex>helper(e_{i}) \leftarrow v_iL'</tex>  HandleSplitVertex(продолжит вращаться вокруг <tex>v_{i}A</tex>) edge <tex>e_j</tex> = , и следующей парой противолежащих точек станет <tex>l \cap P</tex> Search <tex>e_j</tex> in T Insert edge(<tex>v_{i}</tex>langle B, <tex>helper(e_{j})</tex>) in D <tex>helper(e_{j}) \leftarrow v_i</tex> Insert <tex>e_{i}</tex> in T <tex>helper(e_{i}) E \leftarrow v_i</tex> В последующих трех функциях обработки вершины <tex>v_i</tex> происходит обращение к смежному ребру <tex>e_{i-1}rangle</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 D Delete <tex>e_{i-1}</tex> from T edge <tex>e_j</tex> = <tex>l \cap P</tex> Search <tex>e_j</tex> in T if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge') Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D <tex>helper(e_{j}) \leftarrow v_i</tex>  HandleRegularVertex(<tex>v_{i}</tex>) if (interior of <tex>P</tex> lies to the |[[Файл:calipers.png|250px|thumb|right of <tex>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 D Delete <tex>e_{i-1}</tex> from T Insert <tex>e_{i}</tex> in T <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 T if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge') Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D <tex>helper(e_{j|}) \leftarrow v_i</tex>===== Корректность ==Асимптотика ==={{ЛеммаТеорема

Функция ''MakeMonotone(P)'' корректно выполняет разбиение многоугольника Представленный выше алгоритм генерирует все пары противолежащих точек в многоугольнике <tex>P</tex>. Другими словами эта функция добавляет в , состоящем из <tex>PN</tex> множество непересекающихся диагоналейвершин, которые разбивают за время <tex>PO(N)</tex> на монотонные части.|proof=Тот факт, что <tex>P</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>H</tex> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>, диагональ <tex>v_{i}v_m</tex> будет посещена каждой из прямых не может пересекать никакую из ранее добавленных диагоналейболее двух раз.

=== Псевдокод =Ссылки ==Как ранее уже было отмечено, задаём <tex>P</tex> в виде рёберного списка c двойными связями <tex>D</tex>* ''M.I. TriangulateMonotonePolygon(P) vertex [n] V = new vertex(P); // массив вершин <tex>P</tex>Shamos'' Computational geometry, отсортированный по y1978 {{-координате в порядке убывания. stack S = new stack(); S.push(V[1]); S.push(V[2]); for j <tex>\leftarrow</tex> 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 <tex>\leftarrow</tex> S76.peek(); S* ''Яглом И.pop(); while (IsValidDiagonal(edge(V[j], SМ.peek()), last)) //проверка возможности построения //диагонали — предикат "левый поворот" last <tex>\leftarrow</tex> SБолтянский В.peek(); SГ.pop(); Insert edge(V[j]'' Выпуклые фигуры, last) in D S.push(last); S.push(V[j]); S1951 {{---}} С.pop() while (S <tex>\neq \varnothing </tex>) if (S.size() <tex>\neq</tex> 1) Insert edge(V[j]20, S144.peek()) in D S.pop()=== Корректность ===* Все построенные диагонали попарно не пересекаются. Это гарантируется тем, что при каждом просмотре определённой вершины рассматривается только та часть <tex>P'<[https:/tex> многоугольника <tex>P</tex>, которая не была протриангулирована, следовательно внутри этой области по определению не может лежать ни одной из уже построенных диагоналейgithub. Несложно заметить, что в стеке <tex>S</tex> на каждой итерации главного цикла хранятся вершины, которые принадлежат именно <tex>P'<com/tex> и лежат выше рассматриваемой вершины.* Количество построенных диагоналей всегда будет <tex>n-3<Megabyte777/tex>, поэтому непротриангулированных частей в многоугольнике не останется.=== Оценка работы ===Построение массива вершин требует линейное время и занимает линейную память. Главный цикл ''for'' выполняется <tex>n-3<cg/tex> раза. Каждая его итерация может потребовать линейное время. Однако заметим, что на каждой итерации главного цикла в стек кладутся максимум две вершины, следовательно общее число выполнения операции ''push'', включая первые две вершины, положенные в начале алгоритма, ограничено <tex>2n-4<blob/tex>. Количество операций ''pop'' за время работы алгоритма не превысит количества операций ''push''. Отсюда общее время работы цикла ''for'' <tex>\mathcal{O}(n)<master/tex>. В итоге общее время работы <tex>\mathcal{O}(n)<include/tex>.=== Общая оценка ===Разбиение многоугольника на монотонные части занимает <tex>\mathcal{O}(n \log n)<cg/tex> времени и <tex>\mathcal{O}(n)<operations/tex> памятиdiameter. Триангуляция каждой из частей занимает линейную память и время. Учитывая то, что суммарное количество вершин во всех частях <tex>\mathcal{O}(n)</tex>, триангуляция всех частей займёт <tex>\mathcal{O}(n)</tex> по времени и по памятиh Реализация - Github.com]