113
правок
Изменения
→Грани
[[Файл: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>, в котором каждая граница является вершиной. Также добавим вершину для мнимой границы внешней грани. Между двумя циклами (вершинами графа) существует ребро тогда и только тогда, когда один цикл является границей дырки, а второй цикл является ближайшим слева к самой левой вершине первого цикла. Если левее самой левой вершины цикла нет полуребер, то соединим этот цикл с мнимой границей внешней грани ППЛГ.
