[[Файл: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> и обновив старые.
==Алгоритм==
'''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>'ах.
Дано: 2 ППЛГ 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>S_1</tex> и <tex>S_2</tex> в РСДС <tex>D</tex>.Для каждой компоненты графа:
2Пусть <tex>C</tex> будет уникальная наружная граница цикла в компоненте, а <tex>f</tex> будет означать face ограниченный этим циклом. Создадим face для <tex>f</tex>. Находим все пересечения ребер Запишем <tex>outer\_component</tex> в какой-нибудь <tex>half-edge</tex> из <tex>S_1C</tex> с ребрами . И создадим список <tex>inner\_components</tex>, состоящий из указателей на какой-нибудь <tex>half-edge</tex> из каждого цикла. А так же пусть <tex>incident\_face</tex> в каждом <tex>half-edge</tex> будут обновлены на <tex>S_2f</tex> с помощью заметающей прямой.
2.1 Когда находим точки пересечения, то обновляем <tex>D</tex>.
3. Теперь <tex>D</tex> это нормальный РСДС, но без информации о faces.
4. Находим boundary cycles в <tex>D</tex>.
5. Создаем граф <tex>G</tex>, в котором узлы будут отвечать за boundary cycles и в котором ребра будут соединять только те узлы, один из которых будет являться границей дыры, а другой будет находиться слева от самой левой точки первого. (В случае, если это самая внешняя граница, то для нее пусть будет мнимая гигантская граница, с которой мы ее и соединим).
6. Для каждой компоненты графа:
7. Пусть <tex>C</tex> будет уникальная наружная граница цикла в компоненте, а <tex>f</tex> будет означать face ограниченный этим циклом. Создадим face для <tex>f</tex>. Запишем outer_component в какой-нибудь half-edge из <tex>C</tex>. И создадим список inner_components, состоящий из указателей на какой-нибудь half-edge из каждого цикла. А так же пусть incident_face в каждом half-edge будут обновлены на <tex>f</tex>.
==Q&A==
*'''Сколько будет faces?'''
Столько же, сколько <tex>outer boudaries \_boudaries</tex> + 1.
*'''Как узнать, что данный цикл это внешняя граница для face или же это дыра в нем?'''
Мы знаем, что face находится слева от half-edge. Поэтому возьмем самую левую точку (в случаем, если их несколько, то самую нижнюю) и возьмем входящий и выходящий из нее half-edge. В случае угла между ними менее 180 градусов, то это внешняя граница, иначе это дыра. Это действует только для самой левой точки из цикла.
*'''Че Что за граф такой пацанскийи для чего он нужен?(Граф <tex>D</tex> из 5 пункта)'''
См рисунок. Из него мы сможем понять, какие циклы принадлежат одному и тому же face. Например, в рисунке мы видим, что C2, C3 и C6 являются циклами одного face. Из предыдущего вопроса мы понимаем, что C2 есть внешняя граница.
Подробнее:
{{Лемма
Вспоминаем, что во время работы алгоритма заметающей прямой, мы смотрели на отрезки левее от event point. Из этого получаем, что информацию для постройки нашего графа мы получаем из этого алгоритма. То есть для начала мы делаем узел для каждого цикла, затем для создания ребер мы смотри на самые левые вершины циклов. Если есть half-edge слева от вершины, то создаем ребро между циклами (в котором вершина и в котором half-edge).
*'''Еще что-то?'''
Да. названия face должны быть такими-же как в старых РСДС.
(Как это делать. Много букв и много не нужного, но пусть будет. Легко перевести)
One thing remains: each face f in the overlay must be labeled with the names of the faces in the old subdivisions that contained it. To find these faces, consider an arbitrary vertex v of f . If v is the intersection of an edge e 1 from S 1 and an edge e 2 from S 2 then we can decide which faces of S 1 and S 2 contain f by looking at the IncidentFace() pointer of the appropriate half-edges corresponding to e 1 and e 2 . If v is not an intersection but a vertex of, say, S 1 , then we only know the face of S 1 containing f . To find the face of S 2 containing f , we have to do some more work: we have to determine the face of S 2 that contains v. In other words, if we knew for each vertex of S 1 in which face of S 2 it lay, and vice versa, then we could label the faces of O(S 1 , S 2 ) correctly. How can we compute this information? The solution is to apply the paradigm that has been introduced in this chapter, plane sweep, once more. However, we won’t explain this final step here. It is a good exercise to test your understanding of the plane sweep approach to design the algorithm yourself. (In fact, it is not necessary to compute this information in a separate plane sweep. It can also be done in the sweep that computes the intersections.)
== Литература и источники ==
* Вычислительная геометрия. Алгоритмы и приложения, де Берг Марк и другие. Глава 2.3
