Изменения

[[Файл:PSLG.png|400px|thumb|left|Input <tex>\Rightarrow</tex> Output]]== Введение ==[[Файл:PSLG1PSLG_overlaying_w.png|400px|thumb|right|Создание новой компоненты]][[Файл:PSLG2.png|400px|thumb|right|Создание новой компонентыПример работы алгоритма пересечения ППЛГ]][[Файл:PSLG3.png|400px|thumb|left|Граф для поиска face]] ==Постановка задачи==Даны два Пересечением двух [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|ППЛГ]]является ППЛГ, требуется построить их объединение получающийся наложением двух исходных ППЛГ с созданием вершин в виде [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]точках пересечения ребер. При этом создав новые <tex>face</tex> и обновив старые. ===Формально=== Определим объединение пересечение двух pslg ППЛГ <tex>S1S_1</tex> и <tex>S2S_2</tex>, чтобы получился граф как ППЛГ <tex>O(S1S_1, S2S_2)</tex>, такой, что в нем существует грань <tex>facef</tex> f в тогда и только тогда, когда существуют грани <tex>O(S1, S2)f_1</tex>, тогда и только тогда есть в <tex>faceS_1</tex> f1 и f2 в <tex>S1f_2</tex> и в <tex>S2S_2</tex> соответственнотакие, что <tex>f</tex> является максимально связанным наибольшим связным подмножеством <tex>f1 f_1 \cap f2f_2</tex>. Требуется чтобы каждый Иначе говоря, пересечение двух ППЛГ — это разбиение плоскости с помощью ребер из <tex>faceS_1</tex> в и <tex>S_2</tex>. {{Задача|definition = Необходимо построить [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]] для <tex>O(S1S_1, S2S_2)</tex> был отмечен с помощью label of the , имея РСДС для <tex>facesS_1</tex> в и <tex>S1S_2</tex> и . Кроме того, для каждой грани из <tex>S2O(S_1, S_2)</tex>, который содержит их. Таким образом мы получаем доступ к информации хранящейся будем хранить ссылки на этих грани из <tex>S_1</tex> и <tex>facesS_2</tex>, содержащие ее.}}

===Алгоритм===Для начала скопируем ППЛГ <tex>S_1</tex> и <tex>S_2</tex> в новый РСДС. Далее необходимо преобразовать полученный РСДС, чтобы он соответствовал <tex>O(S_1, S_2)</tex>. Отдельно рассмотрим преобразования вершин, полуребер и граней.

====Первоначальное слияние=Вершины и полуребра ===[[Файл:PSLG_sweep_w.png|220px|right|thumb|Алгоритм заметающей прямой]]Алгоритм базируется на [[Пересечение множества отрезков|заметающей прямой]], определяющей пересечения отрезков. Запускаем алгоритм на множестве отрезков, представляющих собой ребра из <tex>S_1</tex> и <tex>S_2</tex>. Напомним, что алгоритм поддерживает очередь событий <tex>Q</tex> и текущий статус <tex>T</tex> заметающей прямой. Также будем поддерживать ссылки между ребрами статуса и соответствующими полуребрами из РСДС. Поддерживаемый инвариант: в любой момент времени РСДС над заметающей прямой корректен.

