Ich habe eine Menge von Punkten (1 Million davon, möglicherweise in der Zukunft, wie 10 oder 100 Millionen) im 3D-Raum, die eine Kugel bilden (sie füllen die Kugel - sie sind nicht nur auf der Oberfläche) und Ich würde gerne die Tetraeder bauen, die jede Kugel mit ihren ersten Nachbarn verbinden ... Auf der Suche nach der Tetraederisierung ist alles, was ich bisher gefunden habe:
Wie kann ich das tun?
2014-08-09 zuerst von, vielen Dank für Ihre Vorschläge! Ich war - und bin immer noch - in den Ferien und war nur vorbei, um zu überprüfen, ob jemand geantwortet hatte ... Ich bin nicht enttäuscht !!! :-) Ich schätze, ich werde zuerst CGAL versuchen und von dort aus sehen. Ich habe andere Datenberechnungen für die gleiche Menge von Punkten in O (n2), von denen ich annehme, dass sie ungefähr 1 Woche dauern wird, also wären ein paar Stunden nicht so schlecht. Minuten wären ein wahr gewordener Traum!
Sie suchen nach einem Delaunay-Triangulation -Algorithmus im 3-Raum.
Ich hoffe, es macht Ihnen nichts aus, eine Weile zu warten, denn eine Delaunay-Triangulation von 100 Millionen Punkten wird ziemlich lange dauern.
qhull hat eine n-dimensionale Delaunay-Implementierung, die Sie vielleicht ausprobieren würden. So auch CGAL . Beide Pakete berechnen die Delaunay-Triangulation in O (n log (n)) asymptotischer Zeit, und CGAL kann dies bei einer geeigneten Auswahl von Geometriekernen auf eine numerisch robuste Weise tun. (Das heißt, es kann automatisch zu einer exakten Arithmetik für jene Berechnungen wechseln, bei denen eine ungenaue Arithmetik ein unsicheres Ergebnis erzeugt.)
Ich würde nicht empfehlen, selbst in zwei Dimensionen eine schnelle Delaunay-Triangulation zu implementieren. Erschreckende Dinge können passieren, wenn Sie Prädikate für die Ergebnisse der Arithmetik auswerten müssen.
Tags und Links algorithm c++ mesh computational-geometry tetrahedra