Изменения

Для начала посмотрим, как можно больше информации от doubly connected edge lists для <tex>S1</tex> и <tex>S2</tex> мы можем повторно использовать в doubly connected edge lists для <tex>O(S1, S2)</tex>. Рассмотрим сеть ребер и вершин S1. Эта сеть разделена на кусочки краями <tex>S2</tex>. Эти кусочки в большинстве своем могут использоваться повторно, все, за исключением тех, которые отделены краями <tex>S2</tex>. Такие нужно обновлять. Если ориентация <tex>half-edge</tex> изменится, нам придется менять информацию в этих записях. Половинки ребра ориентированы таким образом, что <tex>face</tex>, которым они связаны лежит слева; форма <tex>face</tex> может изменяться в наложении, но он будет оставаться в той же стороне <tex>half-edge</tex>. Следовательно, мы можем повторно использовать <tex>half-edge</tex> records, соответствующие краям, которые не пересекаются пересекают ребра из другой карты. Иными словами, есть только <tex>half-edge</tex> records в <tex>DCEL</tex> для <tex>O(S1, S2)</tex>, которые мы не можем заимствовать из <tex>S1</tex> или <tex>S2</tex>, ими являются те, которые попадают на пересечение между краями из разных картдругого графа.