Konstruieren der Kontur eines Polygons (insbesondere eine Triangulation)

Question

Wie würde ich mich über die Kontur des 2d Polygon konstruieren, die nur Dreiecken gebildet wird, und es kann Löcher aufweisen und die Außenkontur kann konkav / konvex sein und die Löcher können auch konkav / konvex sein.

Von dem, was lese ich hier es scheint, dass es genau das Gegenteil von der Triangulation Problem. Kennen Sie Artikel, diese Art von Problem behandeln?

Sind Octrees / Quadtrees auf diese relevant?

Answer 1

Ich denke, dass Sie Daten in Form von Sätzen von drei Punkten haben, die ein „gefüllt“ Dreieck bildet, dass diese Dreiecken entlang der Kanten angrenzen, und dass alle Ecken, die Ecken der kompletten Form sein wird, sind auch Eckpunkte alle Dreiecke, die diesen Punkt berühren. Sie würden dann müssen nur alle Kanten finden, die nicht verdoppelt werden, das heißt nicht gehören zu zwei nebeneinander liegenden Dreiecken.

Answer 2

Ich glaube, Sie Ihr Problem durch die Schaffung eine topologischen Datenstruktur lösen kann Ihren Satz von Dreiecken zu stellen, und dann diese Struktur mit, um über die Dreieckskanten zu durchlaufen, die an der Grenze liegen.

Zum Beispiel: Sie können eine Halfedge-Datenstruktur erstellen. Sie halfedges sogar an der Grenze (richtig), Iterieren über die Begrenzungskontur einfügen Unter der Annahme, ist so einfach wie ein Halfedge auf der Grenze lokalisieren und dann über das Iterieren es ist „next“ Zeiger, bis Sie zum Halfedge Sie von den ersten Schritten zurück.

Ähnlich halfedges, können Sie andere topologische Strukturen wie geflügelte-Kante, etc. verwenden, aber das Konzept ist das gleiche.