Пересечение многоугольников (PSLG overlaying) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показаны 52 промежуточные версии 8 участников)
Строка 1: Строка 1:
[[Файл:PSLG.png|400px|thumb|left|Ну как то так. Очевидно же]]
+
== Введение ==
[[Файл:PSLG1.png|400px|thumb|right|Создание новой компоненты]]
+
[[Файл:PSLG_overlaying_w.png|400px|right|thumb|Пример работы алгоритма пересечения ППЛГ]]
[[Файл:PSLG2.png|400px|thumb|right|Создание новой компоненты]]
+
Пересечением двух [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|ППЛГ]] является ППЛГ, получающийся наложением двух исходных ППЛГ с созданием вершин в точках пересечения ребер. Определим пересечение двух ППЛГ <tex>S_1</tex> и <tex>S_2</tex> как ППЛГ <tex>O(S_1, S_2)</tex>, такой, что в нем существует грань <tex>f</tex> тогда и только тогда, когда существуют грани <tex>f_1</tex> в <tex>S_1</tex> и <tex>f_2</tex> в <tex>S_2</tex> такие, что <tex>f</tex> является наибольшим связным подмножеством <tex>f_1 \cap f_2</tex>. Иначе говоря, пересечение двух ППЛГ — это разбиение плоскости с помощью ребер из <tex>S_1</tex> и <tex>S_2</tex>.
[[Файл:PSLG3.png|400px|thumb|left|Граф для поиска face]]
+
{{Задача
 +
|definition = Необходимо построить [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]] для <tex>O(S_1, S_2)</tex>, имея РСДС для <tex>S_1</tex> и <tex>S_2</tex>. Кроме того, для каждой грани из <tex>O(S_1, S_2)</tex> будем хранить ссылки на грани из <tex>S_1</tex> и <tex>S_2</tex>, содержащие ее.
 +
}}
  
==Алгоритм==
+
== Алгоритм ==
'''MapOverlay (<tex>S_1</tex>, <tex>S_2</tex>)'''
+
Для начала скопируем ППЛГ <tex>S_1</tex> и <tex>S_2</tex> в новый РСДС. Далее необходимо преобразовать полученный РСДС, чтобы он соответствовал <tex>O(S_1, S_2)</tex>. Отдельно рассмотрим преобразования вершин, полуребер и граней.
  
Дано: 2 ППЛГ в виде РСДС.
+
=== Вершины и полуребра ===
 +
[[Файл:PSLG_sweep_w.png|220px|right|thumb|Алгоритм заметающей прямой]]
 +
Алгоритм базируется на [[Пересечение множества отрезков|заметающей прямой]], определяющей пересечения отрезков. Запускаем алгоритм на множестве отрезков, представляющих собой ребра из <tex>S_1</tex> и <tex>S_2</tex>. Напомним, что алгоритм поддерживает очередь событий <tex>Q</tex> и текущий статус <tex>T</tex> заметающей прямой. Также будем поддерживать ссылки между ребрами статуса и соответствующими полуребрами из РСДС. Поддерживаемый инвариант: в любой момент времени РСДС над заметающей прямой корректен.
  
Вывод: пересечение этих ППЛГ в виде РСДС.
+
Обработка точки события происходит следующим образом: сначала обновляем <tex>Q</tex> и <tex>T</tex> (как в алгоритме пересечения отрезков). Если оба ребра события принадлежат одному ППЛГ, переходим к следующему событию. В противном случае, необходимо модифицировать РСДС. Возможны следующие варианты пересечений (см. рисунок ниже):
Алгоритм:
+
<ol type="a">
 +
<li>Вершина ребра <tex>e_2</tex> проходит через ребро <tex>e_1</tex>, разбивая его на два новых ребра.</li>
 +
<li>Ребро <tex>e_1</tex> пересекает ребро <tex>e_2</tex>. Образуется четыре новых ребра.</li>
 +
<li>Ребра <tex>e_1</tex> и <tex>e_2</tex> пересекаются в общей вершине.</li>
 +
<li>Вершина ребра <tex>e_1</tex> проходит через ребро <tex>e_2</tex>, разбивая его на два новых ребра.</li>
 +
<li>Ребра <tex>e_1</tex> и <tex>e_2</tex> имеют общий отрезок. Образуется новое ребро.</li>
 +
</ol>
  
