Bagaimana cara membuat daftar tepi yang terhubung dua kali lipat diberikan satu set segmen garis?

Untuk graf planar diberikan tertanam di pesawat, didefinisikan oleh satu set segmen garis E = { e 1 , . . . , e m } , setiap segmen e i diwakili oleh titik akhir { L i , R i } . Buat struktur data DCEL untuk subdivisi planar, jelaskan algoritme, buktikan kebenarannya, dan tunjukkan kerumitannya.$G(V,E)$$E= \left \{ e_1,...,e_m \right \}$$e_i$$\left \{ L_i,R_i \right \}$

Menurut uraian struktur data DCEL ini , ada banyak koneksi antara objek yang berbeda (yaitu simpul, tepi dan wajah) dari DCEL. Jadi, DCEL tampaknya sulit dibangun dan dipelihara.

Apakah Anda mengetahui adanya algoritma efisien yang dapat digunakan untuk membangun struktur data DCEL?

Struktur data (konvensi yang konsisten dengan artikel 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 */
};

Algoritma

1. Untuk setiap titik akhir, buat simpul .

2. Untuk setiap segmen input, buat dua setengah sisi , dan tetapkan simpul dan kembar ekornya.

3. Untuk setiap titik akhir, urutkan setengah sisi yang ujung ekornya adalah titik akhir itu dalam urutan searah jarum jam.

4. Untuk setiap pasang setengah sisi e1, e2dalam urutan searah jarum jam, tetapkan e1->twin->next = e2dan e2->prev = e1->twin.

5. Pilih salah satu dari setengah sisi dan tetapkan sebagai perwakilan untuk titik akhir. (Kasus degenerasi: jika hanya ada setengah sisi edalam daftar yang diurutkan, set e->twin->next = edan e->prev = e->twin). Pointer berikutnya adalah permutasi pada half-edge.

6. Untuk setiap siklus, alokasikan dan tetapkan struktur wajah .