N-dimensionale Delaunay Tesselation Software-Bibliotheken

10

Ich habe eine Reihe bekannter Punkte / Knoten, die im N-dimensionalen Raum unregelmäßig verteilt sind (N> = 2), und ich möchte eine Möglichkeit, die Delaunay-Triangulation dieser Punkte zu generieren und die entsprechenden Elemente zurückzugeben.

Gibt es vorhandene Vernetzungsbibliotheken, die eine ND Delaunay-Triangulation durchführen?

(Ich mache das, weil ich die vermaschten Elemente als Grundlage für die lineare Interpolation an jedem Punkt im Raum verwenden möchte. Meine Dimension wird derzeit von einer C ++ - Klasse behandelt, die über Dimensionen erstellt wird, wenn dies einen Unterschied zu Vorschlägen macht ...)

computational-geometry high-dimensional mesh-generation delaunay-triangulation unstructured-mesh Mirams
quelle
Hallo Mirams, und willkommen bei scicomp! Diese Frage könnte
Paul
Vielen Dank für den Link, ich hatte gehofft, nicht meinen eigenen Mesher schreiben zu müssen. Tetgen (für 3D) führt viele Codezeilen aus. Es scheint ein Problem zu sein, das oft gelöst worden sein muss.
Mirams
beliebte Frage ... auch scicomp.stackexchange.com/questions/7664/…
Clipper
Die Delaunay-Triangulation wird typischerweise von der konvexen Hülle im höherdimensionalen Raum abgeleitet. Siehe die Bemerkung qhull unten.
Meawoppl
3D ist nicht so schwer, aber für 4D ist es extrem schwierig beim Verfeinern. Ich habe eine Frage zu MathOverflow gestellt, aber noch keine Antwort: mathoverflow.net/questions/130878/…
Shuhao Cao

Antworten:

4

Ich denke, Sie können dies mit einer konvexen Rumpfsoftware (z. B. QHull) über den Hebealgorithmus tun. Zumindest scheint die Dokumentation von matlabs "delaunayn" -Befehl dies anzuzeigen.

rchilton1980
quelle
2
4D getestet, und das scheint in QHull gut zu funktionieren (ich benutze es über scipy.spatial in Python).
Ethan Coon
1
Sie werden qhull nicht schlagen. Ich habe in via Scipy auch in bis zu 6 Dimensionen verwendet.
Meawoppl
Hmmm - dies von qhull.org/news/qhull-news.html ist nicht ideal: "Alle Benutzer In 3D und höher erzeugt die Option 'Qt' keine konformen Triangulationen für benachbarte, nicht einfache Facetten. Zum Beispiel Wenn Sie ein reguläres 3-D-Array von Eingabestellen haben, besteht die Delaunay-Triangulation aus Würfeln. Mit der Option 'Qt' wird jeder Würfel in Tetraeder trianguliert. Innerhalb jedes Würfels ist die Triangulation konsistent, aber nicht unbedingt zwischen benachbarten Würfeln konsistent [C. Bertoglio; C. de Visser]. Wie dieses Problem behoben werden kann, ist unbekannt. " Einen Versuch wert, ich werde sehen, wie es mir geht.
Mirams
5

Diese Funktion scheint in CGAL verfügbar zu sein

Juan M. Bello-Rivas
quelle
Das sieht auch gut aus. Ich werde sowohl Qhull als auch dies versuchen. Danke für die Vorschläge.
Mirams
0

Ich habe auch distmesh in Matlab gefunden, das dies zu können scheint:

Distmesh Homepage

Es führt Tesselationen für Finite-Elemente-Netze (über QHull) durch, bietet jedoch eine schöne Schnittstelle zum Definieren von Bereichen / Oberflächen basierend auf Abstandsfunktionen. Besser für Fälle, in denen Sie eine Oberfläche mathematisch definieren möchten und sich nicht darum kümmern, wo sich die internen Knoten befinden.

Mirams
quelle