Пересечение многоугольников (PSLG overlaying)

Эта статья находится в разработке!

Вычисление пересечения двух многоугольников представленных в виде РСДС

Ну как то так. Очевидно же

Алгоритм

MapOverlay ([math]S_1[/math], [math]S_2[/math]) Дано: 2 ППЛГ в виде РСДС. Вывод: пересечение этих ППЛГ в виде РСДС. Алгоритм: 1. Копируем [math]S_1[/math] и [math]S_2[/math] в РСДС [math]D[/math].

2. Находим все пересечения ребер из [math]S_1[/math] с ребрами из [math]S_2[/math] с помощью заметающей прямой.

2.1 Когда находим точки пересечения, то обновляем [math]D[/math].

2.2 Сохраняем half-edge слева от event point в vertex, содержащемся в [math]D[/math].

3. Теперь [math]D[/math] это нормальный РСДС, но без информации о faces.

4. Находим boundary cycles в [math]D[/math].

5. Создаем граф [math]G[/math], в котором узлы будут отвечать за boundary cycles и в котором ребра будут соединять только те узлы, один из которых будет являться границей дыры, а другой будет находиться слева от самой левой точки первого. (В случае, если это самая внешняя граница, то для нее пусть будет мнимая гигантская граница, с которой мы ее и соединим).

6. Для каждой компоненты графа:

7. Пусть [math]С[/math] будет уникальная наружная граница цикла в компоненте, а [math]f[/math] будет означать face ограниченный этим циклом. Создадим face для [math]f[/math]. Запишем outer_component в какой-нибудь half-edge из [math]C[/math]. И создадим список inner_components, состоящий из указателей на какой-нибудь half-edge из каждого цикла. А так же пусть incident_face в каждом half-edge будут обновлены на [math]f[/math].