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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Вершины и полуребра)
 
(не показано 39 промежуточных версий 5 участников)
Строка 1: Строка 1:
[[Файл:PSLG.png|400px|thumb|left|Input <tex>\Rightarrow</tex> Output]]
+
== Введение ==
[[Файл: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>, содержащие ее.
==Постановка задачи==
+
}}
Даны два [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|ППЛГ]], требуется построить их объединение в виде [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]. При этом создав новые <tex>face</tex> и обновив старые.
 
 
 
===Формально===
 
 
 
Определим объединение двух pslg <tex>S1</tex> и <tex>S2</tex>, чтобы получился граф <tex>O(S1, S2)</tex>, такой, что существует <tex>face</tex> f в <tex>O(S1, S2)</tex>, тогда и только тогда есть <tex>face</tex> f1 и f2 в <tex>S1</tex> и <tex>S2</tex> соответственно, что <tex>f</tex> является максимально связанным подмножеством <tex>f1 \cap f2</tex>. Требуется чтобы каждый <tex>face</tex> в <tex>O(S1, S2)</tex> был отмечен с помощью label of the <tex>faces</tex> в <tex>S1</tex> и <tex>S2</tex>, который содержит их. Таким образом мы получаем доступ к информации хранящейся на этих <tex>faces</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> заметающей прямой. Также будем поддерживать ссылки между ребрами статуса и соответствующими полуребрами из РСДС. Поддерживаемый инвариант: в любой момент времени РСДС над заметающей прямой корректен.
  
Для начала посмотрим, как можно больше информации от doubly connected edge lists для <tex>S1</tex> и <tex>S2</tex> мы можем повторно использовать в doubly connected edge lists для <tex>O(S1, S2)</tex>. Рассмотрим сеть ребер и вершин S1. Эта сеть разделена на кусочки краями <tex>S2</tex>. Эти кусочки в большинстве своем могут использоваться повторно, все, за исключением тех, которые отделены краями <tex>S2</tex>. Такие нужно обновлять. Если ориентация <tex>half-edge</tex> изменится, нам придется менять информацию в этих записях. Половинки ребра ориентированы таким образом, что <tex>face</tex>, которым они связаны лежит слева; форма <tex>face</tex> может изменяться в наложении, но он будет оставаться в той же стороне <tex>half-edge</tex>. Следовательно, мы можем повторно использовать <tex>half-edge</tex> records, соответствующие краям, которые не пересекают ребра из другого графа.
+
Обработка точки события происходит следующим образом: сначала обновляем <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>h_4</tex> при обходе по часовой стрелке и исходящем из <tex>v</tex>. Полуребро <tex>h_4</tex> должно быть связано с первым полуребром, идущим в <tex>v</tex>, при обходе против часовой стрелки. Аналогично обработаем <tex>e''</tex>.
Во-первых, скопировать doubly­ connected edge lists <tex>S1</tex> и <tex>S2</tex> в один новый <tex>DCEL</tex>. Новый <tex>DCEL</tex> не является допустимым <tex>DCEL</tex>, т.к. он еще не представляет собой плоский подграф. Это задача алгоритма заметающей прямой: он должен трансформировать <tex>DCEL</tex> в допустимый <tex>DCEL</tex> для <tex>O(S1, S2)</tex> путем вычисления пересечения между двумя сетями ребер, и связывая воедино соответствующие части из двух <tex>DCEL</tex>. Мы применяем этот алгоритм на множестве сегментов, что является объединением множеств ребер двух подграфов <tex>S1</tex> и <tex>S2</tex>. Напомним, что алгоритм поддерживается двумя структурами данных: очереди событий <tex>Q</tex>, в котором хранятся точки событий, и структура состояния <tex>T</tex>, которой является бинарное дерево храненящее сегменты, пересекающие линии развертки, расположенные слева направо. Мы теперь также должны поддерживать <tex>DCEL</tex> <tex>D</tex>. Первоначально <tex>D</tex> содержит копию <tex>DCEL</tex> для <tex>S1</tex> и <tex>DCEL</tex> для <tex>S2</tex>. В плоскости развертки преобразуем <tex>D</tex> к правильному <tex>DCEL</tex> для <tex>O(S1, S2)</tex>. Мы держим перекрестные указатели между ребер в структуре состояния <tex>T</tex> и половина текущих записей в <tex>D</tex>, которые соответствуют им. Таким образом мы можем получить доступ к части <tex>D</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>T</tex> и <tex>Q</tex>, как и в алгоритме заметающей прямой. Если событие включает в себя только ребра из одного из двух подграфов, это все, точка событие является вершиной, которые могут быть использованы повторно. Если событие включает края с двух подграфов, мы должны сделать локальные изменения в <tex>D</tex> -- связать doubly­ connected edge list двух оригинальных подграфов в точке пересечения.
+
=== Грани ===
 +
