How do I visit all edges incident to a vertex in a DCEL data structure?

Question

In a doubly-connected edge list (DCEL) data structure, each vertex v stores a pointer to one arbitrary half-edge, v.inc, which has v as its origin, that is, v.inc.origin == v. However, there may be multiple half-edges which have v as its origin.

How do I access or iterate all half-edges which have v has their origin?

Answer 1

We can do that by exploiting the structure of the DCEL.

Recall first that each half-edge h has a pointer to its twin half-edge, h.twin. Each half-edge h also has a pointer to its successor, h.next, and predecessor, h.prev, half-edges, which lie on the boundary of its incident face (that is, on the boundary of h.face), assuming that the incident face of h lies to its left (if we walk, in a counter-clockwise matter, along the edges incident to h.face by following the "next" pointers).

So, how do we visit all half-edges which have a vertex v as their origin?

The solution consists in exploiting the pointers h.twin and h.next.

Let h be the half-edge such that a vertex v stores h as its own incident half-edge (that is, h == v.inc), where v is the vertex that we want to know all half-edges which have v as its origin, where h is one of those half-edges. We can then access h.twin, which has v as its destination. Hence, h.twin.next is a half-edge which also leaves v. Unless v is adjacent only to one vertex u, which implies that v.inc == h is the only half-edge leaving v (and we are done), then h.twin.next is different from h. In that case, let w = h.twin.next. Then w.twin is a half-edge which has v as its destination (i.e. like h.twin). Hence, w.twin.next is also a half-edge which leaves v. We can proceed in this matter until w.twin.next is equal to h.

In a more formal way, the algorithm may look as follows.

function all_half_edges_leaving(v):
    h = v.inc
    list = [h]
    w = h.twin.next
    while w != h:
        list.append(w)
        w = w.twin.next
   return list

Clearly, once we have the half-edges leaving v, we can access in constant time also its twins (given that each half-edge stores a pointer to its twin). Alternatively, we may also store the twins in a list during the procedure above.