Изменения

== Введение ==[[Файл:PSLGPSLG_overlaying_w.png|400px|right|thumb|leftПример работы алгоритма пересечения ППЛГ]]Пересечением двух [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|Input ППЛГ]] является ППЛГ, получающийся наложением двух исходных ППЛГ с созданием вершин в точках пересечения ребер. Определим пересечение двух ППЛГ <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 \Rightarrowcap f_2</tex>. Иначе говоря, пересечение двух ППЛГ — это разбиение плоскости с помощью ребер из <tex>S_1</tex> Output]]и <tex>S_2</tex>. {{Задача[[Файл:PSLG1.png|400px|thumb|right|Создание новой компоненты]]definition = Необходимо построить [[ФайлППЛГ и РСДС (PSLG и DCEL):PSLG2.png|400px|thumbопределение, построение РСДС множества прямых|right|Создание новой компонентыРСДС]][[Файл:PSLG3для <tex>O(S_1, S_2)</tex>, имея РСДС для <tex>S_1</tex> и <tex>S_2</tex>.png|400px|thumb|left|Граф Кроме того, для поиска face]]каждой грани из <tex>O(S_1, S_2)</tex> будем хранить ссылки на грани из <tex>S_1</tex> и <tex>S_2</tex>, содержащие ее.}}

==Постановка задачиАлгоритм ==Даны два [[Для начала скопируем ППЛГ <tex>S_1</tex> и <tex>S_2</tex> в новый РСДС (PSLG и DCEL): определение, построение . Далее необходимо преобразовать полученный РСДС множества прямых|ППЛГ]], требуется построить их объединение в виде [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]. При этом создав новые чтобы он соответствовал <tex>faceO(S_1, S_2)</tex> . Отдельно рассмотрим преобразования вершин, полуребер и обновив старыеграней.

==Алгоритм= Вершины и полуребра ==='''MapOverlay ([[Файл:PSLG_sweep_w.png|220px|right|thumb|Алгоритм заметающей прямой]]Алгоритм базируется на [[Пересечение множества отрезков|заметающей прямой]], определяющей пересечения отрезков. Запускаем алгоритм на множестве отрезков, представляющих собой ребра из <tex>S_1</tex>и <tex>S_2</tex>. Напомним, что алгоритм поддерживает очередь событий <tex>S_2Q</tex>)''' и текущий статус <tex>:T</tex>заметающей прямой. Также будем поддерживать ссылки между ребрами статуса и соответствующими полуребрами из РСДС. Поддерживаемый инвариант: в любой момент времени РСДС над заметающей прямой корректен.

1Обработка точки события происходит следующим образом: сначала обновляем <tex>Q</tex> и <tex>T</tex> (как в алгоритме пересечения отрезков). Если оба ребра события принадлежат одному ППЛГ, переходим к следующему событию. Копируем В противном случае, необходимо модифицировать РСДС. Возможны следующие варианты пересечений (см. рисунок ниже):<ol type="a"><li>Вершина ребра <tex>S_1e_2</tex> проходит через ребро <tex>e_1</tex>, разбивая его на два новых ребра.</li><li>Ребро <tex>e_1</tex> пересекает ребро <tex>e_2</tex>. Образуется четыре новых ребра.</li><li>Ребра <tex>e_1</tex> и <tex>S_2e_2</tex> пересекаются в граф общей вершине.</li><li>Вершина ребра <tex>e_1</tex> проходит через ребро <tex>e_2</tex>, разбивая его на два новых ребра.</li><li>Ребра <tex>e_1</tex>Dи <tex>e_2</tex>имеют общий отрезок.Образуется новое ребро.</li></ol>

2{| cellpadding="3"|[[Файл:PSLG_overlay_cases_w. Находим все пересечения png|600px|center|thumb|Варианты пересечений ребер из <tex>S_1e_1</tex> с ребрами из и <tex>S_2e_2</tex> с помощью заметающей прямой.Слева направо случаи (a) - (e).]]|}

