Die Quad-Edge-Datenstruktur (Delaunay / Voronoi)

2 Fragen an die Rechengeometer oder Algebraisten:

Ich fange gerade an, mich mit Computergeometrie zu beschäftigen, und ich liebe sie =)

Ich versuche, den berühmten Artikel von Guibas und Stolfi mit dem Titel "Primitive für die Manipulation allgemeiner Unterteilungen und die Berechnung von Voronoi-Diagrammen" zu lesen , um einen Delaunay-Triangulationsalgorithmus zu implementieren. Ich bin versucht, alle theoretischen Dinge zu überspringen und einfach die Beschreibung der Quad-Edge-Datenstruktur zu lesen, um Zeit zu sparen. Ich denke jedoch, dass es sich lohnen kann, die ganze Mathematik in dem Artikel zu verstehen, wenn die Struktur weit verbreitet ist oder nur, weil sie schön sein kann.

Die Mathematik ist ein bisschen zu eng für mich. Ich bin nicht völlig ahnungslos in Bezug auf die Topologie, aber die Beschreibung ihrer Randalgebra erfordert Kenntnisse der abstrakten Algebra, die ich nicht habe.

Meine beiden Fragen sind: Welche anderen Anwendungen der Quad-Edge-Struktur gibt es neben der Berechnung von Delaunay / Voronoi? Es scheint ein extrem mächtiges Werkzeug zu sein.

Die zweite Frage; Was ist eine abstrakte Algebra? Es wäre großartig, wenn Sie mir einen Verweis auf eine Einführung in die abstrakte Algebra geben könnten, gerade genug, damit ich den Abschnitt über ihre Randalgebra verstehen kann.

Vielen Dank!

Ich denke, Guibas und Stolfis "Randalgebra" -Formalismus ist ein bisschen unnötig.

Alles, was wirklich notwendig ist, ist sich an die Unterscheidung zwischen primären und dualen Graphen zu erinnern. Jede Fläche des ursprünglichen Graphen hat einen entsprechenden dualen Vertex f * ; jede Kante e des Urgraphen hat eine entsprechende Doppelkante e ∗ ; und jeder Scheitelpunkt v des ursprünglichen Graphen hat eine entsprechende doppelte Fläche v ∗ . Ursprüngliche Kanten verbinden Urscheitelpunkte und separate Urflächen. Doppelkanten verbinden Doppelscheitelpunkte und separate Doppelflächen. Das Doppelte des Doppelten von allem ist das Ursprüngliche. Siehe Abbildung 4 in der Arbeit von Guibas und Stolfi:$f$$f^*$$e$$e^*$$v$$v^*$

Guibas und Stolfi schlagen vor, jede Kante (entweder die ursprüngliche oder die duale) als Sammlung von vier gerichteten, orientierten Kanten zu betrachten. Der Einfachheit halber werde ich diese Pfeile nennen . Jeder Pfeil Punkte von einem Endpunkt Schwanz ( → e ) an den anderen Endpunkt Kopf ( → e$\vec{e}$$\text{tail}(\vec{e})$$\text{head}(\vec{e})$ und lokal trennen zwei Flächen und rechts ( → e ) . Die Wahl des Endpunkts, der als Tail bezeichnet werden soll ( → e ), liegt beim Dart$\text{left}(\vec{e})$$\text{right}(\vec{e})$$\text{tail}(\vec{e})$Richtung und die Wahl, welches Gesicht nach ist seine Ausrichtung . (Guibas und Stolfi verwenden "Org" und "Dest" anstelle von "Tail" und "Head", aber ich bevorzuge die kürzeren Labels, weil unnötige Abkürzungen böse sind.)$\text{left}(\vec{e})$

Für jeden Dart assoziieren Guibas und Stolfi drei verwandte Darts:$\vec{e}$

1. : Der Pfeil verlässt den Schwanz ( → e ) im Gegenuhrzeigersinn nach → e .$\text{tailNext}(\vec{e})$$\text{tail}(\vec{e})$$\vec{e}$
2. : Der "gleiche" Pfeil wie$\text{flip}(\vec{e})$$\vec{e}$$\text{left}(\vec{e})$$\text{right}(\vec{e})$
3. $\text{rotate}(\vec{e})$$\vec{e}$

Diese drei Funktionen erfüllen alle Arten von wundervollen Identitäten, wie zum Beispiel die folgenden:

• $\text{right}(\text{tailNext}(\vec{e})) = \text{left}(\vec{e})$
• $\text{right}(\text{flip}(\vec{e})) = \text{left}(\vec{e})$
• $\text{right}(\text{rotate}(\vec{e})) = \text{head}(\vec{e})^*$
• $\text{flip}(\text{flip}(\vec{e})) = \vec{e}$
• $\text{rotate}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))) = \vec{e}$
• $\text{tailNext}(\text{rotate}(\text{tailNext}(\text{rotate}(\vec{e})))) = \vec{e}$

$e~Flip$e.Flip

Darüber hinaus kann man unter Berücksichtigung dieser drei Funktionen mehrere andere nützliche Funktionen definieren, wie z

• $\text{reverse}(\vec{e}) = \text{rotate}(\text{flip}(\text{rotate}(\vec{e})))$
• $\text{leftNext}(\vec{e}) = \text{rotate}(\text{tailNext}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))))$$\vec{e}$$\text{left}(\vec{e})$

Wenn Sie diese Funktionen kennen, erfahren Sie schließlich alles über die Topologie der Unterteilung, und jede polygonale Unterteilung einer beliebigen Oberfläche (orientierbar oder nicht) kann mit diesen drei Funktionen codiert werden.

Die Vierkantendatenstruktur ist eine besonders praktische Darstellung eines Oberflächendiagramms, das den Zugriff auf alle diese Funktionen sowie auf mehrere andere zeitlich konstante Vorgänge wie Einfügen, Löschen, Zusammenziehen, Erweitern und Spiegeln von Kanten ermöglicht. Teilen oder Zusammenführen von Eckpunkten oder Flächen; und Hinzufügen oder Löschen von Ziehpunkten oder Kreuzkappen.

Habe Spaß!