1. Копируем <tex>S_1</tex> и <tex>S_2</tex> в РСДС <tex>D</tex>.
+
{| cellpadding="3"
 +
|[[Файл:PSLG_overlay_cases_w.png|600px|center|thumb|Варианты пересечений ребер <tex>e_1</tex> и <tex>e_2</tex>. Слева направо случаи (a) - (e).]]
 +
|}
  
2. Находим все пересечения ребер из <tex>S_1</tex> с ребрами из <tex>S_2</tex> с помощью заметающей прямой.
+
Рассмотрим один из случаев, остальные обрабатываются аналогично. Пусть ребро <tex>e</tex> из <tex>S_1</tex> проходит через вершину <tex>v</tex> из <tex>S_2</tex>. Ребро <tex>e</tex> заменяем двумя ребрами <tex>e'</tex> и <tex>e''</tex>. Два полуребра, соответствующих <tex>e</tex>, заменяются четырьмя полуребрами: два существующих полуребра будут исходить из концов <tex>e</tex>, а два новых полуребра — из <tex>v</tex> (см. рисунок). Устанавливаем ссылки на близнецов для ребер <tex>e'</tex> и <tex>e''</tex>. Обновим ссылки на следующие полуребра для <tex>h_1</tex> и <tex>h_4</tex>, пусть это будут <tex>h_5</tex> и <tex>h_6</tex>, соответственно. Не забудем установить полуребра <tex>h_1</tex> и <tex>h_4</tex> в качестве предыдущих полуребер у <tex>h_5</tex> и <tex>h_6</tex>. Теперь обновим ссылки на полуребра, инцидентные вершине <tex>v</tex>. Для этого сначала при помощи порядка обхода определим, между какими полуребрами <tex>S_2</tex> находится <tex>e</tex>. Рассмотрим полуребро <tex>h_3</tex>: свяжем его с первым полуребром, видимым из <tex>h_4</tex> при обходе по часовой стрелке и исходящем из <tex>v</tex>. Полуребро <tex>h_4</tex> должно быть связано с первым полуребром, идущим в <tex>v</tex>, при обходе против часовой стрелки. Аналогично обработаем <tex>e''</tex>.
 +
{| cellpadding="3"
 +
|[[Файл:PSLG_edge_vertex_w.png|x180px|center|thumb|Пересечение вершины <tex>v</tex> и ребра <tex>e</tex>]]
 +
|[[Файл:PSLG_edge_vertex2_w.png|x180px|center|thumb|Модификация полуребер]]
 +
|}
 +
==== Время работы ====
 +
Большинство шагов алгоритма работают константное время. Определение соседних полуребер с <tex>e'</tex> и <tex>e''</tex> происходит за линейное время от степени вершины. Следовательно, обновление РСДС не увеличивает время работы алгоритма пересечения отрезков, поэтому сведения о вершинах и полуребрах для итогового РСДС могут быть вычислены за время <tex>O(n \log{n} + k \log{n})</tex>, где <tex>n</tex> — сумма сложностей <tex>S_1</tex> и <tex>S_2</tex>, <tex>k</tex> — количество точек пересечения.
  
2.1 Когда находим точки пересечения, то обновляем <tex>D</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>S_1</tex> и <tex>S_2</tex>, содержащие новую грань. Также необходимо для полуребер установить ссылки на инцидентную грань.
 +
У каждой грани существует уникальная внешняя граница, поэтому количество граней будет на единицу больше, чем количество внешних границ (дополнительная граница ограничивает весь ППЛГ). Таким образом, каждой грани можно ставить в соответствие внешнюю границу данной грани (кроме внешней грани ППЛГ, для нее мы введем мнимую внешнюю границу). Следовательно, необходимо обойти все внешние границы ППЛГ и создать грань для каждой границы. Для того, чтобы определить, является цикл внешней границей или дыркой, рассмотрим самую левую вершину цикла <tex>v</tex> (определяется обходом по циклу). Напомним, что полуребра ориентированы так, что инцидентная им грань лежит левее полуребра. С учетом этого, оценим угол внутри грани между полуребрами, инцидентными <tex>v</tex>. Если угол меньше <tex>180^\circ</tex>, то цикл является внешней границей грани, в противном случае – лежит внутри грани. Данное свойство выполняется для вершины <tex>v</tex>, но может не выполняться для остальных вершин.
  