Для начала посмотрим, как можно больше информации от doubly connected edge lists для Обработка точки события происходит следующим образом: сначала обновляем <tex>S1Q</tex> и <tex>S2T</tex> мы можем повторно использовать (как в doubly connected edge lists для алгоритме пересечения отрезков). Если оба ребра события принадлежат одному ППЛГ, переходим к следующему событию. В противном случае, необходимо модифицировать РСДС. Возможны следующие варианты пересечений (см. рисунок ниже):<ol type="a"><li>Вершина ребра <tex>O(S1, S2)e_2</tex> проходит через ребро <tex>e_1</tex>, разбивая его на два новых ребра. Рассмотрим сеть ребер и вершин S1. Эта сеть разделена на кусочки краями </li><li>Ребро <tex>S2e_1</tex>. Эти кусочки в большинстве своем могут использоваться повторно, все, за исключением тех, которые отделены краями пересекает ребро <tex>S2e_2</tex>. Такие нужно обновлятьОбразуется четыре новых ребра. Если ориентация </li><li>Ребра <tex>e_1</tex> и <tex>half-edgee_2</tex> изменится, нам придется менять информацию пересекаются в этих записяхобщей вершине. Половинки </li><li>Вершина ребра ориентированы таким образом, что <tex>facee_1</tex>, которым они связаны лежит слева; форма проходит через ребро <tex>facee_2</tex> может изменяться в наложении, но он будет оставаться в той же стороне разбивая его на два новых ребра.</li><li>Ребра <tex>half-edgee_1</tex>. Следовательно, мы можем повторно использовать и <tex>half-edgee_2</tex> records, соответствующие краям, которые не пересекают ребра из другого графаимеют общий отрезок. Образуется новое ребро.</li></ol>

====Объединения графов====Во-первыхРассмотрим один из случаев, скопировать doubly­ connected edge lists остальные обрабатываются аналогично. Пусть ребро <tex>e</tex>S1из <tex>S_1</tex> и проходит через вершину <tex>S2v</tex> в один новый из <tex>DCELS_2</tex>. Новый Ребро <tex>e</tex> заменяем двумя ребрами <tex>e'</tex> и <tex>DCELe''</tex> не является допустимым . Два полуребра, соответствующих <tex>DCELe</tex>, т.к. он еще не представляет собой плоский подграф. Это задача алгоритма заметающей прямойзаменяются четырьмя полуребрами: он должен трансформировать два существующих полуребра будут исходить из концов <tex>DCELe</tex> в допустимый , а два новых полуребра — из <tex>DCELv</tex> (см. рисунок). Устанавливаем ссылки на близнецов для ребер <tex>O(S1, S2)e'</tex> путем вычисления пересечения между двумя сетями ребер, и связывая воедино соответствующие части из двух <tex>DCELe''</tex>. Мы применяем этот алгоритм Обновим ссылки на множестве сегментовследующие полуребра для <tex>h_1</tex> и <tex>h_4</tex>, что является объединением множеств ребер двух подграфов пусть это будут <tex>S1h_5</tex> и <tex>S2h_6</tex>, соответственно. Напомним, что алгоритм поддерживается двумя структурами данных: очереди событий Не забудем установить полуребра <tex>h_1</tex> и <tex>Qh_4</tex>, в котором хранятся точки событий, качестве предыдущих полуребер у <tex>h_5</tex> и структура состояния <tex>Th_6</tex>. Теперь обновим ссылки на полуребра, которой является бинарное дерево храненящее сегментыинцидентные вершине <tex>v</tex>. Для этого сначала при помощи порядка обхода определим, пересекающие линии разверткимежду какими полуребрами <tex>S_2</tex> находится <tex>e</tex>. Рассмотрим полуребро <tex>h_3</tex>: свяжем его с первым полуребром, расположенные слева направо. Мы теперь также должны поддерживать видимым из <tex>DCELh_4</tex> при обходе по часовой стрелке и исходящем из <tex>Dv</tex>. Первоначально Полуребро <tex>Dh_4</tex> содержит копию должно быть связано с первым полуребром, идущим в <tex>DCELv</tex> для , при обходе против часовой стрелки. Аналогично обработаем <tex>S1e''</tex> и .{| cellpadding="3"|[[Файл:PSLG_edge_vertex_w.png|x180px|center|thumb|Пересечение вершины <tex>DCELv</tex> для и ребра <tex>S2e</tex>]]|[[Файл:PSLG_edge_vertex2_w.png|x180px|center|thumb|Модификация полуребер]]|}==== Время работы ====Большинство шагов алгоритма работают константное время. В плоскости развертки преобразуем Определение соседних полуребер с <tex>De'</tex> к правильному и <tex>DCELe''</tex> происходит за линейное время от степени вершины. Следовательно, обновление РСДС не увеличивает время работы алгоритма пересечения отрезков, поэтому сведения о вершинах и полуребрах для итогового РСДС могут быть вычислены за время <tex>O(S1n \log{n} + k \log{n})</tex>, S2)где <tex>n</tex>. Мы держим перекрестные указатели между ребер в структуре состояния — сумма сложностей <tex>TS_1</tex> и половина текущих записей в <tex>DS_2</tex>, которые соответствуют им. Таким образом мы можем получить доступ к части <tex>Dk</tex>, которая должна быть изменена, когда мы сталкиваемся с точкой — количество точек пересечения.

