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