Даны два [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|ППЛГ]], требуется построить их объединение в виде [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]. При этом создав новые <tex>face</tex> и обновив старые.
==Алгоритм=Формально==='''MapOverlay Определим объединение двух pslg <tex>S1</tex> и <tex>S2</tex>, чтобы получился граф <tex>O(S1, S2)</tex>, такой, что существует <tex>face</tex> f в <tex>O(S1, S2)</tex>, тогда и только тогда есть <tex>face</tex> f1 и f2 в <tex>S1</tex> и <tex>S_1S2</tex>соответственно, что <tex>S_2f</tex>является максимально связанным подмножеством <tex>f1 \cap f2</tex>. Требуется чтобы каждый <tex>face</tex> в <tex>O(S1, S2)''' </tex> был отмечен с помощью label of the <tex>faces</tex> в <tex>:S1</tex>и <tex>S2</tex>, который содержит их. Таким образом мы получаем доступ к информации хранящейся на этих <tex>faces</tex>. ===Алгоритм===
1. Копируем <tex>S_1</tex> и <tex>S_2</tex> в граф <tex>D</tex>.====Первоначальное слияние====
2Для начала посмотрим, как можно больше информации от doubly connected edge lists для <tex>S1</tex> и <tex>S2</tex> мы можем повторно использовать в doubly connected edge lists для <tex>O(S1, S2)</tex>. Рассмотрим сеть ребер и вершин S1. Эта сеть разделена на кусочки краями <tex>S2</tex>. Находим Эти кусочки в большинстве своем могут использоваться повторно, все пересечения ребер , за исключением тех, которые отделены краями <tex>S2</tex>. Такие нужно обновлять. Если ориентация <tex>half-edge</tex> изменится, нам придется менять информацию в этих записях. Половинки ребра ориентированы таким образом, что <tex>face</tex>, которым они связаны лежит слева; форма <tex>face</tex> может изменяться в наложении, но он будет оставаться в той же стороне <tex>half-edge</tex>. Следовательно, мы можем повторно использовать <tex>half-edge</tex> records, соответствующие краям, которые не пересекаются ребра из другой карты. Иными словами, есть только <tex>half-edge</tex> records в <tex>DCEL</tex> для <tex>O(S1, S2)</tex>, которые мы не можем заимствовать из <tex>S_1S1</tex> или <tex>S2</tex> с ребрами , ими являются те, которые попадают на пересечение между краями из разных карт.Это предлагает следующие подходы. Во-первых, скопировать doublyconnected edge lists <tex>S1</tex> и <tex>S_2S2</tex> с помощью заметающей прямойв один новый <tex>DCEL</tex>. Новый <tex>DCEL</tex> не является допустимым <tex>DCEL</tex>, т.к. он еще не представляет собой плоский подграф.
2.1 Когда находим точки пересечения, то обновляем <tex>D</tex>, то есть строим из него [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]].====Объединения графов====
3Это задача алгоритма заметающей прямой: он должен трансформировать <tex>DCEL</tex> в допустимый <tex>DCEL</tex> для <tex>O(S1, S2)</tex> путем вычисления пересечения между двумя сетями ребер, и связывая воедино соответствующие части из двух <tex>DCEL</tex>. Мы применяем этот алгоритм на множестве сегментов, что является объединением множеств ребер двух подграфов <tex>S1</tex> и <tex>S2</tex>. Напомним, что алгоритм поддерживается двумя структурами данных: очереди событий <tex>Q</tex>, в котором хранятся точки событий, и структура состояния <tex>T</tex>, которой является бинарное дерево храненящее сегменты, пересекающие линии развертки, расположенные слева направо. Мы теперь также должны поддерживать <tex>DCEL</tex> <tex>D</tex>. Теперь Первоначально <tex>D</tex> это нормальный [[ППЛГ содержит копию <tex>DCEL</tex> для <tex>S1</tex> и РСДС <tex>DCEL</tex> для <tex>S2</tex>. В плоскости развертки преобразуем <tex>D</tex> к правильному <tex>DCEL</tex> для <tex>O(PSLG S1, S2)</tex>. Мы держим перекрестные указатели между ребер в структуре состояния <tex>T</tex> и DCEL): определениеполовина текущих записей в <tex>D</tex>, построение РСДС множества прямых|РСДС]], но без информации о которые соответствуют им. Таким образом мы можем получить доступ к части <tex>faceD</tex>'ах, которая должна быть изменена, когда мы сталкиваемся с точкой пересечения.
4В другом случае, мы поддерживаем то, что в любое время в течение развертки, часть выше линии развертки наложения будет считаться правильной. Теперь что мы должны делать, когда мы достигнем точки событий. Находим boundary cycles в Прежде всего, мы обновляем <tex>T</tex> и <tex>DQ</tex>, как и в алгоритме заметающей прямой. То есть обновляем этот графЕсли событие включает в себя только ребра из одного из двух подграфов, это все, точка событие является вершиной, которые могут быть использованы повторно. Пока только добавляя Если событие включает края с двух подграфов, мы должны сделать локальные изменения в него ребра (<tex>half-edgeD</tex>'ы соответственно)-- связать doubly connected edge list двух оригинальных подграфов в точке пересечения.
5. Создаем граф Рассмотри один из 2 возможных случаев, а именно, когда edge <tex>е</tex> из <tex>S1</tex> проходит через вершину <tex>V</tex> <tex>GS2</tex> , (о нем нижесм. Рисунок)edge <tex>е</tex> должно быть заменено двумя edges обозначим <tex>e'</tex> и <tex>e''</tex>. В <tex>DCEL</tex>, два <tex>half-edge</tex> для е должны превратиться в котором узлы будут отвечать за boundary cycles и четыре. Мы создаем два новых <tex>half-edge</tex>, с <tex>V</tex> в котором ребра будут соединять только те узлынуле. Два существующих <tex>half-edge</tex> для е содержат конечные точки <tex>e</tex>, один из которых будет являться границей дыры (как их происхождения. Тогда мы объединяем попарно существующие <tex>half-edges</tex> с новыми <tex>holehalf-edges</tex>, это внутренний цикл устанавливая их указатели twin'ов. Так <tex>facee'</tex>представлен одним новым и одним существующим частично edge, и то же самое для <tex>e''a)</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>. Точно также и соединим)для <tex>e''</tex>.
5.1. Для каждой компоненты графа:====Время работы объединения====
Пусть <tex>C</tex> будет уникальная наружная граница цикла Большинство из шагов в компонентеприведенном выше описании принимать только константное время. Есть случаи на которые потребуется дополнительное время, а О(M), где Mчисло ребер, точки событий. Это означает, что обновление <tex>fD</tex> будет означать face ограниченный этим цикломне увеличивает время работы алгоритма заметащей прямой асимптотически. Создадим face для <tex>f</tex>Любое пересечение, которое мы находим является вершиной наложения. Запишем <tex>outer\_component</tex> в какой-нибудь Из этого следует, что вершина record и <tex>half-edge</tex> из record doubly connected edge list для <tex>CO(S1, S2)</tex>. И создадим список можно вычислить в <tex>innerO(N\ *\ log N\ +\ k\_components*\ log\ n)</tex>время, состоящий из указателей на какой-нибудь где <tex>half-edgen</tex> из каждого цикла. А так же пусть обозначает сумму сложностей <tex>incident\_faceS1</tex> в каждом и <tex>half-edge</tex> будут обновлены на <tex>fS2</tex>, а k является сложностью наложения.
====Воссоздание <tex>faces</tex>====
После того, как все сделано, осталось вычислить информацию о <tex>faces</tex> в <tex>O(S1, S2)</tex>. Точнее, мы должны создать <tex>face</tex> record для каждого <tex>face</tex> е в <tex>O(S1, S2)</tex>, мы должны сделать <tex>outer\_component</tex> (<tex>e</tex>) указывают на <tex>half-edges</tex> на внешней границе <tex>F</tex>, и мы должны сделать список <tex>inner\_components</tex> (<tex>F</tex>) из указателей на <tex>half-edges</tex> на связанных областях пробелов внутри <tex>f</tex>. Кроме того, мы должны установить <tex>incident\_face</tex> () поля времени <tex>half-edges</tex> на границе <tex>F</tex> так, что они указывают на лицевые записи <tex>F</tex>. Наконец, каждый из новых <tex>faces</tex> должны быть помечены именами <tex>faces</tex> в старых подграфах, которые содержат его. Рассмотрим два <tex>half-edges</tex> цикла, свойственных <tex>v</tex>. Т.к. мы знаем, что incident <tex>face</tex> лежит слева, мы можем вычислить угол который эти два <tex>half-edges</tex> образуют внутри <tex>face</tex>. Если этот угол f меньше, чем 180◦ то циклом является внешняя граница, и в противном случае это граница дыры. Это свойство имеет место для левой вершины цикла, но не обязательно для других вершин этого цикла.
{{Лемма
|about=
К предыдущему вопросу
|statement=
Каждая компонента графа отвечает за множество циклов инцидентных одному <tex>face</tex>.
|proof= Рассмотрим цикл <tex>C</tex>, который ограничивает дыру в <tex>face</tex> <tex>f</tex>. Поскольку <tex>f</tex> локально лежит левее самой левой вершины из <tex>C</tex>, то <tex>C</tex> должен быть соединен с другим циклом, который тоже ограничивает <tex>f</tex>. отсюда следует, что циклы есть компонента связности в графе, описывающая один и тот-же <tex>face</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>f</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> в doublyconnected edge list может быть установлена в <tex>О(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>:</tex>
==Q&A==*'''Копирование РСДС'''Просто объединение 1. Копируем <tex>S_1</tex> и <tex>S_2</tex> в одну структуру. Как сделать его правильным - это уже следующие пунктыграф <tex>D</tex>.
*'''Как из 2. Находим все пересечения ребер сделать новую компоненту РСДС'''См рисунокиз <tex>S_1</tex> с ребрами из <tex>S_2</tex> с помощью заметающей прямой.
*'''Сколько будет faces?'''Столько же2.1 Когда находим точки пересечения, сколько то обновляем <tex>outer\_boudariesD</tex> + 1, то есть строим из него [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]].
*'''Как узнать, что данный цикл 3. Теперь <tex>D</tex> это внешняя граница для face или же это дыра в нем?''' Мы знаем, что face находится слева от half-edge. Поэтому возьмем самую левую точку нормальный [[ППЛГ и РСДС (в случаем, если их несколько, то самую нижнююPSLG и DCEL) и возьмем входящий и выходящий из нее half-edge. В случае угла между ними менее 180 градусов: определение, то это внешняя границапостроение РСДС множества прямых|РСДС]], иначе это дыра. Это действует только для самой левой точки из циклано без информации о <tex>face</tex>'ах.
*'''Что за граф и для чего он нужен? (Граф 4. Находим boundary cycles в <tex>D</tex> из 5 пункта)'''См рисунок. Из него мы сможем понять, какие циклы принадлежат одному и тому же faceТо есть обновляем этот граф. Например, Пока только добавляя в рисунке мы видим, что C2, C3 и C6 являются циклами одного face. Из предыдущего вопроса мы понимаем, что C2 есть внешняя границанего ребра (<tex>half-edge</tex>'ы соответственно).
Подробнее:5. Создаем граф <tex>G</tex> (о нем ниже), в котором узлы будут отвечать за boundary cycles и в котором ребра будут соединять только те узлы, один из которых будет являться границей дыры (<tex>hole</tex>, это внутренний цикл <tex>face</tex>'a), а другой будет находиться слева от самой левой точки первого. (В случае, если это самая внешняя граница, то для нее пусть будет мнимая гигантская граница, с которой мы ее и соединим).
{{Лемма|about=К предыдущему вопросу|statement=Каждая компонента графа отвечает за множество циклов инцидентных одному face5.|proof= Рассмотрим цикл <tex>C</tex>, который ограничивает дыру в face <tex>f</tex>. Поскольку <tex>f</tex> локально лежит левее самой левой вершины из <tex>C</tex>, то <tex>C</tex> должен быть соединен с другим циклом, который тоже ограничивает <tex>f</tex>. отсюда следует, что циклы есть компонента связности в графе, описывающая один и тот-же face1. Для того, что бы закончить доказательство, покажем, что каждый цикл ограничивающий дыру в <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>f</tex>. Противоречие.}}каждой компоненты графа:
*'''Как построить этот граф?'''Вспоминаем, что во время работы алгоритма заметающей прямойПусть <tex>C</tex> будет уникальная наружная граница цикла в компоненте, мы смотрели на отрезки левее от event pointа <tex>f</tex> будет означать face ограниченный этим циклом. Из этого получаем, что информацию Создадим face для постройки нашего графа мы получаем <tex>f</tex>. Запишем <tex>outer\_component</tex> в какой-нибудь <tex>half-edge</tex> из этого алгоритма<tex>C</tex>. То есть для начала мы делаем узел для каждого циклаИ создадим список <tex>inner\_components</tex>, затем для создания ребер мы смотри состоящий из указателей на самые левые вершины циклов. Если есть какой-нибудь <tex>half-edge слева от вершины, то создаем ребро между циклами (</tex> из каждого цикла. А так же пусть <tex>incident\_face</tex> в котором вершина и в котором каждом <tex>half-edge)</tex> будут обновлены на <tex>f</tex>.
== Литература и источники ==
* Вычислительная геометрия. Алгоритмы и приложения, де Берг Марк и другие. Глава 2.3
