Изменения

Во-первых, скопировать doubly­ connected edge lists <tex>S1</tex> и <tex>S2</tex> в один новый <tex>DCEL</tex>. Новый <tex>DCEL</tex> не является допустимым <tex>DCEL</tex>, т.к. он еще не представляет собой плоский подграф. Это задача алгоритма заметающей прямой: он должен трансформировать <tex>DCEL</tex> в допустимый <tex>DCEL</tex> для <tex>O(S1, S2)</tex> путем вычисления пересечения между двумя сетями ребер, и связывая воедино соответствующие части из двух <tex>DCEL</tex>. Мы применяем Применяем этот алгоритм на множестве сегментов, что является объединением множеств ребер двух подграфов <tex>S1</tex> и <tex>S2</tex>. Напомним, что алгоритм Алгоритм поддерживается двумя структурами данных: очереди событий <tex>Q</tex>, в котором хранятся точки событий, и структура состояния <tex>T</tex>, которой является бинарное дерево храненящее сегменты, пересекающие линии развертки, расположенные слева направо. Мы теперь также должны поддерживать <tex>DCEL</tex> <tex>D</tex>. Первоначально <tex>D</tex> содержит копию <tex>DCEL</tex> для <tex>S1</tex> и <tex>DCEL</tex> для <tex>S2</tex>. В плоскости развертки преобразуем <tex>D</tex> к правильному <tex>DCEL</tex> для <tex>O(S1, S2)</tex>. Мы держим перекрестные указатели между ребер в структуре состояния <tex>T</tex> и половина текущих записей в <tex>D</tex>, которые соответствуют им. Таким образом мы можем получить доступ к части <tex>D</tex>, которая должна быть изменена, когда мы сталкиваемся с точкой пересечения.

Рассмотри один из 2 возможных случаев, а именно, когда edge <tex>e</tex> из <tex>S1</tex> проходит через вершину <tex>V</tex> <tex>S2</tex>, (см. Рисунок) edge <tex>e</tex> должно быть заменено двумя edges обозначим <tex>e'</tex> и <tex>e''</tex>. В <tex>DCEL</tex>, два <tex>half-edge</tex> для е должны превратиться в четыре. Мы создаем два новых <tex>half-edge</tex>, с <tex>V</tex> в нуле. Два существующих <tex>half-edge</tex> для е содержат конечные точки <tex>e</tex>, как их происхождения. Тогда мы объединяем попарно существующие <tex>half-edges</tex> с новыми <tex>half-edges</tex>, устанавливая их указатели twin'ов. Так <tex>e'</tex> представлен одним новым и одним существующим частично edge, и то же самое для <tex>e''</tex>. Теперь мы должны установить ряд <tex>Prev</tex> и <tex>Next</tex>. <tex>Next</tex> двух новых <tex>half-edges</tex> являются копией <tex>Next</tex> старого <tex>half-edge</tex>, не имеющего пары. В <tex>half-edges</tex>, в которые эти указатели точки должны обновлять свои <tex>Prev</tex> и установливать устанавливать его на новых <tex>half-edges</tex>. Далее мы должны установить <tex>Next</tex> и <tex>Prev</tex> четырех <tex>half-edges</tex> представляющих <tex>e'</tex> и <tex>e''</tex>, и из четырех <tex>half-edges</tex> инциденого инцидентного <tex>S2</tex> <tex>v</tex>. Мы размещаем эти четыре <tex>half-edges</tex> от <tex>S2</tex>, проверяя, где <tex>e'</tex> и <tex>e''</tex> должны быть в циклическом порядке вершин вокруг вершины <tex>v</tex>. Есть четыре пары <tex>half-edges</tex>, которые связанны между собой <tex>Next</tex> с одним и <tex>Prev</tex> с другим. <tex>e'</tex> должен быть привязан к первому <tex>half-edge</tex> по часовой стрелке с началом в <tex>v.</tex> <tex>half-edge</tex> для <tex>e'</tex> с началом в <tex>v</tex> должен быть связан с первым против часовой стрелки <tex>half-edge</tex> с окончанием в <tex>v</tex>. Точно также и для <tex>e''</tex>.