[Solved]: Problem with storing an existing triangulation in a DCEL

Problem Detail: I am new to StackExchange, and I already made the mistake of posting a new question as a response to a previous question. Here, I rewrote my question more clearly and separately. I am trying to store an existing 2D triangulation in a DCEL data structure, and I have all of the vertices and edges. I was able to store all of the information correctly except the half_edge representative for each triangle. Here is the algorithm I used: (taken from Constructing of Double Connected Edge List (DCEL))

Algorithm: For each endpoint, create a vertex. For each input segment, create two half-edges and assign their tail vertices and twins. For each endpoint, sort the half-edges whose tail vertex is that endpoint in clockwise order. For every pair of half-edges e1, e2 in clockwise order, assign e1->twin->next = e2 and e2->prev = e1->twin. 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. For every cycle, allocate and assign a face structure.

The last sentence 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, which cycle is it referring to? If you have any other ideas, please share. Thank you very much for your help. I’ve been struggling with this for a while. PS- I am working in C++. Also, I am using the same structure as provided in the link above.

Asked By : Sioma Dukh

Answered By : jcb

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 $ABleftrightarrow BCleftrightarrow CA$ and the second is $BA leftrightarrow ACleftrightarrow 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 $ABleftrightarrow BCleftrightarrow 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;

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14591

Asked By : Sioma Dukh

Answered By : jcb

Best Answer from StackOverflow

Related