139
правок
Изменения
Нет описания правки
==Алгоритм==
MapOverlay (<tex>S_1</tex>, <tex>S_2</tex>)
Дано: 2 ППЛГ в виде РСДС.
Вывод: пересечение этих ППЛГ в виде РСДС.
Алгоритм:
1. Копируем <tex>S_1</tex> и <tex>S_2</tex> в РСДС <tex>D</tex>.
2.1 Когда находим точки пересечения, то обновляем <tex>D</tex>.
3. Теперь <tex>D</tex> это нормальный РСДС, но без информации о faces.
==Q&A==
Копирование РСДС - просто объединение в одну структуру. Как сделать его правильным - это уже следующие пункты.
Как из пересечения ребер сделать новую компоненту РСДС - см рисунок.
Сколько будет faces? Столько же, сколько outer boudaries + 1.
Как узнать, что данный цикл это внешняя граница для face или же это дыра в нем? Мы знаем, что face находится слева от half-edge. Поэтому возьмем самую левую точку (в случаем, если их несколько, то самую нижнюю) и возьмем входящий и выходящий из нее half-edge. В случае угла между ними менее 180 градусов, то это внешняя граница, иначе это дыра. Это действует только для самой левой точки из цикла.
Че за граф такой пацанский? ну ваще он тащит.
