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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 33 промежуточные версии 4 участников)
Строка 1: Строка 1:
== Постановка задачи ==
+
== Введение ==
Определим пересечение двух [[ППЛГ и РСДС (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>. Необходимо построить [[ППЛГ и РСДС (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>, содержащие ее.
+
[[Файл:PSLG_overlaying_w.png|400px|right|thumb|Пример работы алгоритма пересечения ППЛГ]]
 
+
Пересечением двух [[ППЛГ и РСДС (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>.  
<картинка>
+
{{Задача
 +
|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>, содержащие ее.
 +
}}
  
 
== Алгоритм ==
 
== Алгоритм ==
Для начала, скопируем ППЛГ <tex>S_1</tex> и <tex>S_2</tex> в новый РСДС. Далее необходимо преобразовать полученный РСДС, чтобы он соответствовал <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>. Напомним, что алгоритм поддерживает очередь событий <tex>Q</tex> и текущий статус <tex>T</tex> заметающей прямой. Также будем поддерживать ссылки между ребрами статуса и соответствующими полуребрами из РСДС. Поддерживаемый инвариант: над заметающей прямой корректный РСДС.
+
[[Файл: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> (как в алгоритме пересечения отрезков). Если оба ребра события принадлежат одному ППЛГ, переходим к следующему событию. В противном случае, необходимо модифицировать РСДС. Возможны следующие варианты событий (см. рисунок ниже):
 
  
<картинка>
+
Обработка точки события происходит следующим образом: сначала обновляем <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>
  
Рассмотрим один из случаев, остальные обрабатываются аналогично. Пусть ребро <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_overlay_cases_w.png|600px|center|thumb|Варианты пересечений ребер <tex>e_1</tex> и <tex>e_2</tex>. Слева направо случаи (a) - (e).]]
<картинка>
+
|}
  
 +
Рассмотрим один из случаев, остальные обрабатываются аналогично. Пусть ребро <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> — сложность пересечения.
+
Большинство шагов алгоритма работают константное время. Определение соседних полуребер с <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> — количество точек пересечения.
  
 
=== Грани ===
 
=== Грани ===
Необходимо получить информацию о гранях итогового РСДС: ссылка на полуребро внешней границы, список ссылкок на полуребра дырок внутри грани, ссылка на грани из <tex>S_1</tex> и <tex>S_2</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>v</tex> (нижнюю из левых, в случае равенства). Напомним, что полуребра ориентированы так, что инцидентная им грань лежит левее полуребра. С учетом этого, оценим угол внутри грани между полуребрами, инцидентными <tex>v</tex>. Если угол меньше <tex>180^\circ</tex>, то цикл является внешней границей, в противном случае – дыркой. Данное свойство выполняется для вершины <tex>v</tex>, но может не выполняться для остальных вершин.
+
Необходимо получить информацию о гранях итогового РСДС: ссылка на полуребро внешней границы, список ссылок на полуребра дырок внутри грани, ссылка на грани из <tex>S_1</tex> и <tex>S_2</tex>, содержащие новую грань. Также необходимо для полуребер установить ссылки на инцидентную грань.
 
+
У каждой грани существует уникальная внешняя граница, поэтому количество граней будет на единицу больше, чем количество внешних границ (дополнительная граница ограничивает весь ППЛГ). Таким образом, каждой грани можно ставить в соответствие внешнюю границу данной грани (кроме внешней грани ППЛГ, для нее мы введем мнимую внешнюю границу). Следовательно, необходимо обойти все внешние границы ППЛГ и создать грань для каждой границы. Для того, чтобы определить, является цикл внешней границей или дыркой, рассмотрим самую левую вершину цикла <tex>v</tex> (определяется обходом по циклу). Напомним, что полуребра ориентированы так, что инцидентная им грань лежит левее полуребра. С учетом этого, оценим угол внутри грани между полуребрами, инцидентными <tex>v</tex>. Если угол меньше <tex>180^\circ</tex>, то цикл является внешней границей грани, в противном случае – лежит внутри грани. Данное свойство выполняется для вершины <tex>v</tex>, но может не выполняться для остальных вершин.
<картинка>
 
  
Для определения того, какие границы принадлежат одной грани, постоим вспомогательный граф <tex>G</tex>, в котором каждая граница является вершиной. Также добавим вершину для мнимой границы внешней грани. Между двумя циклами (вершинами графа) существует ребро тогда и только тогда, когда один цикл является границей дырки, а второй цикл является ближайшим слева к самой левой вершине первого цикла. Если левее самой левой вершины цикла нет полуребер, то соединим этот цикл с мнимой границей внешней грани ППЛГ.
+
Для определения того, какие границы принадлежат одной грани, построим вспомогательный граф <tex>G</tex>, в котором каждая граница является вершиной. Также добавим вершину для мнимой границы внешней грани. Между двумя вершинами графа, соответствующим двум циклам РСДС, существует ребро тогда и только тогда, когда один цикл является границей дырки, а второй цикл является ближайшим слева к самой левой вершине первого цикла. Если левее самой левой вершины цикла нет полуребер, то соединим этот цикл с мнимой границей внешней грани ППЛГ.
 +
{| cellpadding="3"
 +
| [[Файл:PSLG_graph_w.png|400px|center|thumb|Построение графа <tex>G</tex>]]
 +
|}
  
<картинка>
 
  
 
{{Лемма
 
{{Лемма
 
|statement=Каждой компоненте связности графа <tex>G</tex> соответствует множество циклов, инцидентных только одной грани.
 
|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> ограничивают одну и ту же грань.
 
|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>f. Противоречие с определением <tex>C</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>.  
 
}}
 
}}
  
 
==== Построение графа <tex>G</tex>====
 
==== Построение графа <tex>G</tex>====
Напомним, что в алгоритме заметающей прямой для пересечения отрезков мы искали ближайший отрезок, находящийся левее точки события. Эта информация необходима для построения графа <tex>G</tex>. Сначала создадим вершину для каждой границы. Далее необходимо построить ребра в графе, для этого найдем левую вершину каждой дырки и определим, какое ребро лежит слева от данной вершины. Для эффективности будем для каждого полуребра хранить ссылку на вершину графа, содержащую это полуребро. Таким образом, информация о гранях может быть восстановлена за время <tex>O(n + k)</tex>, после алгоритма заметающей прямой.
+
Напомним, что в алгоритме заметающей прямой для пересечения отрезков мы искали ближайший отрезок, находящийся левее точки события. Эта информация необходима для построения графа <tex>G</tex>. Сначала создадим вершину для каждой границы. Далее необходимо построить ребра в графе, для этого найдем левую вершину каждой дырки и определим, какое ребро лежит слева от данной вершины. Для эффективности будем для каждого полуребра хранить ссылку на вершину графа, содержащую это полуребро. Таким образом, информация о гранях может быть восстановлена за время <tex>O(n + k)</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> содержит данную вершину, и наоборот. Это также делается заметающей прямой.
 
Необходимо для каждой грани РСДС определить, какие грани из <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> содержит данную вершину, и наоборот. Это также делается заметающей прямой.
  
<tex></tex>
+
=== Итог ===
 +
Вход: два ППЛГ <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>.
 +
 
 +
== Общее время работы ==
 +
{{Теорема
 +
|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>.
 +
|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>.
 +
}}
 +
 
 +
== См.также ==
 +
*[[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]]
 +
*[[Пересечение множества отрезков]]
 +
 
 +
== Источники информации ==
 +
* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 33-39
 +
 
 +
[[Категория: Вычислительная геометрия]]
 +
[[Категория: ППЛГ и РСДС]]

Текущая версия на 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