3. Теперь <tex>D</tex> это нормальный РСДС, но без информации о faces.
+
Для определения того, какие границы принадлежат одной грани, построим вспомогательный граф <tex>G</tex>, в котором каждая граница является вершиной. Также добавим вершину для мнимой границы внешней грани. Между двумя вершинами графа, соответствующим двум циклам РСДС, существует ребро тогда и только тогда, когда один цикл является границей дырки, а второй цикл является ближайшим слева к самой левой вершине первого цикла. Если левее самой левой вершины цикла нет полуребер, то соединим этот цикл с мнимой границей внешней грани ППЛГ.
 +
{| cellpadding="3"
 +
| [[Файл:PSLG_graph_w.png|400px|center|thumb|Построение графа <tex>G</tex>]]
 +
|}
  
4. Находим boundary cycles в <tex>D</tex>.
 
  
5. Создаем граф <tex>G</tex>, в котором узлы будут отвечать за boundary cycles и в котором ребра будут соединять только те узлы, один из которых будет являться границей дыры, а другой будет находиться слева от самой левой точки первого. (В случае, если это самая внешняя граница, то для нее пусть будет мнимая гигантская граница, с которой мы ее и соединим).
+
{{Лемма
 +
|statement=Каждой компоненте связности графа <tex>G</tex> соответствует множество циклов, инцидентных только одной грани.
 +
|proof=Рассмотрим цикл <tex>C</tex>, ограничивающий дырку в грани <tex>f</tex>. Грань <tex>f</tex> лежит левее самой левой вершины <tex>C</tex>, поэтому <tex>C</tex> должен быть связан с другим циклом грани <tex>f</tex>. Следовательно, циклы одной компоненты связности графа <tex>G</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>C</tex>.  
 +
}}
  
6. Для каждой компоненты графа:
+
==== Построение графа <tex>G</tex>====
 +
Напомним, что в алгоритме заметающей прямой для пересечения отрезков мы искали ближайший отрезок, находящийся левее точки события. Эта информация необходима для построения графа <tex>G</tex>. Сначала создадим вершину для каждой границы. Далее необходимо построить ребра в графе, для этого найдем левую вершину каждой дырки и определим, какое ребро лежит слева от данной вершины. Для эффективности будем для каждого полуребра хранить ссылку на вершину графа, содержащую это полуребро. Таким образом, информация о гранях может быть восстановлена за время <tex>O(n + k)</tex>, после алгоритма заметающей прямой. Также заметим, что информацию о структуре графа можно хранить в записях граней.
  
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>.
+
==== Маркировка граней ====
 +
Необходимо для каждой грани РСДС определить, какие грани из <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> содержит данную вершину, и наоборот. Это также делается заметающей прямой.
  
==Q&A==
+
=== Итог ===
*'''Копирование РСДС'''
+
Вход: два ППЛГ <tex>S_1</tex> и <tex>S_2</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>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>.
  
*'''Сколько будет faces?'''
+
== Общее время работы ==
Столько же, сколько outer boudaries + 1.
+
{{Теорема
 
+
|statement=Пусть <tex>S_1</tex> имеет сложность <tex>n_1</tex>, <tex>S_2</tex> имеет сложность <tex>n_2</tex>, <tex>n = n_1 + n_2</tex>. Пересечение <tex>S_1</tex> и <tex>S_2</tex> может быть построено за время <tex>O(n \log{n} + k \log{n})</tex>, где <tex>k</tex> – количество точек пересечения <tex>S_1</tex> и <tex>S_2</tex>.
*'''Как узнать, что данный цикл это внешняя граница для face или же это дыра в нем?'''
+
|proof=Копирование двух РСДС в один занимает <tex>O(n)</tex> времени, заметающая прямая работает <tex>O(n \log{n} + k \log{n})</tex> времени по лемме. Создание граней работает линейное время от сложности <tex>O(S_1, S_2)</tex>. Маркировка граней РСДС работает за <tex>O(n \log{n} + k \log{n})</tex>.
Мы знаем, что face находится слева от half-edge. Поэтому возьмем самую левую точку (в случаем, если их несколько, то самую нижнюю) и возьмем входящий и выходящий из нее half-edge. В случае угла между ними менее 180 градусов, то это внешняя граница, иначе это дыра. Это действует только для самой левой точки из цикла.
 
 
 
*'''Че за граф такой пацанский?'''
 
См рисунок. Из него мы сможем понять, какие циклы принадлежат одному и тому же face. Например, в рисунке мы видим, что C2, C3 и C6 являются циклами одного face. Из предыдущего вопроса мы понимаем, что C2 есть внешняя граница.
 
 
 
{{Лемма
 
|statement=
 
Каждая компонента графа отвечает за множество циклов инцидентных одному face.
 
|proof= Рассмотрим цикл <tex>C</tex>, который ограничивает дыру в face <tex>f</tex>. Поскольку <tex>f</tex> локально лежит левее самой левой вершины из <tex>C</tex>, то <tex>C</tex> должен быть соединен с другим циклом, который тоже ограничивает <tex>f</tex>. отсюда следует, что циклы есть компонента связности в графе, описывающая один и тот-же face. Для того, что бы закончить доказательство, покажем, что каждый цикл ограничивающий дыру в <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>. Противоречие.
 
 
}}
 
}}
  
