|
|
| Строка 1: |
Строка 1: |
| − | [[Файл:PSLG.png|400px|thumb|left|Input <tex>\Rightarrow</tex> Output]]
| |
| − | [[Файл:PSLG1.png|400px|thumb|right|Создание новой компоненты]]
| |
| − | [[Файл:PSLG2.png|400px|thumb|right|Создание новой компоненты]]
| |
| − | [[Файл:PSLG3.png|400px|thumb|left|Граф для поиска face]]
| |
| | | | |
| − | ==Постановка задачи==
| |
| − | Даны два [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|ППЛГ]], требуется построить их объединение в виде [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]. При этом создав новые <tex>face</tex> и обновив старые.
| |
| − |
| |
| − | ===Формально===
| |
| − |
| |
| − | Определим объединение двух 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>S2</tex> соответственно, что <tex>f</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>.
| |
| − |
| |
| − | ===Алгоритм===
| |
| − |
| |
| − | ====Первоначальное слияние====
| |
| − |
| |
| − | Для начала посмотрим, как можно больше информации от 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, соответствующие краям, которые не пересекают ребра из другого графа.
| |
| − |
| |
| − |
| |
| − | ====Объединения графов====
| |
| − | Во-первых, скопировать doubly connected edge lists <tex>S1</tex> и <tex>S2</tex> в один новый <tex>DCEL</tex>. Новый <tex>DCEL</tex> не является допустимым <tex>DCEL</tex>, т.к. он еще не представляет собой плоский подграф. Это задача алгоритма заметающей прямой: он должен трансформировать <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(S1, S2)</tex>. Мы держим перекрестные указатели между ребер в структуре состояния <tex>T</tex> и половина текущих записей в <tex>D</tex>, которые соответствуют им. Таким образом мы можем получить доступ к части <tex>D</tex>, которая должна быть изменена, когда мы сталкиваемся с точкой пересечения.
| |
| − |
| |
| − | В другом случае, мы поддерживаем то, что в любое время в течение развертки, часть выше линии развертки наложения будет считаться правильной. Теперь что мы должны делать, когда мы достигнем точки событий. Прежде всего, мы обновляем <tex>T</tex> и <tex>Q</tex>, как и в алгоритме заметающей прямой. Если событие включает в себя только ребра из одного из двух подграфов, это все, точка событие является вершиной, которые могут быть использованы повторно. Если событие включает края с двух подграфов, мы должны сделать локальные изменения в <tex>D</tex> -- связать doubly connected edge list двух оригинальных подграфов в точке пересечения.
| |
| − |
| |
| − | Рассмотри, когда edge <tex>e</tex> из <tex>S1</tex> проходит через вершину <tex>V</tex> <tex>S2</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>. Точно также и для <tex>e''</tex>.
| |
| − |
| |
| − | ====Время работы объединения====
| |
| − |
| |
| − | Большинство из шагов в приведенном выше описании принимать только константное время. Есть случаи на которые потребуется дополнительное время, О(M), где Mчисло ребер, точки событий. Это означает, что обновление <tex>D</tex> не увеличивает время работы алгоритма заметащей прямой асимптотически. Любое пересечение, которое мы находим является вершиной наложения. Из этого следует, что вершина record и <tex>half-edge</tex> record doubly connected edge list для <tex>O(S1, S2)</tex> можно вычислить за <tex>O(n \ * \ \log n + k \ *\ \log n)</tex> время, где <tex>n</tex> обозначает сумму сложностей <tex>S1</tex> и <tex>S2</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>
| |
| − |
| |
| − | 1. Копируем <tex>S_1</tex> и <tex>S_2</tex> в граф <tex>D</tex>.
| |
| − |
| |
| − | 2. Находим все пересечения ребер из <tex>S_1</tex> с ребрами из <tex>S_2</tex> с помощью заметающей прямой.
| |
| − |
| |
| − | 2.1 Когда находим точки пересечения, то обновляем <tex>D</tex>, то есть строим из него [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]].
| |
| − |
| |
| − | 3. Теперь <tex>D</tex> это нормальный [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]], но без информации о <tex>face</tex>'ах.
| |
| − |
| |
| − | 4. Находим boundary cycles в <tex>D</tex>. То есть обновляем этот граф. Пока только добавляя в него ребра (<tex>half-edge</tex>'ы соответственно).
| |
| − |
| |
| − | 5. Создаем граф <tex>G</tex> (о нем ниже), в котором узлы будут отвечать за boundary cycles и в котором ребра будут соединять только те узлы, один из которых будет являться границей дыры (<tex>hole</tex>, это внутренний цикл <tex>face</tex>'a), а другой будет находиться слева от самой левой точки первого. (В случае, если это самая внешняя граница, то для нее пусть будет мнимая гигантская граница, с которой мы ее и соединим).
| |
| − |
| |
| − | 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>, состоящий из указателей на какой-нибудь <tex>half-edge</tex> из каждого цикла. А так же пусть <tex>incident\_face</tex> в каждом <tex>half-edge</tex> будут обновлены на <tex>f</tex>.
| |
| − |
| |
| − |
| |
| − | == Литература и источники ==
| |
| − | * Вычислительная геометрия. Алгоритмы и приложения, де Берг Марк и другие. Глава 2.3
| |
