139
правок
Изменения
Нет описания правки
[[Файл:PSLG.png|400px|thumb|left|Ну как то так. Очевидно же]]
Дано: 2 ППЛГ в виде РСДС.
Вывод: пересечение этих ППЛГ в виде РСДС.
Алгоритм:
1. Копируем S1 <tex>S_1</tex> и S2 <tex>S_2</tex> в РСДС <tex>D</tex>.
2. Находим все пересечения ребер из S1 <tex>S_1</tex> с ребрами из S2 <tex>S_2</tex> с помощью заметающей прямой.
2.1 Когда находим точки пересечения, то обновляем <tex>D</tex>.
2.2 Сохраняем half-edge слева от event point в vertex, содержащемся в <tex>D</tex>.
3. Теперь <tex>D </tex> это нормальный РСДС, но без информации о faces.
4. Находим boundary cycles в <tex>D</tex>.
5. Создаем граф <tex>G</tex>, в котором узлы будут отвечать за boundary cycles и в котором ребра будут соединять только те узлы, один из которых будет являться границей дыры, а другой будет находиться слева от самой левой точки первого. (В случае, если это самая внешняя граница, то для нее пусть будет мнимая гигантская граница, с которой мы ее и соединим).
6. Для каждой компоненты графа:
7. Пусть <tex>С </tex> будет уникальная наружная граница цикла в компоненте, а <tex>f </tex> будет означать face ограниченный этим циклом. Создадим face для <tex>f</tex>. Запишем outer_component в какой-нибудь half-edge из <tex>C</tex>. И создадим список inner_components, состоящий из указателей на какой-нибудь half-edge из каждого цикла. А так же пусть incident_face в каждом half-edge будут обновлены на <tex>f</tex>.
==Q&A==