В другом случае=== Грани ===[[Файл:PSLG_left_vertex_w.png|250px|right|thumb|Поиск внешних границ и дырок. Вершины <tex>v</tex> и <tex>u</tex> – левые вершины циклов. Для полуребер <tex>h_1</tex> и <tex>h_2</tex> грань <tex>f</tex> является внутренней, мы поддерживаем то, что в любое время в течение развертки, часть выше линии развертки наложения будет считаться правильнойдля полуребер <tex>h_3</tex> и <tex>h_4</tex> – внешней. Теперь что мы должны делать]]Необходимо получить информацию о гранях итогового РСДС: ссылка на полуребро внешней границы, когда мы достигнем точки событий. Прежде всегосписок ссылок на полуребра дырок внутри грани, мы обновляем ссылка на грани из <tex>TS_1</tex> и <tex>QS_2</tex>, как и содержащие новую грань. Также необходимо для полуребер установить ссылки на инцидентную грань.У каждой грани существует уникальная внешняя граница, поэтому количество граней будет на единицу больше, чем количество внешних границ (дополнительная граница ограничивает весь ППЛГ). Таким образом, каждой грани можно ставить в алгоритме заметающей прямойсоответствие внешнюю границу данной грани (кроме внешней грани ППЛГ, для нее мы введем мнимую внешнюю границу). Если событие включает в себя только ребра из одного из двух подграфовСледовательно, это необходимо обойти всевнешние границы ППЛГ и создать грань для каждой границы. Для того, чтобы определить, точка событие является вершинойцикл внешней границей или дыркой, которые могут быть использованы повторнорассмотрим самую левую вершину цикла <tex>v</tex> (определяется обходом по циклу). Напомним, что полуребра ориентированы так, что инцидентная им грань лежит левее полуребра. С учетом этого, оценим угол внутри грани между полуребрами, инцидентными <tex>v</tex>. Если событие включает края с двух подграфовугол меньше <tex>180^\circ</tex>, то цикл является внешней границей грани, мы должны сделать локальные изменения в противном случае – лежит внутри грани. Данное свойство выполняется для вершины <tex>Dv</tex> -- связать doubly­ connected edge list двух оригинальных подграфов в точке пересечения, но может не выполняться для остальных вершин.