*'''Как построить этот граф?'''
+
== См.также ==
Вспоминаем, что во время работы алгоритма заметающей прямой, мы смотрели на отрезки левее от event point. Из этого получаем, что информацию для постройки нашего графа мы получаем из этого алгоритма. То есть для начала мы делаем узел для каждого цикла, затем для создания ребер мы смотри на самые левые вершины циклов. Если есть half-edge слева от вершины, то создаем ребро между циклами (в котором вершина и в котором half-edge).
+
*[[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]]
 +
*[[Пересечение множества отрезков]]
  
*'''Еще что-то?'''
+
== Источники информации ==
Да. названия face должны быть такими-же как в старых РСДС.
+
* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 33-39
(Как это делать. Много букв и много не нужного, но пусть будет. Легко перевести)
 
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
+
[[Категория: ППЛГ и РСДС]]

Текущая версия на 19:23, 4 сентября 2022

Введение

Пример работы алгоритма пересечения ППЛГ

Пересечением двух ППЛГ является ППЛГ, получающийся наложением двух исходных ППЛГ с созданием вершин в точках пересечения ребер. Определим пересечение двух ППЛГ [math]S_1[/math] и [math]S_2[/math] как ППЛГ [math]O(S_1, S_2)[/math], такой, что в нем существует грань [math]f[/math] тогда и только тогда, когда существуют грани [math]f_1[/math] в [math]S_1[/math] и [math]f_2[/math] в [math]S_2[/math] такие, что [math]f[/math] является наибольшим связным подмножеством [math]f_1 \cap f_2[/math]. Иначе говоря, пересечение двух ППЛГ — это разбиение плоскости с помощью ребер из [math]S_1[/math] и [math]S_2[/math].

Задача:
Необходимо построить РСДС для [math]O(S_1, S_2)[/math], имея РСДС для [math]S_1[/math] и [math]S_2[/math]. Кроме того, для каждой грани из [math]O(S_1, S_2)[/math] будем хранить ссылки на грани из [math]S_1[/math] и [math]S_2[/math], содержащие ее.


Алгоритм

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

Вершины и полуребра

Алгоритм заметающей прямой

Алгоритм базируется на заметающей прямой, определяющей пересечения отрезков. Запускаем алгоритм на множестве отрезков, представляющих собой ребра из [math]S_1[/math] и [math]S_2[/math]. Напомним, что алгоритм поддерживает очередь событий [math]Q[/math] и текущий статус [math]T[/math] заметающей прямой. Также будем поддерживать ссылки между ребрами статуса и соответствующими полуребрами из РСДС. Поддерживаемый инвариант: в любой момент времени РСДС над заметающей прямой корректен.

Обработка точки события происходит следующим образом: сначала обновляем [math]Q[/math] и [math]T[/math] (как в алгоритме пересечения отрезков). Если оба ребра события принадлежат одному ППЛГ, переходим к следующему событию. В противном случае, необходимо модифицировать РСДС. Возможны следующие варианты пересечений (см. рисунок ниже):

  1. Вершина ребра [math]e_2[/math] проходит через ребро [math]e_1[/math], разбивая его на два новых ребра.
  2. Ребро [math]e_1[/math] пересекает ребро [math]e_2[/math]. Образуется четыре новых ребра.
  3. Ребра [math]e_1[/math] и [math]e_2[/math] пересекаются в общей вершине.
  4. Вершина ребра [math]e_1[/math] проходит через ребро [math]e_2[/math], разбивая его на два новых ребра.
  5. Ребра [math]e_1[/math] и [math]e_2[/math] имеют общий отрезок. Образуется новое ребро.