2Рассмотрим один из случаев, остальные обрабатываются аналогично. Пусть ребро <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>.1 Когда находим точки пересеченияДля этого сначала при помощи порядка обхода определим, то обновляем между какими полуребрами <tex>S_2</tex> находится <tex>De</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(PSLG n \log{n} + k \log{n})</tex>, где <tex>n</tex> — сумма сложностей <tex>S_1</tex> и DCEL): определение<tex>S_2</tex>, построение РСДС множества прямых|РСДС]]<tex>k</tex> — количество точек пересечения.

3=== Грани ===[[Файл: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>Dh_3</tex> это нормальный [[ППЛГ и <tex>h_4</tex> – внешней.]]Необходимо получить информацию о гранях итогового РСДС : ссылка на полуребро внешней границы, список ссылок на полуребра дырок внутри грани, ссылка на грани из <tex>S_1</tex> и <tex>S_2</tex>, содержащие новую грань. Также необходимо для полуребер установить ссылки на инцидентную грань.У каждой грани существует уникальная внешняя граница, поэтому количество граней будет на единицу больше, чем количество внешних границ (PSLG дополнительная граница ограничивает весь ППЛГ). Таким образом, каждой грани можно ставить в соответствие внешнюю границу данной грани (кроме внешней грани ППЛГ, для нее мы введем мнимую внешнюю границу). Следовательно, необходимо обойти все внешние границы ППЛГ и DCELсоздать грань для каждой границы. Для того, чтобы определить, является цикл внешней границей или дыркой, рассмотрим самую левую вершину цикла <tex>v</tex> (определяется обходом по циклу): определение. Напомним, что полуребра ориентированы так, что инцидентная им грань лежит левее полуребра. С учетом этого, оценим угол внутри грани между полуребрами, инцидентными <tex>v</tex>. Если угол меньше <tex>180^\circ</tex>, построение РСДС множества прямых|РСДС]]то цикл является внешней границей грани, но без информации о в противном случае – лежит внутри грани. Данное свойство выполняется для вершины <tex>facev</tex>'ах, но может не выполняться для остальных вершин.

