Изменения
Нет описания правки
Необходимо для каждой грани РСДС определить, какие грани из <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>S_1</tex>и <tex>S_2</tex>, представленные в виде РСДС. Выход: пересечение <tex>S_1</tex> и <tex>S_2</tex>, представленное в виде РСДС <tex>D</tex>.# Скопируем <tex>S_1</tex> и <tex>S_2</tex> в новый РСДС <tex>D</tex>.# Найдем пересечения ребер из <tex>S_1</tex> и <tex>S_2</tex> с помощью заметающей прямой. При обработке события будем обновлять <tex>D</tex>, если событие затрагивает <tex>S_1</tex> и <tex>S_2</tex>. Также для вершины события сохраним информацию о ближайшем полуребре слева.# Найдем граничные циклы в <tex>O(S_1, S_2)</tex>, обходя <tex>D</tex>.# Построим граф <tex>G</tex>, вершинам которого соответствуют циклы, соединив ребрами дырки и циклы, ближайшие слева к левым вершинам дырок.# Для каждой компоненты связности графа <tex>G</tex>: пусть <tex>C</tex> – внешняя граница компоненты связности, ограничивающая грань <tex>f</tex>. Создать запись для этой грани, установить ссылку на полуребро внешней границы грани и ссылки на полуребра дырок грани. Также для всех полуребер грани установить ссылки на инцидентную грань.# Для каждой грани <tex>f</tex> из <tex>O(S_1, S_2)</tex> установить ссылки на грани из <tex>S_1</tex> и <tex>S_2</tex>, содержащие <tex>f</tex>. === Общее время работы ==={{Теорема|statement=Пусть <tex>S_1</tex> имеет сложность <tex>n_1</tex>, <tex>S_2</tex> имеет сложность <tex>n_2</tex>, <tex>n = n_1 + n_2</tex>. Пересечение <tex>S_1</tex> и <tex>S_2</tex> может быть построено за время <tex>O(n \log{n} + k \log{n})</tex>, где <tex>k</tex> – сложность пересечения.|proof=Копирование двух РСДС в один занимает <tex>O(n)</tex> времени, заметающая прямая работает <tex>O(n \log{n} + k \log{n})</tex> времени по лемме. Создание граней работает линейное время от сложности <tex>O(S_1, S_2)</tex>. Маркировка граней РСДС работает за <tex>O(n \log{n} + k \log{n})</tex>.}}