Варианты пересечений ребер [math]e_1[/math] и [math]e_2[/math]. Слева направо случаи (a) - (e).

Рассмотрим один из случаев, остальные обрабатываются аналогично. Пусть ребро [math]e[/math] из [math]S_1[/math] проходит через вершину [math]v[/math] из [math]S_2[/math]. Ребро [math]e[/math] заменяем двумя ребрами [math]e'[/math] и [math]e''[/math]. Два полуребра, соответствующих [math]e[/math], заменяются четырьмя полуребрами: два существующих полуребра будут исходить из концов [math]e[/math], а два новых полуребра — из [math]v[/math] (см. рисунок). Устанавливаем ссылки на близнецов для ребер [math]e'[/math] и [math]e''[/math]. Обновим ссылки на следующие полуребра для [math]h_1[/math] и [math]h_4[/math], пусть это будут [math]h_5[/math] и [math]h_6[/math], соответственно. Не забудем установить полуребра [math]h_1[/math] и [math]h_4[/math] в качестве предыдущих полуребер у [math]h_5[/math] и [math]h_6[/math]. Теперь обновим ссылки на полуребра, инцидентные вершине [math]v[/math]. Для этого сначала при помощи порядка обхода определим, между какими полуребрами [math]S_2[/math] находится [math]e[/math]. Рассмотрим полуребро [math]h_3[/math]: свяжем его с первым полуребром, видимым из [math]h_4[/math] при обходе по часовой стрелке и исходящем из [math]v[/math]. Полуребро [math]h_4[/math] должно быть связано с первым полуребром, идущим в [math]v[/math], при обходе против часовой стрелки. Аналогично обработаем [math]e''[/math].

Пересечение вершины [math]v[/math] и ребра [math]e[/math]
Модификация полуребер

Время работы

Большинство шагов алгоритма работают константное время. Определение соседних полуребер с [math]e'[/math] и [math]e''[/math] происходит за линейное время от степени вершины. Следовательно, обновление РСДС не увеличивает время работы алгоритма пересечения отрезков, поэтому сведения о вершинах и полуребрах для итогового РСДС могут быть вычислены за время [math]O(n \log{n} + k \log{n})[/math], где [math]n[/math] — сумма сложностей [math]S_1[/math] и [math]S_2[/math], [math]k[/math] — количество точек пересечения.

Грани

Поиск внешних границ и дырок. Вершины [math]v[/math] и [math]u[/math] – левые вершины циклов. Для полуребер [math]h_1[/math] и [math]h_2[/math] грань [math]f[/math] является внутренней, для полуребер [math]h_3[/math] и [math]h_4[/math] – внешней.

Необходимо получить информацию о гранях итогового РСДС: ссылка на полуребро внешней границы, список ссылок на полуребра дырок внутри грани, ссылка на грани из [math]S_1[/math] и [math]S_2[/math], содержащие новую грань. Также необходимо для полуребер установить ссылки на инцидентную грань. У каждой грани существует уникальная внешняя граница, поэтому количество граней будет на единицу больше, чем количество внешних границ (дополнительная граница ограничивает весь ППЛГ). Таким образом, каждой грани можно ставить в соответствие внешнюю границу данной грани (кроме внешней грани ППЛГ, для нее мы введем мнимую внешнюю границу). Следовательно, необходимо обойти все внешние границы ППЛГ и создать грань для каждой границы. Для того, чтобы определить, является цикл внешней границей или дыркой, рассмотрим самую левую вершину цикла [math]v[/math] (определяется обходом по циклу). Напомним, что полуребра ориентированы так, что инцидентная им грань лежит левее полуребра. С учетом этого, оценим угол внутри грани между полуребрами, инцидентными [math]v[/math]. Если угол меньше [math]180^\circ[/math], то цикл является внешней границей грани, в противном случае – лежит внутри грани. Данное свойство выполняется для вершины [math]v[/math], но может не выполняться для остальных вершин.