[[Файл: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>, но может не выполняться для остальных вершин.
  
Рассмотри один из 2 возможных случаев, а именно, когда edge <tex>e</tex> из <tex>S1</tex> проходит через вершину <tex>V</tex> <tex>S2</tex>, (см. Рисунок) edge <tex>e</tex> должно быть заменено двумя edges обозначим <tex>e'</tex> и <tex>e''</tex>. В <tex>DCEL</tex>, два <tex>half-edge</tex> для е должны превратиться в четыре. Мы создаем два новых <tex>half-edge</tex>, с <tex>V</tex> в нуле. Два существующих <tex>half-edge</tex> для е содержат конечные точки <tex>e</tex>, как их происхождения. Тогда мы объединяем попарно существующие <tex>half-edges</tex> с новыми <tex>half-edges</tex>, устанавливая их указатели twin'ов. Так <tex>e'</tex> представлен одним новым и одним существующим частично edge, и то же самое для <tex>e''</tex>. Теперь мы должны установить ряд <tex>Prev</tex> и <tex>Next</tex>. <tex>Next</tex> двух новых <tex>half-edges</tex> являются копией <tex>Next</tex> старого <tex>half-edge</tex>, не имеющего пары. В <tex>half-edges</tex>, в которые эти указатели точки должны обновлять свои <tex>Prev</tex> и установливать его на новых <tex>half-edges</tex>. Далее мы должны установить <tex>Next</tex> и <tex>Prev</tex> четырех <tex>half-edges</tex> представляющих <tex>e'</tex> и <tex>e''</tex>, и из четырех <tex>half-edges</tex> инциденого <tex>S2</tex> <tex>v</tex>. Мы размещаем эти четыре <tex>half-edges</tex> от <tex>S2</tex>, проверяя, где <tex>e'</tex> и <tex>e''</tex> должны быть в циклическом порядке вершин вокруг вершины <tex>v</tex>. Есть четыре пары <tex>half-edges</tex>, которые связанны между собой <tex>Next</tex> с одним и <tex>Prev</tex> с другим. <tex>e'</tex> должен быть привязан к первому <tex>half-edge</tex> по часовой стрелке с началом в <tex>v.</tex> <tex>half-edge</tex> для <tex>e'</tex> с началом в <tex>v</tex> должен быть связан с первым против часовой стрелки <tex>half-edge</tex> с окончанием в <tex>v</tex>. Точно также и для <tex>e''</tex>.
+
Для определения того, какие границы принадлежат одной грани, построим вспомогательный граф <tex>G</tex>, в котором каждая граница является вершиной. Также добавим вершину для мнимой границы внешней грани. Между двумя вершинами графа, соответствующим двум циклам РСДС, существует ребро тогда и только тогда, когда один цикл является границей дырки, а второй цикл является ближайшим слева к самой левой вершине первого цикла. Если левее самой левой вершины цикла нет полуребер, то соединим этот цикл с мнимой границей внешней грани ППЛГ.
 +
{| cellpadding="3"
 +
| [[Файл:PSLG_graph_w.png|400px|center|thumb|Построение графа <tex>G</tex>]]
 +
|}
  
====Время работы объединения====
 
 
Большинство из шагов в приведенном выше описании принимать только константное время. Есть случаи на которые потребуется дополнительное время, О(M), где M­число ребер, точки событий. Это означает, что обновление <tex>D</tex> не увеличивает время работы алгоритма заметащей прямой асимптотически. Любое пересечение, которое мы находим является вершиной наложения. Из этого следует, что вершина record и <tex>half-edge</tex> record doubly­ connected edge list для <tex>O(S1, S2)</tex> можно вычислить за <tex>O(n\ *\ log n\ +\ k\ *\ log\ n)</tex> время, где <tex>n</tex> обозначает сумму сложностей <tex>S1</tex> и <tex>S2</tex>, а k является сложностью наложения.
 
 
====Воссоздание <tex>faces</tex>====
 
После того, как все сделано, осталось вычислить информацию о <tex>faces</tex> в <tex>O(S1, S2)</tex>. Точнее, мы должны создать <tex>face</tex> record для каждого <tex>face</tex> е в <tex>O(S1, S2)</tex>, мы должны сделать <tex>outer\_component</tex> (<tex>e</tex>) указывают на <tex>half-edges</tex> на внешней границе <tex>F</tex>, и мы должны сделать список <tex>inner\_components</tex> (<tex>F</tex>) из указателей на <tex>half-edges</tex> на связанных областях пробелов внутри <tex>f</tex>. Кроме того, мы должны установить <tex>incident\_face</tex> () поля времени <tex>half-edges</tex> на границе <tex>F</tex> так, что они указывают на лицевые записи <tex>F</tex>. Наконец, каждый из новых <tex>faces</tex> должны быть помечены именами <tex>faces</tex> в старых подграфах, которые содержат его. Рассмотрим два <tex>half-edges</tex> цикла, свойственных <tex>v</tex>. Т.к. мы знаем, что incident <tex>face</tex> лежит слева, мы можем вычислить угол который эти два <tex>half-edges</tex> образуют внутри <tex>face</tex>. Если этот угол f меньше, чем 180◦ то циклом является внешняя граница, и в противном случае это граница дыры. Это свойство имеет место для левой вершины цикла, но не обязательно для других вершин этого цикла.
 
  
 
{{Лемма
 
{{Лемма
|about=
+
|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> ограничивают одну и ту же грань.
|statement=
+
Покажем, что каждый цикл, ограничивающий дырку грани <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>face</tex>.
 
|proof= Рассмотрим цикл <tex>C</tex>, который ограничивает дыру в <tex>face</tex> <tex>f</tex>. Поскольку <tex>f</tex> локально лежит левее самой левой вершины из <tex>C</tex>, то <tex>C</tex> должен быть соединен с другим циклом, который тоже ограничивает <tex>f</tex>. отсюда следует, что циклы есть компонента связности в графе, описывающая один и тот-же <tex>face</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>f</tex>. Противоречие.
 
 
}}
 
}}
  
Напомним, что в алгоритме развертки плоскости для отрезка пересечения мы всегда искали сегменты сразу слева от точки событий. (Они должны были быть проверены на пересечении с крайнего левого края через точку событий.) Таким образом, информация, при помощи которой мы должны построить <tex>G</tex> определяется в плоскости развертки. Таким образом, чтобы построить <tex>G</tex>, мы сначала делаем узел для каждого цикла. Чтобы найти дуги <tex>G</tex>, рассмотрим левую вершину <tex>V</tex> для каждого цикла, ограничивающую отверстие. Если <tex>half-edge</tex> сразу же выходит из <tex>V</tex>, то мы добавляем дугу между двумя узлами в <tex>G</tex>, представляющих цикл, содержащий  е и цикл у которого <tex>V</tex> является самой левой вершиной. Чтобы найти эти узлы в <tex>G</tex> мы должны указатели от каждого <tex>half-edge</tex> записать в узел <tex>G</tex>, представляющего цикл этот. Так информация o <tex>face</tex> в doubly­connected edge list может быть установлена в <tex>О(n\ +\ k)</tex> времени, после плоскости развертки. Каждая грань <tex>e</tex> в наложении должна быть помечена с именами <tex>face</tex> в старых графах, которые содержали его. Чтобы найти эти <tex>face</tex>, надо рассмотреть произвольную вершину <tex>V</tex> в <tex>F</tex>. Если <tex>v</tex> является пересечением <tex>e1</tex> от <tex>S1</tex> и <tex>е2</tex> от <tex>S2</tex>, то мы можем решить, какие <tex>face</tex> из <tex>S1</tex> и <tex>S2</tex> содержат <tex>F</tex>, глядя на <tex>incident\_face</tex> указатель соответствующих <tex>half-edges</tex> соответствующих <tex>e1</tex> и <tex>e2</tex>. Если <tex>v</tex> не пересечение, но вершина, скажем, S1, то мы знаем только <tex>face</tex> S1, содержащей <tex>f</tex>. Чтобы найти <tex>face</tex> <tex>S2</tex> , содержащий <tex>F</tex>, мы должны определить <tex>face</tex> <tex>S2</tex>, которое содержит <tex>v</tex>. Другими словами, если бы мы знали для каждой вершины <tex>S1</tex>, в котором <tex>face</tex> <tex>S2</tex> находился, и наоборот, то мы могли бы обозначить <tex>face</tex> <tex>O(S1, S2)</tex> правильно.
+
==== Построение графа <tex>G</tex>====
 +
Напомним, что в алгоритме заметающей прямой для пересечения отрезков мы искали ближайший отрезок, находящийся левее точки события. Эта информация необходима для построения графа <tex>G</tex>. Сначала создадим вершину для каждой границы. Далее необходимо построить ребра в графе, для этого найдем левую вершину каждой дырки и определим, какое ребро лежит слева от данной вершины. Для эффективности будем для каждого полуребра хранить ссылку на вершину графа, содержащую это полуребро. Таким образом, информация о гранях может быть восстановлена за время <tex>O(n + k)</tex>, после алгоритма заметающей прямой. Также заметим, что информацию о структуре графа можно хранить в записях граней.
  
==Итог==
+
==== Маркировка граней ====
'''MapOverlay (<tex>S_1</tex>, <tex>S_2</tex>)''' <tex>:</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> содержит данную вершину, и наоборот. Это также делается заметающей прямой.
  
1. Копируем <tex>S_1</tex> и <tex>S_2</tex> в граф <tex>D</tex>.
+
=== Итог ===
 +
Вход: два ППЛГ <tex>S_1</tex> и <tex>S_2</tex>, представленные в виде РСДС.
  
2. Находим все пересечения ребер из <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>.
  
2.1 Когда находим точки пересечения, то обновляем <tex>D</tex>, то есть строим из него [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]].
+
== Общее время работы ==
 
+
{{Теорема
3. Теперь <tex>D</tex> это нормальный [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]], но без информации о <tex>face</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>.
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>C</tex> будет уникальная наружная граница цикла в компоненте, а <tex>f</tex> будет означать face ограниченный этим циклом. Создадим face для <tex>f</tex>. Запишем <tex>outer\_component</tex> в какой-нибудь <tex>half-edge</tex> из <tex>C</tex>. И создадим список <tex>inner\_components</tex>, состоящий из указателей на какой-нибудь <tex>half-edge</tex> из каждого цикла. А так же пусть <tex>incident\_face</tex> в каждом <tex>half-edge</tex> будут обновлены на <tex>f</tex>.
+
== См.также ==
 +
*[[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]]
 +
*[[Пересечение множества отрезков]]
  
 +
== Источники информации ==
 +
* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 33-39
  
== Литература и источники ==
+
[[Категория: Вычислительная геометрия]]
* Вычислительная геометрия. Алгоритмы и приложения, де Берг Марк и другие. Глава 2.3
+
[[Категория: ППЛГ и РСДС]]

Текущая версия на 14:39, 19 мая 2015

Введение[править]

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

Пересечением двух ППЛГ является ППЛГ, получающийся наложением двух исходных ППЛГ с созданием вершин в точках пересечения ребер. Определим пересечение двух ППЛГ [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