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(nlog 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
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