Для определения того, какие границы принадлежат одной грани, построим вспомогательный граф [math]G[/math], в котором каждая граница является вершиной. Также добавим вершину для мнимой границы внешней грани. Между двумя вершинами графа, соответствующим двум циклам РСДС, существует ребро тогда и только тогда, когда один цикл является границей дырки, а второй цикл является ближайшим слева к самой левой вершине первого цикла. Если левее самой левой вершины цикла нет полуребер, то соединим этот цикл с мнимой границей внешней грани ППЛГ.

Построение графа [math]G[/math]


Лемма:
Каждой компоненте связности графа [math]G[/math] соответствует множество циклов, инцидентных только одной грани.
Доказательство:
[math]\triangleright[/math]

Рассмотрим цикл [math]C[/math], ограничивающий дырку в грани [math]f[/math]. Грань [math]f[/math] лежит левее самой левой вершины [math]C[/math], поэтому [math]C[/math] должен быть связан с другим циклом грани [math]f[/math]. Следовательно, циклы одной компоненты связности графа [math]G[/math] ограничивают одну и ту же грань.

Покажем, что каждый цикл, ограничивающий дырку грани [math]f[/math], находится в одной компоненте связности с внешней границей грани [math]f[/math]. Предположим, что существует цикл, для которого это не выполняется. Пусть [math]C[/math] – самый левый такой цикл, причем его левая вершина также самая левая. По определению, существует ребро между [math]C[/math] и циклом [math]C'[/math], который лежит левее [math]C[/math]. Следовательно, [math]C'[/math] лежит в одной компоненте связности с [math]C[/math], причем [math]C'[/math] не является внешней границей [math]f[/math]. Получается, что [math]C'[/math] лежит левее [math]C[/math], что противоречит определению [math]C[/math].
[math]\triangleleft[/math]

Построение графа [math]G[/math]

Напомним, что в алгоритме заметающей прямой для пересечения отрезков мы искали ближайший отрезок, находящийся левее точки события. Эта информация необходима для построения графа [math]G[/math]. Сначала создадим вершину для каждой границы. Далее необходимо построить ребра в графе, для этого найдем левую вершину каждой дырки и определим, какое ребро лежит слева от данной вершины. Для эффективности будем для каждого полуребра хранить ссылку на вершину графа, содержащую это полуребро. Таким образом, информация о гранях может быть восстановлена за время [math]O(n + k)[/math], после алгоритма заметающей прямой. Также заметим, что информацию о структуре графа можно хранить в записях граней.

Маркировка граней

Необходимо для каждой грани РСДС определить, какие грани из [math]S_1[/math] и [math]S_2[/math] содержат ее. Рассмотрим вершину [math]v[/math] грани [math]f[/math]. Если [math]v[/math] является пересечением ребра [math]e_1[/math] из [math]S_1[/math] и ребра [math]e_2[/math] из [math]S_2[/math], то по указателям на инцидентные грани можно определить, какие грани содержат данные ребра. Если [math]v[/math] является вершиной [math]S_1[/math], то мы можем определить только грань из [math]S_1[/math], содержащую [math]v[/math]. Необходимо научиться определять грань из [math]S_2[/math], содержащую [math]v[/math]. То есть для каждой вершины из [math]S_1[/math] мы должны знать, какая грань из [math]S_2[/math] содержит данную вершину, и наоборот. Это также делается заметающей прямой.

Итог

Вход: два ППЛГ [math]S_1[/math] и [math]S_2[/math], представленные в виде РСДС.

Выход: пересечение [math]S_1[/math] и [math]S_2[/math], представленное в виде РСДС [math]D[/math].

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

Общее время работы

Теорема:
Пусть [math]S_1[/math] имеет сложность [math]n_1[/math], [math]S_2[/math] имеет сложность [math]n_2[/math], [math]n = n_1 + n_2[/math]. Пересечение [math]S_1[/math] и [math]S_2[/math] может быть построено за время [math]O(n \log{n} + k \log{n})[/math], где [math]k[/math] – количество точек пересечения [math]S_1[/math] и [math]S_2[/math].
Доказательство:
[math]\triangleright[/math]
Копирование двух РСДС в один занимает [math]O(n)[/math] времени, заметающая прямая работает [math]O(n \log{n} + k \log{n})[/math] времени по лемме. Создание граней работает линейное время от сложности [math]O(S_1, S_2)[/math]. Маркировка граней РСДС работает за [math]O(n \log{n} + k \log{n})[/math].
[math]\triangleleft[/math]

См.также

Источники информации

  • de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 33-39