Return to Revisions

First, define (based on the Wikipedia article) the following structs (in C) to represent the different elements of a DCEL data structure

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.