Was ist der Vorteil von Half Edge gegenüber Winged Edge?

Was ist der Vorteil der Verwendung von Half Edge gegenüber der Winged Edge-Datenstruktur für die Netzdarstellung?

Ich verstehe beide Netzdarstellungen. Der einzige Unterschied besteht darin, dass die halbe Kante eine gerichtete Kante und die geflügelte Kante eine ungerichtete Kante verwendet. Bisher kann ich mir nicht vorstellen, wie nützlich die Verwendung von Richtungskanten ist, aber es gibt nur mehr Speicherverbrauch.

Soweit ich das beurteilen kann, besteht der Hauptvorteil der Halbkante darin, dass das Durchqueren etwas einfacher sein kann, da die Kanten innerhalb jeder Fläche eine einheitliche Ausrichtung aufweisen.

Betrachten Sie das Problem, alle Scheitelpunkte oder Kanten einer bestimmten Fläche im Gegenuhrzeigersinn zu durchlaufen. In der Halbkantenstruktur kann dies erfolgen, indem Sie mit einer beliebigen Halbkante dieser Fläche beginnen und einfach den "nächsten" Zeigern folgen, bis Sie wieder dort sind, wo Sie begonnen haben.

Im Gegensatz dazu ist dies in einer Struktur mit geflügelten Kanten etwas ärgerlich, da die Kanten beliebig ausgerichtet sind. Jede Kante, auf die Sie stoßen, zeigt entweder im oder gegen den Uhrzeigersinn in Bezug auf das Gesicht, um das Sie iterieren möchten. Sie müssen daher bei jedem Schritt eine zusätzliche bedingte Überprüfung durchführen, um festzustellen, ob Sie die aktuelle Kante vorwärts oder rückwärts durchlaufen sollten.

Andere Arten von Konnektivitätsabfragen verhalten sich ähnlich: Mit der Version mit halber Kante können Sie Links in einer konsistenten Reihenfolge folgen, während die Version mit geflügelter Kante bei jedem Schritt Orientierungsprüfungen erfordert.

Ob die Bedingungen tatsächlich ein Leistungsproblem für die Flügelkante darstellen, hängt wahrscheinlich von anderen Faktoren ab. Für eine "naive" Implementierung mit Zeigern in alle Richtungen und Daten, die über den Speicher verteilt sind, würde ich erwarten, dass der Overhead des Cache-Fehlers den Effekt der Bedingungen überflutet. Wenn Sie jedoch eine dicht gepackte Datenstruktur haben, in der sich alles im Cache befindet, können aufgrund von Verzweigungsvorhersagen usw. einige Auswirkungen der Bedingungen auftreten. Es ist schwer zu sagen.

Wenn ich die Leistung in Ruhe lasse, würde ich die halbe Kante bevorzugen, nur weil es einfacher zu sein scheint, den richtigen Code zu finden und zu schreiben, selbst wenn dies zu einem geringen Speicheraufwand führt.

Übrigens gibt es einige andere Entwurfsoptionen mit Netzdatenstrukturen, die häufig mit dieser verwechselt zu werden scheinen. Ein Kommentator erwähnte die einfache oder doppelte Verknüpfung, aber natürlich können Sie entweder die einfache oder die doppelte Verknüpfung entweder mit der halben oder der geflügelten Kante durchführen. (Obwohl ich nicht sehe, wie eine einzelne Verknüpfung mit einer Flügelkante überhaupt funktionieren würde, müssen Sie, wie oben erwähnt, die Kanten im Verlauf einer Abfrage möglicherweise vorwärts oder rückwärts durchlaufen.)

Es stellt sich auch die Frage, ob die Scheitelpunkt- und Flächenstrukturen eine Liste aller ihrer Kanten oder nur eine speichern (und Sie müssen die Kanten durchlaufen, um den Rest zu finden). Eine Liste mit Kanten variabler Länge pro Scheitelpunkt / Fläche erschwert die Logik erheblich, wenn Sie dies effizient ausführen möchten (dh keine separate Heap-Zuordnung pro Scheitelpunkt / Fläche haben), dies ist jedoch wiederum unabhängig davon, ob die Kanten Halbkanten sind oder Flügelkante.