Изменения

== Постановка задачи ==

Определим пересечение двух [[ППЛГ и РСДС (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>, содержащие ее.

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

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

{| cellpadding="3"

|}

{| cellpadding="3"

|[[Файл:PSLG_edge_vertex_w.png|x180px|center|thumb|Пересечение вершины <tex>v</tex> и ребра <tex>e</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>, в котором каждая граница является вершиной. Также добавим вершину для мнимой границы внешней грани. Между двумя циклами (вершинами графа) существует ребро тогда и только тогда, когда один цикл является границей дырки, а второй цикл является ближайшим слева к самой левой вершине первого цикла. Если левее самой левой вершины цикла нет полуребер, то соединим этот цикл с мнимой границей внешней грани ППЛГ.

{| cellpadding="3"

|}