1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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 vertices. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.