Jak zbudować podwójnie połączoną listę krawędzi, biorąc pod uwagę zestaw segmentów linii?

Dla danego płaskiego wykresu osadzonego w płaszczyźnie, zdefiniowanego przez zestaw segmentów liniowych , każdy segment jest reprezentowany przez punkty końcowe . Skonstruuj strukturę danych DCEL dla podziału planarnego, opisz algorytm, udowodnij jego poprawność i pokaż złożoność.$G(V,E)$$E= \left \{ e_1,...,e_m \right \}$$e_i$$\left \{ L_i,R_i \right \}$

Zgodnie z tym opisem struktury danych DCEL istnieje wiele połączeń między różnymi obiektami (tj. Wierzchołkami, krawędziami i powierzchniami) DCEL. Zatem DCEL wydaje się trudny do zbudowania i utrzymania.

Czy znasz jakiś skuteczny algorytm, który można wykorzystać do budowy struktury danych DCEL?

Struktura danych (konwencje zgodne z artykułem z Wikipedii ):

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

Algorytm

1. Dla każdego punktu końcowego utwórz wierzchołek .

2. Dla każdego segmentu wejściowego utwórz dwie pół-krawędzie i przypisz ich wierzchołki i bliźniaki.

3. Dla każdego punktu końcowego posortuj połówki krawędzi, których wierzchołek ogona jest tym punktem końcowym w kolejności zgodnej z ruchem wskazówek zegara.

4. Dla każdej pary pół krawędzi e1, e2w kolejności zgodnej z ruchem wskazówek zegara przypisz e1->twin->next = e2i e2->prev = e1->twin.

5. Wybierz jedną z krawędzi i przypisz ją jako reprezentatywną dla punktu końcowego. (Przypadek zdegenerowany: jeśli ena posortowanej liście jest tylko jedna połowa krawędzi set e->twin->next = ei e->prev = e->twin). Kolejne wskaźniki to permutacja na pół-krawędziach.

6. Dla każdego cyklu przydziel i przypisz strukturę twarzy .