How do I construct a doubly connected edge list given a set of line segments?

Question

For a given planar graph $G(V,E)$ embedded in the plane, defined by a set of line 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.

According to this description of the DCEL data structure, there are many connections between different objects (i.e. vertices, edges and faces) of the DCEL. So, a DCEL seems to be difficult to build and maintain.

Do you know of any efficient algorithm which can be used to construct a DCEL data structure?

Answer 1

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

1. For each endpoint, create a vertex.

2. For each input segment, create two half-edges, and assign their tail vertices and twins.

3. For each endpoint, sort the half-edges whose tail vertex is that endpoint in clockwise order.

4. For every pair of half-edges e1, e2 in clockwise order, assign e1->twin->next = e2 and e2->prev = e1->twin.

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

6. For every cycle, allocate and assign a face structure.

• pshufb: Basically a bunch of gnarly bookkeeping. This is probably why textbook authors are reluctant to go into detail.