Рассмотри один из 2 возможных случаевДля определения того, а именнокакие границы принадлежат одной грани, когда edge <tex>e</tex> из <tex>S1построим вспомогательный граф </tex> проходит через вершину <tex>V</tex> <tex>S2G</tex>, (см. Рисунок) edge <tex>e</tex> должно быть заменено двумя edges обозначим <tex>e'</tex> и <tex>e''</tex>. В <tex>DCEL</tex>, два <tex>half-edge</tex> для е должны превратиться в четырекотором каждая граница является вершиной. Мы создаем два новых <tex>half-edge</tex>, с <tex>V</tex> в нуле. Два существующих <tex>half-edge</tex> Также добавим вершину для е содержат конечные точки <tex>e</tex>, как их происхождениямнимой границы внешней грани. Тогда мы объединяем попарно существующие <tex>half-edges</tex> с новыми <tex>half-edges</tex>Между двумя вершинами графа, устанавливая их указатели twin'ов. Так <tex>e'</tex> представлен одним новым и одним существующим частично edgeсоответствующим двум циклам РСДС, существует ребро тогда и то же самое для <tex>e''</tex>. Теперь мы должны установить ряд <tex>Prev</tex> и <tex>Next</tex>. <tex>Next</tex> двух новых <tex>half-edges</tex> являются копией <tex>Next</tex> старого <tex>half-edge</tex>только тогда, не имеющего пары. В <tex>half-edges</tex>когда один цикл является границей дырки, в которые эти указатели точки должны обновлять свои <tex>Prev</tex> и установливать его на новых <tex>half-edges</tex>. Далее мы должны установить <tex>Next</tex> и <tex>Prev</tex> четырех <tex>half-edges</tex> представляющих <tex>e'</tex> и <tex>e''</tex>, и из четырех <tex>half-edges</tex> инциденого <tex>S2</tex> <tex>v</tex>а второй цикл является ближайшим слева к самой левой вершине первого цикла. Мы размещаем эти четыре <tex>half-edges</tex> от <tex>S2</tex>, проверяя, где <tex>e'</tex> и <tex>e''</tex> должны быть в циклическом порядке вершин вокруг Если левее самой левой вершины <tex>v</tex>. Есть четыре пары <tex>half-edges</tex>цикла нет полуребер, которые связанны между собой <tex>Next</tex> с одним и <tex>Prev</tex> то соединим этот цикл с другим. <tex>e'</tex> должен быть привязан к первому <tex>half-edge</tex> по часовой стрелке с началом в <tex>vмнимой границей внешней грани ППЛГ.</tex> <tex>half-edge</tex> для <tex>e'</tex> с началом в <tex>v</tex> должен быть связан с первым против часовой стрелки <tex>half-edge</tex> с окончанием в <tex>v</tex>{| cellpadding="3"| [[Файл:PSLG_graph_w. Точно также и для png|400px|center|thumb|Построение графа <tex>e''G</tex>. ]]|}

|about=К предыдущему вопросу|statement=Каждая компонента Каждой компоненте связности графа отвечает за множество циклов инцидентных одному <tex>faceG</tex>соответствует множество циклов, инцидентных только одной грани.|proof= Рассмотрим цикл <tex>C</tex>, который ограничивает дыру ограничивающий дырку в <tex>face</tex> грани <tex>f</tex>. Поскольку Грань <tex>f</tex> локально лежит левее самой левой вершины из <tex>C</tex>, то поэтому <tex>C</tex> должен быть соединен связан с другим циклом, который тоже ограничивает грани <tex>f</tex>. отсюда следуетСледовательно, что циклы есть компонента одной компоненты связности в графе, описывающая один и тот-же графа <tex>faceG</tex>ограничивают одну и ту же грань. Для того, что бы закончить доказательство, покажемПокажем, что каждый цикл , ограничивающий дыру в дырку грани <tex>f</tex> есть , находится в той же одной компоненте связности, что и внешняя граница с внешней границей грани <tex>f</tex>. Предположим, что есть существует цикл, для которого это не таквыполняется. Пусть <tex>C</tex> — – самый левый такой цикл, то есть тот, чья самая причем его левая вершина также самая левая. По определению есть , существует ребро между <tex>C</tex> и неким циклом <tex>C'</tex>, который лежит слева от самой левой вершины левее <tex>C</tex>. Следовательно , <tex>C'</tex> лежит в той же одной компоненте связностис <tex>C</tex>, причем <tex>C'</tex> не является внешней границей <tex>f</tex>. Получается, что и <tex>C'</tex>, который не в той же компонентележит левее <tex>C</tex>, что внешняя граница противоречит определению <tex>fC</tex>. Противоречие.

