Изменения

'''MapOverlay (<tex>S_1</tex>, <tex>S_2</tex>)'''

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

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

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

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

'''Че за граф такой пацанский? ну ваще он тащит''' См рисунок.Из него мы сможем понять, какие циклы принадлежат одному и тому же face. Например, в рисунке мы видим, что C2, C3 и C6 являются циклами одного face. Из предыдущего вопроса мы понимаем, что C2 есть внешняя граница. '''Лемма к предыдущему вопросу''' - Каждая компонента графа отвечает за множество циклов инцидентных одному face. '''Доказательство''': Рассмотрим цикл <tex>C</tex>, который ограничивает дыру в face <tex>f</tex>. Поскольку <tex>f</tex> локально лежит левее самой левой вершины из <tex>C</tex>, то <tex>C</tex> должен быть соединен с другим циклом, который тоже ограничивает <tex>f</tex>. отсюда следует, что циклы есть компонента связности в графе, описывающая один и тот-же face. Для того, что бы закончить доказательство, покажем, что каждый цикл ограничивающий дыру в <tex>f</tex> есть в той же компоненте связности, что и внешняя граница <tex>f</tex>. Предположим, что есть цикл, для которого это не так. Пусть <tex>C</tex> — самый левый такой цикл, то есть тот, чья самая левая вершина самая левая (шляпа). По определению есть ребро между <tex>C</tex> и неким <tex>C'</tex>, который лежит слева от самой левой вершины <tex>C</tex>. Следовательно <tex>C</tex> в той же компоненте связности, что и <tex>C'</tex>, который не в той же компоненте, что внешняя граница <tex>f</tex>. Противоречие. == Литература и источники ==* Вычислительная геометрия. Алгоритмы и приложения, де Берг Марк и другие. Глава 2.3