Search code examples
computational-geometry

How to add a diagonal to a doubly-connected edge list in constant time?

I'm working through the polygon triangulation algorithm in Computational Geometry: Algorithms and Applications, 3rd edition, by Mark de Berg and others. The data structure used to represent the polygon is called a "doubly-connected edge list". As the book describes, "[it] contains a record for each face, edge, and vertex". Each edge is actually stored as two "half edges", representing each side of the edge. This makes it easier to walk the half edges around a face. The half edge records look like:

// Pseudocode. No particular language. The properties need to be pointers/references of some kind.
struct HalfEdge {
   Vertex   origin;
   HalfEdge twin;
   Face     incidentFace;
   HalfEdge next;
   HalfEdge previous;
}

Now imagine I'm processing this polygon, with one face (so far) called Face1. I need to add a diagonal at the dotted line. This will create a new face (Face2). It seems like I need to walk all those HalfEdges that now surround Face2 and set their incidentFace property to point to Face2.

But the book says:

The diagonals computed for the split and merge vertices are added to the doubly-connected edge list. To access the doubly-connected edge list we use cross-pointers between the edges in the status structure and the corresponding edges in the doubly-connected edge list. Adding a diagonal can then be done in constant time with some simple pointer manipulations.

I don't see any further explanation. I'm not sure what a "cross pointer" means here. The "status structure" refers to a binary search tree of edges that is used to easily find the edge to the left of a given vertex, as the polygon is processed from top to bottom.

Can anyone explain this further? How are they able to update all the edges in constant time?

Solution

  • The same book (page 33) says:

    Even more important is to realize that in many applications the faces of the subdivision carry no interesting meaning (think of the network of rivers or roads that we looked at before). If that is the case, we can completely forget about the face records, and the IncidentFace() field of half-edges. As we will see, the algorithm of the next section doesn’t need these fields (and is actually simpler to implement if we don’t need to update them).

    So, you don't need to modify the incidentFace field in any half-edges after each diagonal insertion - you will be able to find vertices of all the monotone polygons using the next field of the HalfEdge record after all the necessary diagonals are inserted into the DCEL.

    The most intricate job here is to set next and prev fields of newly inserted half-edges, and to modify these fields in existing half-edges. Exactly four existing half-edges need to be updated after each insertion - but it's not easy to find them.

    As you already know, each DCEL vertex record contains a field, pointing to any half-edge, originating in this vertex. If you keep this field pointing to an internal half-edge or most recently inserted half-edge, then it'll be a little bit easier to find half-edges, which need updates in their next and prev fields after each insertion.