So konvertieren Sie die Kantenliste in DCEL

Question

Ich versuche, die Triangulation von polygone zu machen. Das Problem ist, dass ich die Darstellung der Triangulation in Form einer Kantenliste bekomme, aber ich muss die DCEL (doppelt verbundene Kantenliste) bekommen. Gibt es einen schnellen Algorithmus, um die Kantenliste in DCEL zu konvertieren?

Answer 1

Es gibt immer den offensichtlichen Weg. Fügen Sie jedem Listenelement einen Backlink hinzu: Gehen Sie einmal durch Ihre Liste, indem Sie zwei Iteratoren an einer Stelle hinter der anderen verwenden, und fügen Sie den Backlink hinzu.

---

Noch einfacher wäre es, nur die std::list class zu verwenden. Es ist eine DCEL, also können Sie Ihre aktuelle Liste einfach in eine std::list konvertieren.