Изменения

Рассмотри один из 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>.