Пересечение многоугольников (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].

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

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

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

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

7. Пусть [math]C[/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].

Q&A

Копирование РСДС - просто объединение в одну структуру. Как сделать его правильным - это уже следующие пункты.

Как из пересечения ребер сделать новую компоненту РСДС - см рисунок.

Сколько будет faces? Столько же, сколько outer boudaries + 1.

Как узнать, что данный цикл это внешняя граница для face или же это дыра в нем? Мы знаем, что face находится слева от half-edge. Поэтому возьмем самую левую точку (в случаем, если их несколько, то самую нижнюю) и возьмем входящий и выходящий из нее half-edge. В случае угла между ними менее 180 градусов, то это внешняя граница, иначе это дыра. Это действует только для самой левой точки из цикла.

Че за граф такой пацанский? ну ваще он тащит.