113
правок
Изменения
Нет описания правки
|}
==== Время работы ====
Большинство шагов алгоритма работают константное время. Определение соседних полуребер с <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>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"
| [[Файл:PSLG_graph_w.png|400px|center|thumb|Построение графа <tex>G</tex>]]
