Пересечение многоугольников (PSLG overlaying)
Вычисление пересечения двух многоугольников представленных в виде РСДС
Алгоритм
MapOverlay (S1, S2) Дано: 2 ППЛГ в виде РСДС. Вывод: пересечение этих ППЛГ в виде РСДС. Алгоритм: 1. Копируем S1 и S2 в РСДС D.
2. Находим все пересечения ребер из S1 с ребрами из S2 с помощью заметающей прямой.
2.1 Когда находим точки пересечения, то обновляем D.
2.2 Сохраняем half-edge слева от event point в vertex, содержащемся в D.
3. Теперь D это нормальный РСДС, но без информации о faces.
4. Находим boundary cycles в D.
5. Создаем граф G, в котором узлы будут отвечать за boundary cycles и в котором ребра будут соединять только те узлы, один из которых будет являться границей дыры, а другой будет находиться слева от самой левой точки первого. (В случае, если это самая внешняя граница, то для нее пусть будет мнимая гигантская граница, с которой мы ее и соединим).
6. Для каждой компоненты графа:
7. Пусть С будет уникальная наружная граница цикла в компоненте, а f будет означать face ограниченный этим циклом. Создадим face для f. Запишем outer_component в какой-нибудь half-edge из C. И создадим список inner_components, состоящий из указателей на какой-нибудь half-edge из каждого цикла. А так же пусть incident_face в каждом half-edge будут обновлены на f.
