Como construo uma lista de arestas duplamente conectada, considerando um conjunto de segmentos de linha?

Para um determinado gráfico plano incorporado no plano, definido por um conjunto de segmentos de linha , cada segmento é representado por seus pontos finais . Construa uma estrutura de dados DCEL para a subdivisão planar, descreva um algoritmo, prove sua correção e mostre a complexidade.$G(V,E)$$E= \left \{ e_1,...,e_m \right \}$$e_i$$\left \{ L_i,R_i \right \}$

De acordo com esta descrição da estrutura de dados do DCEL , existem muitas conexões entre diferentes objetos (vértices, arestas e faces) do DCEL. Portanto, um DCEL parece ser difícil de construir e manter.

Você conhece algum algoritmo eficiente que possa ser usado para construir uma estrutura de dados DCEL?

Estrutura de dados (convenções consistentes com o artigo da 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 terminal, crie um vértice .

2. Para cada segmento de entrada, crie duas meias arestas e atribua seus vértices de cauda e gêmeos.

3. Para cada ponto final, classifique as meias-arestas cujo vértice final é o ponto final no sentido horário.

4. Para cada par de meias arestas e1, e2no sentido horário, atribua e1->twin->next = e2e e2->prev = e1->twin.

5. Escolha uma das meias-arestas e atribua-a como representante para o terminal. (Caso degenerado: se houver apenas uma meia borda ena lista classificada set e->twin->next = ee e->prev = e->twin). Os próximos ponteiros são uma permutação em meias bordas.

6. Para cada ciclo, aloque e atribua uma estrutura de face .