==== Построение графа <tex>G</tex>====Напомним, что в алгоритме развертки плоскости заметающей прямой для отрезка пересечения отрезков мы всегда искали сегменты сразу слева от ближайший отрезок, находящийся левее точки событий. (Они должны были быть проверены на пересечении с крайнего левого края через точку событийсобытия.) Таким образом, Эта информация, при помощи которой мы должны построить необходима для построения графа <tex>G</tex> определяется в плоскости развертки. Таким образом, чтобы Сначала создадим вершину для каждой границы. Далее необходимо построить <tex>G</tex>ребра в графе, мы сначала делаем узел для каждого цикла. Чтобы найти дуги <tex>G</tex>, рассмотрим этого найдем левую вершину <tex>V</tex> каждой дырки и определим, какое ребро лежит слева от данной вершины. Для эффективности будем для каждого циклаполуребра хранить ссылку на вершину графа, ограничивающую отверстиесодержащую это полуребро. Если <tex>half-edge</tex> сразу же выходит из <tex>V</tex>, то мы добавляем дугу между двумя узлами в <tex>G</tex>, представляющих цикл, содержащий е и цикл у которого <tex>V</tex> является самой левой вершиной. Чтобы найти эти узлы в <tex>G</tex> мы должны указатели от каждого <tex>half-edge</tex> записать в узел <tex>G</tex>Таким образом, представляющего цикл этот. Так информация o <tex>face</tex> в doubly­connected edge list о гранях может быть установлена в восстановлена за время <tex>ОO(n\ +\ k)</tex> времени, после плоскости развертки. Каждая грань <tex>e</tex> в наложении должна быть помечена с именами <tex>face</tex> в старых графах, которые содержали егоалгоритма заметающей прямой. Чтобы найти эти <tex>face</tex>Также заметим, надо рассмотреть произвольную вершину <tex>V</tex> что информацию о структуре графа можно хранить в <tex>F</tex>. Если <tex>v</tex> является пересечением <tex>e1</tex> от <tex>S1</tex> и <tex>е2</tex> от <tex>S2</tex>, то мы можем решить, какие <tex>face</tex> из <tex>S1</tex> и <tex>S2</tex> содержат <tex>F</tex>, глядя на <tex>incident\_face</tex> указатель соответствующих <tex>half-edges</tex> соответствующих <tex>e1</tex> и <tex>e2</tex>. Если <tex>v</tex> не пересечение, но вершина, скажем, S1, то мы знаем только <tex>face</tex> S1, содержащей <tex>f</tex>. Чтобы найти <tex>face</tex> <tex>S2</tex> , содержащий <tex>F</tex>, мы должны определить <tex>face</tex> <tex>S2</tex>, которое содержит <tex>v</tex>. Другими словами, если бы мы знали для каждой вершины <tex>S1</tex>, в котором <tex>face</tex> <tex>S2</tex> находился, и наоборот, то мы могли бы обозначить <tex>face</tex> <tex>O(S1, S2)</tex> правильнозаписях граней.

==Итог== Маркировка граней ===='''MapOverlay (Необходимо для каждой грани РСДС определить, какие грани из <tex>S_1</tex> и <tex>S_2</tex> содержат ее. Рассмотрим вершину <tex>v</tex> грани <tex>f</tex>. Если <tex>v</tex> является пересечением ребра <tex>e_1</tex> из <tex>S_1</tex> и ребра <tex>e_2</tex> из <tex>S_2</tex>, то по указателям на инцидентные грани можно определить, какие грани содержат данные ребра. Если <tex>v</tex> является вершиной <tex>S_1</tex>, то мы можем определить только грань из <tex>S_1</tex>, содержащую <tex>v</tex>. Необходимо научиться определять грань из <tex>S_2</tex>)''' , содержащую <tex>:v</tex>. То есть для каждой вершины из <tex>S_1</tex> мы должны знать, какая грань из <tex>S_2</tex> содержит данную вершину, и наоборот. Это также делается заметающей прямой.

1. Копируем === Итог ===Вход: два ППЛГ <tex>S_1</tex> и <tex>S_2</tex> , представленные в граф <tex>D</tex>виде РСДС.

