Constructing of Double Connected Edge List (DCEL)

Problem Detail: 

For a given planar graph $G(V,E)$ embedded in the plane, defined by list of segments $E= \left \{ e_1,...,e_m \right \} $, each segment $e_i$ is represented by its endpoints $\left \{ L_i,R_i \right \}$. Construct a DCEL data structure for the planar subdivision, describe an algorithm, prove it's correctness and show the complexity.

More information about DCEL (double connected edge list) you can find on wikipedia - DCEL.

According to description of DCEL and connections between different objects of DCEL (vertices, edges and faces) the required data structure must be complicated.

I found that doubly-linked lists can be used as data structure for DCEL, I am not sure how to build and maintain connections between vertices - edges and edges - faces.

I tried to find any hint in textbook, but the construction of DCEL wasn't described, map overlay is more popular topic.

Regarding the algorithm, plane sweep algorithm with $O((n+l)\log n)$ should do the job, but it seems to be overkill, because segments are intersected not in arbitrary points, but only in endpoints, therefore $O(n\log n)$ seems more reasonable.

The main problem is the data structure, so far I haven't seen any good example with at least similar complexity.

Please, if you have any idea about a data structure for DCEL or about algorithm for constructing DCEL, share it with us.

Asked By : com

Answered By : pshufb

Data structure (conventions consistent with the Wikipedia article):

struct half_edge;  struct vertex {     struct half_edge *rep;  /* rep->tail == this */ };  struct face {     struct half_edge *rep;  /* rep->left == this */ };  struct half_edge {     struct half_edge *prev;  /* prev->next == this */     struct half_edge *next;  /* next->prev == this */     struct half_edge *twin;  /* twin->twin == this */     struct vertex *tail;     /* twin->next->tail == tail &&                                 prev->twin->tail == tail */     struct face *left;       /* prev->left == left && next->left == left */ }; 

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. If you do things right, this won't require extra code.) The next pointers are a permutation on half-edges. For every cycle, allocate and assign a face structure.

Best Answer from StackOverflow

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