Изменения

== Постановка задачи Введение ==Определим пересечение [[Файл: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>. Отдельно рассмотрим преобразования вершин, полуребер и граней.

[[Файл: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>

{| 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>Qh_4</tex> при обходе по часовой стрелке и исходящем из <tex>v</tex>. Полуребро <tex>Th_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> — количество точек пересечения. рисунок ниже):

=== Грани ===[[Файл: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>, но может не выполняться для остальных вершин.

Рассмотрим один из случаевДля определения того, остальные обрабатываются аналогично. Пусть ребро <tex>e</tex> из <tex>S_1</tex> пересекает вершину <tex>v</tex> из <tex>S_2</tex>. Ребро <tex>e</tex> заменяем двумя ребрами <tex>e'</tex> и <tex>e''</tex>. Два полуребракакие границы принадлежат одной грани, соответствующих построим вспомогательный граф <tex>eG</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>{| cellpadding="3"| [[Файл: свяжем его с первым полуребром, видимым из <tex>h_4</tex> при обходе по часовой стрелке и исходящем из <tex>v</tex>. Полуребро <tex>h_4</tex> должно быть связано с первым полуребром, идущим в <tex>v</tex>, при обходе против часовой стрелкиPSLG_graph_w. Аналогично обработаем png|400px|center|thumb|Построение графа <tex>e''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> ограничивают одну и ту же грань.Покажем, что каждый цикл, ограничивающий дырку грани <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>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>e'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>e''v</tex> происходит за линейное время от степени . То есть для каждой вершиныиз <tex>S_1</tex> мы должны знать, какая грань из <tex>S_2</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>nk</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

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