Изменения

Напомним, что в алгоритме развертки плоскости для отрезка пересечения мы всегда искали сегменты сразу слева от точки событий. (Они должны были быть проверены на пересечении с крайнего левого края через точку событий.) Таким образом, информация, при помощи которой мы должны построить <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> правильно.

==Итог==