4. Находим boundary cycles в Для определения того, какие границы принадлежат одной грани, построим вспомогательный граф <tex>DG</tex>, в котором каждая граница является вершиной. Также добавим вершину для мнимой границы внешней грани. Между двумя вершинами графа, соответствующим двум циклам РСДС, существует ребро тогда и только тогда, когда один цикл является границей дырки, а второй цикл является ближайшим слева к самой левой вершине первого цикла. То есть обновляем Если левее самой левой вершины цикла нет полуребер, то соединим этот графцикл с мнимой границей внешней грани ППЛГ.{| cellpadding="3"| [[Файл:PSLG_graph_w. Пока только добавляя в него ребра (png|400px|center|thumb|Построение графа <tex>half-edgeG</tex>'ы соответственно).]]|}

5{{Лемма|statement=Каждой компоненте связности графа <tex>G</tex> соответствует множество циклов, инцидентных только одной грани.1|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>CG</tex> будет уникальная наружная граница цикла ====Напомним, что в компонентеалгоритме заметающей прямой для пересечения отрезков мы искали ближайший отрезок, а находящийся левее точки события. Эта информация необходима для построения графа <tex>fG</tex> будет означать face ограниченный этим циклом. Создадим face Сначала создадим вершину для <tex>f</tex>каждой границы. Запишем <tex>outer\_component</tex> Далее необходимо построить ребра в какой-нибудь <tex>half-edge</tex> из <tex>C</tex>графе, для этого найдем левую вершину каждой дырки и определим, какое ребро лежит слева от данной вершины. Для эффективности будем для каждого полуребра хранить ссылку на вершину графа, содержащую это полуребро. И создадим список Таким образом, информация о гранях может быть восстановлена за время <tex>inner\_componentsO(n + k)</tex>, состоящий из указателей на какой-нибудь <tex>half-edge</tex> из каждого циклапосле алгоритма заметающей прямой. А так же пусть <tex>incident\_face</tex> Также заметим, что информацию о структуре графа можно хранить в каждом <tex>half-edge</tex> будут обновлены на <tex>f</tex>записях граней.

   ==Q&AОбщее время работы ==*'''Копирование РСДС'''Просто объединение в одну структуру. Как сделать его правильным - это уже следующие пункты. *'''Как из пересечения ребер сделать новую компоненту РСДС'''См рисунок. *'''Сколько будет faces?'''Столько же, сколько <tex>outer\_boudaries</tex> + 1. *'''Как узнать, что данный цикл это внешняя граница для face или же это дыра в нем?''' Мы знаем, что face находится слева от half-edge. Поэтому возьмем самую левую точку (в случаем, если их несколько, то самую нижнюю) и возьмем входящий и выходящий из нее half-edge. В случае угла между ними менее 180 градусов, то это внешняя граница, иначе это дыра. Это действует только для самой левой точки из цикла. *'''Что за граф и для чего он нужен? (Граф <tex>D</tex> из 5 пункта)'''См рисунок. Из него мы сможем понять, какие циклы принадлежат одному и тому же face. Например, в рисунке мы видим, что C2, C3 и C6 являются циклами одного face. Из предыдущего вопроса мы понимаем, что C2 есть внешняя граница. Подробнее: {{Лемма|about=К предыдущему вопросуТеорема|statement=Каждая компонента графа отвечает за множество циклов инцидентных одному face.|proof= Рассмотрим цикл Пусть <tex>CS_1</tex>, который ограничивает дыру в face имеет сложность <tex>fn_1</tex>. Поскольку , <tex>fS_2</tex> локально лежит левее самой левой вершины из имеет сложность <tex>Cn_2</tex>, то <tex>Cn = n_1 + n_2</tex> должен быть соединен с другим циклом, который тоже ограничивает . Пересечение <tex>fS_1</tex>. отсюда следует, что циклы есть компонента связности в графе, описывающая один и тот-же face. Для того, что бы закончить доказательство, покажем, что каждый цикл ограничивающий дыру в <tex>fS_2</tex> есть в той же компоненте связности, что и внешняя граница может быть построено за время <tex>fO(n \log{n} + k \log{n})</tex>. Предположим, что есть цикл, для которого это не так. Пусть где <tex>Ck</tex> — самый левый такой цикл, то есть тот, чья самая левая вершина самая левая (шляпа). По определению есть ребро между – количество точек пересечения <tex>CS_1</tex> и неким <tex>C'S_2</tex>, который лежит слева от самой левой вершины .|proof=Копирование двух РСДС в один занимает <tex>CO(n)</tex>. Следовательно времени, заметающая прямая работает <tex>CO(n \log{n} + k \log{n})</tex> в той же компоненте связности, что и времени по лемме. Создание граней работает линейное время от сложности <tex>C'O(S_1, S_2)</tex>, который не в той же компоненте, что внешняя граница . Маркировка граней РСДС работает за <tex>fO(n \log{n} + k \log{n})</tex>. Противоречие.

== См.также ==*'''Как построить этот граф?'''Вспоминаем, что во время работы алгоритма заметающей прямой, мы смотрели на отрезки левее от event point. Из этого получаем, что информацию для постройки нашего графа мы получаем из этого алгоритма. То есть для начала мы делаем узел для каждого цикла, затем для создания ребер мы смотри на самые левые вершины циклов. Если есть half-edge слева от вершины, то создаем ребро между циклами [[ППЛГ и РСДС (в котором вершина PSLG и в котором half-edgeDCEL).: определение, построение РСДС множества прямых]]*[[Пересечение множества отрезков]]

== Литература и источники ==* [[Категория: Вычислительная геометрия. Алгоритмы и приложения, де Берг Марк ]][[Категория: ППЛГ и другие. Глава 2.3РСДС]]