¿Cómo construyo una lista de bordes doblemente conectada dado un conjunto de segmentos de línea?

Para un gráfico plano dado incrustado en el plano, definido por un conjunto de segmentos de línea , cada segmento está representado por sus puntos finales . Construya una estructura de datos DCEL para la subdivisión plana, describa un algoritmo, pruebe que es correcto y muestre la complejidad.$G(V,E)$$E= \left \{ e_1,...,e_m \right \}$$e_i$$\left \{ L_i,R_i \right \}$

De acuerdo con esta descripción de la estructura de datos DCEL , hay muchas conexiones entre diferentes objetos (es decir, vértices, aristas y caras) del DCEL. Entonces, un DCEL parece ser difícil de construir y mantener.

¿Conoces algún algoritmo eficiente que pueda usarse para construir una estructura de datos DCEL?

Estructura de datos (convenciones consistentes con el artículo de Wikipedia ):

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 */
};

Algoritmo

1. Para cada punto final, cree un vértice .

2. Para cada segmento de entrada, cree dos medios bordes y asigne sus vértices de cola y gemelos.

3. Para cada punto final, ordene los medios bordes cuyo vértice de la cola es ese punto final en el sentido de las agujas del reloj.

4. Para cada par de medios bordes e1, e2en el sentido de las agujas del reloj, asigne e1->twin->next = e2y e2->prev = e1->twin.

5. Elija uno de los medios bordes y asígnelo como representante del punto final. (Caso degenerado: si solo hay un medio borde een la lista ordenada, set e->twin->next = ey e->prev = e->twin). Los siguientes punteros son una permutación en medios bordes.

6. Para cada ciclo, asigne y asigne una estructura de cara .