2Выход: пересечение <tex>S_1</tex> и <tex>S_2</tex>, представленное в виде РСДС <tex>D</tex>.# Скопируем <tex>S_1</tex> и <tex>S_2</tex> в новый РСДС <tex>D</tex>. Находим все # Найдем пересечения ребер из <tex>S_1</tex> с ребрами из и <tex>S_2</tex> с помощью заметающей прямой. При обработке события будем обновлять <tex>D</tex>, если событие затрагивает <tex>S_1</tex> и <tex>S_2</tex>. Также для вершины события сохраним информацию о ближайшем полуребре слева.# Найдем граничные циклы в <tex>O(S_1, S_2)</tex>, обходя <tex>D</tex>.# Построим граф <tex>G</tex>, вершинам которого соответствуют циклы, соединив ребрами дырки и циклы, ближайшие слева к левым вершинам дырок.# Для каждой компоненты связности графа <tex>G</tex>: пусть <tex>C</tex> – внешняя граница компоненты связности, ограничивающая грань <tex>f</tex>. Создать запись для этой грани, установить ссылку на полуребро внешней границы грани и ссылки на полуребра дырок грани. Также для всех полуребер грани установить ссылки на инцидентную грань.# Для каждой грани <tex>f</tex> из <tex>O(S_1, S_2)</tex> установить ссылки на грани из <tex>S_1</tex> и <tex>S_2</tex>, содержащие <tex>f</tex>.

2.1 Когда находим точки пересечения== Общее время работы =={{Теорема|statement=Пусть <tex>S_1</tex> имеет сложность <tex>n_1</tex>, то обновляем <tex>DS_2</tex> имеет сложность <tex>n_2</tex>, то есть строим из него [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]<tex>n = n_1 + n_2</tex>. 3. Теперь Пересечение <tex>DS_1</tex> это нормальный [[ППЛГ и РСДС <tex>S_2</tex> может быть построено за время <tex>O(PSLG и DCELn \log{n} + k \log{n}): определение, построение РСДС множества прямых|РСДС]]</tex>, но без информации о где <tex>facek</tex>'ах. 4. Находим boundary cycles в – количество точек пересечения <tex>DS_1</tex>. То есть обновляем этот граф. Пока только добавляя в него ребра (и <tex>half-edgeS_2</tex>'ы соответственно). 5. Создаем граф |proof=Копирование двух РСДС в один занимает <tex>GO(n)</tex> (о нем ниже)времени, в котором узлы будут отвечать за boundary cycles и в котором ребра будут соединять только те узлы, один из которых будет являться границей дыры (заметающая прямая работает <tex>holeO(n \log{n} + k \log{n})</tex>, это внутренний цикл времени по лемме. Создание граней работает линейное время от сложности <tex>faceO(S_1, S_2)</tex>'a), а другой будет находиться слева от самой левой точки первого. Маркировка граней РСДС работает за <tex>O(В случае, если это самая внешняя граница, то для нее пусть будет мнимая гигантская граница, с которой мы ее и соединимn \log{n} + k \log{n})</tex>. 5.1. Для каждой компоненты графа:}}

Пусть <tex>C</tex> будет уникальная наружная граница цикла в компоненте, а <tex>f</tex> будет означать face ограниченный этим циклом== См. Создадим face для <tex>f</tex>. Запишем <tex>outer\_component</tex> в какой-нибудь <tex>half-edge</tex> из <tex>C</tex>. И создадим список <tex>inner\_components</tex>также ==*[[ППЛГ и РСДС (PSLG и DCEL): определение, состоящий из указателей на какой-нибудь <tex>half-edge</tex> из каждого цикла. А так же пусть <tex>incident\_face</tex> в каждом <tex>half-edge</tex> будут обновлены на <tex>f</tex>.построение РСДС множества прямых]]*[[Пересечение множества отрезков]]

== Литература и источники ==* [[Категория: Вычислительная геометрия. Алгоритмы и приложения, де Берг Марк ]][[Категория: ППЛГ и другие. Глава 2.3РСДС]]