Problem with storing an existing triangulation in a DCEL

Question

I am trying to store an existing 2D triangulation (of which I have all of the vertices and edges) in a DCEL data structure.

Using the algorithm described in this answer, I was able to store a part of the triangulation, but not the "half-edge" representative for each triangle.

The algorithm is reported below

Algorithm

1. For each endpoint, create a vertex.

2. For each input segment, create two half-edges, and assign their tail vertices and twins.

3. For each endpoint, sort the half-edges whose tail vertex is that endpoint in clockwise order.

4. For every pair of half-edges e1, e2 in clockwise order, assign e1->twin->next = e2 and e2->prev = e1->twin.

5. Pick one of the half-edges and assign it as the representative for the endpoint. (Degenerate case: if there's only one half-edge e in the sorted list, set e->twin->next = e and e->prev = e->twin). The next pointers are a permutation on half-edges.

6. For every cycle, allocate and assign a face structure.

Instruction 5 seems to be easier said than done. How can I ensure that every triangle will have a representative, and that a representative will be assigned only once for each triangle?

Furthermore, in point 6, which cycle is it referring to?

(So far, my implementation is similar to the one provided in the answer.)

Answer 1

The point of a half-edge data structure is that each half-edge is incident to exactly one face, and each face is represented by a list of half-edges given in order around the face. This is different from a normal planar map in which edges are incident to two faces. This can make certain coding tasks easier to deal with. So an (undirected) edge $\{u, v\}$ gets split into two half-edges $uv$ and $vu$ which are directed and twins of each other.

To list all half-edges (in order) incident to a face just requires following next pointers from each edge. Something like:

HalfEdge startEdge = ...some half-edge...
HalfEdge walk = startEdge;
do {
  //... do something here ...
  walk = walk.next;
} while (walk != startEdge);

In a DCEL the code above will walk around all edges in ccw order incident to the face startEdge.

Here is a concrete example:

Suppose we want to represent a triangulation with a single triangle $ABC$ where $A$, $B$, and $C$ are given in ccw order. We create six half edges: $AB$, $BC$, $CA$, $BA$, $CB$, and $AC$.

set the twins: $AB.twin$ = $BA$, $BA.twin = AB$. $AC.twin = CA$, $CA.twin = AC$, $BC.twin = CB$ $CB.twin = BC$.

set the next pointers: $AB.next = BC$, $BC.next = CA$, $CA.next = AB$ $AC.next = CB$ $CB.next = BA$, $BA.next = AC$.

and prev pointers $AB.prev = CA$, $BC.prev = AB$, $CA.prev = BC$, $BA.prev = CB$ $AC.prev = BA$ $CB.prev = AC$.

Now we already have implicitly faces: if we start with $AB$ and chase the next pointers around until we get back to $AB$, we get $AB$, $BC$, $CA$ which represents the interior of the triangle. If we start with $BA$ we get a different list: $BA$, $AC$, $CB$. This list represents the so-called "unbounded" face which is the exterior of our triangle. These are the "cycles" you mentioned. The first cycle is the (cyclic) list $AB\leftrightarrow BC\leftrightarrow CA$ and the second is $BA \leftrightarrow AC\leftrightarrow CB$.

For some applications this is all you need, but for others you may want a structure for storing extra information about the face. Keep in mind that the face is already represented by the double linked list $AB\leftrightarrow BC\leftrightarrow CA$. However we can make two data structures $f_0$ and $f_1$ for storing extra information for the unbounded face $f_0$ and the interior of the triangle $f_1$. We then set pointers again:

$AB.face = f_1$, $BC.face = f_1$, $CA.face = f_1$, $BA.face = f_0$, $CB.face = f_0$, $AC.face = f_0$.

So now each half-edge points to the face incident to it. But we may also want to start with a face structure and then get a list of its incident half-edges. We already have the half-edges stored as lists, so we just need to point to any arbitrary start of the list, something like:

$f_0.halfEdgeList = BA$

$f_1.halfEdgeList = AB$

So now given a face $f$, we can loop over all its incident half-edges as before:

HalfEdge startEdge = f.halfEdgeList;
HalfEdge walk = startEdge;
do { // ... same as above
  walk = walk.next;
} while (walk != startEdge);

Finally, assuming you already have correctly set the previous, next, and twin pointers for your half-edges, then you could do something like this: when you create a half-edge, initialize its face pointer to 0. Then add all half-edges to a queue.

Note I'm writing pseudo-code, not C++ code here:

while (!queue.Empty()) {
  HalfEdge startWalk = queue.dequeue();
  if (startWalk.face = 0) {
    //This half-edge doesn't have a face yet
    Face f = create_new_face(); //Some function to create a new face and add it to any appropriate lists

    //Now walk around all edges from startWalk setting the face:
    HalfEdge current = startWalk;
    do {
      current.face = f;
      current = current.next;
    } while (current != startWalk);
  }
}

UPDATE: I looked at the link you provided and want to give a bit of terminology. Above I used the terms source and target to refer to the the start and end vertices of the half-edge. In the C++ code you linked to source is called tail, and target is the tail of the twin. So if you have a half edge called halfEdge:

vertex *source = halfEdge->tail;
vertex *target = halfEdge->twin->tail;