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.