Gibt es irgendwelche erprobten Datenstrukturen für die Punktpositionierung in Tetraedernetzen, in denen die Tetraeder alle disjunkt sind, sich aber "berühren"? I.e. Die meisten Gesichter sind Gesichter von genau zwei Tetraedern.
Nach OrtIch meine, dass ich herausfinden möchte, in welchem der Tetraeder sich ein bestimmter Punkt befindet oder ob er sich nicht in einem befindet.
Bisher habe ich es versucht:
Ein einfacher KD-Baum. Dies war viel zu langsam für meine Bedürfnisse, da die durchschnittliche Baumtiefe sehr hoch war und ich immer noch viele einzelne Tetraeder in jedem Blatt testen musste.
Ein Gitter, das alle sich überschneidenden Tetraeder für jede Zelle enthielt. Dies scheint viel besser zu funktionieren, war aber immer noch nicht schnell genug. Erstens enthielt das Gitter viele leere Zellen, weil mein Gesamtnetz nicht sehr "kastenförmig" ist. Zweitens enthielten die meisten Zellen, die tatsächlich Tetraeder enthielten, eine Menge von ihnen (10+). Ich nehme an, das liegt daran, dass viele Tetraeder sich jeden Eckpunkt teilen, und sobald ein Eckpunkt in einer Zelle ist, sind auch alle seine benachbarten Tetraeder.
Einige weitere Informationen zu den Eingabedaten: Das Netz ist normalerweise nicht konvex und kann Löcher oder Einschlüsse aufweisen. Obwohl die letzten beiden etwas unwahrscheinlich sind, muss ich mit ihnen umgehen, was "Gehen" ohne (teure und komplizierte?) Vorverarbeitung unmöglich macht.
Wenn es sich um eine 3D-Triangulation aus Tetraedern mit Nachbarschaftsinformationen handelt, können Sie einfach wandern verwenden. Dies ist eine Standardtechnik für die Punktpositionierung und verwendet 3D Orientierungstests .
Weitere Informationen finden Sie in der Publikation Wandern in einer Triangulation von Olivier Devillers et al. (Google es und Sie werden eine PDF davon finden.)
Einige schnelle Gedanken: ein Octree wird Ihrem Rasteransatz ähneln, aber Ihnen erlauben, leere Gitter schnell zu ignorieren und Gitter zu unterteilen, die zu voll sind.
Sie erwähnen auch nicht, wie Sie testen, ob ein Punkt innerhalb eines Tetraeders liegt. Es ist eine Weile her, seit ich es angeschaut habe, aber vielleicht könnten baryzentrische Koordinaten Ihre Geschwindigkeit beschleunigen Punkt-in-Tetraeder-Tests? Oder ein Sweep-Line-Algorithmus , um Tetraeder auf der Basis von Tetraeder-Scheitelpunkten, die eindeutig auf der falschen Seite der Sweep-Linie liegen, schnell auszuschließen enthält den Punkt.
Das ist zugegebenermaßen ein bisschen Brainstorming.
Vielleicht ein Brauch eines kdTree, der Flächen-ausgerichtete Ebenen anstelle von Achsen-ausgerichteten Ebenen verwendet.
Wenn ein Punkt auf der "richtigen" Seite aller vier Ebenen eines Tetraeders liegt, muss er innerhalb des Tetraeders liegen. (Richtig?) Und wenn Sie auf der falschen Seite eines Flugzeugs sind, dann können Sie nicht nur das aktuelle tet, sondern auch alle anderen auf dieser Seite des Flugzeugs ausschließen.
Es scheint, dass Sie in der Lage sein sollten, einen Baum zu bauen, bei dem jeder Knoten eine einzelne Ebene ist, und ein Blattknoten bedeutet, dass Sie sich in einer bestimmten Ebene befinden (vorausgesetzt, die Knoten schneiden sich nie). Der Baum kann tief sein, aber da jeder Test nur gegen eine Ebene ist (statt eines teureren Dreiecks-Tests) und da ein Blattknoten genau eine Antwort gibt, scheint es, als sollte es schnell sein.
Der Aufbau des Baumes kann sich als schwierig erweisen.
Tags und Links algorithm computational-geometry