Welche Datenstruktur für Baum? (z.B. Octree, KD-tree)

[Sternkucker]

Liebe Forenmitglieder,

Ich habe eine 3D-Punktwolke mit > 100.000 Teilchen und möchte im Rahmen einer Simulation die jeweiligen Nachbarn finden. Ich habe zunächst eine einfache Schleife genommen, und für alle anderen Teilchen den Abstand berechnet. Das klappt, ist aber zu langsam. Dann habe ich mir einen Cache gebaut, der in einer Datei gesichert wird - das macht's aber nur mäßig schneller, da im Laufe der Simulation einzelne Teilchen wegfallen und der Cache dann immer weniger Trefferquote hat.

Nun habe ich gelesen, dass Baumverfahren die Suche massiv beschleunigen können - insbesondere K-D-Baum und Octree. Ich habe mir einige Texte zu KD-Bäumen durchgelesen und glaube, das Verfahren im Wesentlichen verstanden zu haben. Auch habe ich eine C++ Implementation gefunden - die verstehe ich aber nichtmal im Ansatz, wohl weil ich keinerlei Ahnung von C++ habe.

Ich möchte also so einen K-D-Baum in Delphi implementieren. Könnt ihr mir helfen, welche Datenstruktur sich dafür empfiehlt? Da stehe ich irgendwie auf dem Schlauch. Ich habe z.B. meine 3D-Datenwerte in einem array of record gespeichert, den ich mit Setlength anpasse:

Delphi-Quellcode:

star : array of record
         x : Single;
         y : Single;
         z : Single;
         s : Integer;    // Status des Punktes

So ein Baum wächst aber in alle Richtungen - in die Tiefe, und in die Breite. Mit welchem Datentyp könnte ich das abbilden? Ich habe zuerst an ein mehrdimensionales array[0..10,0..10,0..10,...] gedacht, aber man kennt im Vorhinein weder Tiefe noch Breite. Außerdem kann man sich nicht vorstellen, wo oben und unten ist, wo links und rechts Werte eingefügt bzw. gesucht werden müssen.

Ich bin vertraut mit den einfachen Datentypen aus Delphi - also records, arrays, integers, floats etc. Ich kenne Schleifen, Klassen, Units, Funktionen und Prozeduren und kann damit recht sicher umgehen. Ich habe aber z.B. noch nie etwas mit Pointern gemacht. Das nur zur Info, damit ihr meine Kenntnisse ungefähr einschätzen könnt.

Wer kann mir einen Tip geben zur Umsetzung? Danke an alle!

[mkinzler]

Dynamische Strukturen würde ich dynamisch verwalten, also nicht mit Arrays.
Für einen 3D-Raum sollte ein Octree reichen.
http://wiki.delphigl.com/index.php/Tutorial_Octree

[Sternkucker]

Cooles Tutorial. Das Programmier-Level ist halt ziemlich hoch und deutlich über meinem angesiedelt.
Kannst du mir einen Lesetip für das erwähnte "dynamische" geben? Hat das mit Pointern zu tun?

Beim Lesen des Octree ist mir aufgefallen: Im Grunde wird doch dabei der Raum in Würfel eingeteilt. Sagen wir, 10x10x10 = 1000 Würfel als Unterteilung des Gesamtraumes.

• Nun könnte ich doch eine Liste erstellen: Würfel 1 enthält Punkte 1, 2, 3,...
• Noch eine Liste: Würfel 1 grenzt an Würfel 2, 3, ... (gesamt 26)
• Man durchsuche den Ausgangswürfel und die umliegenden nach dem nächstliegenden Punkt, und weite die Suche aus falls nötig

So muss man zur Laufzeit im Idealfall nur 26 + 1 von gesamt 1000 Würfeln durchsuchen, das wäre ein Speedup von 37. Die Berechnungen, die zum Aufbau der Struktur anfallen, können im Vorfeld ablaufen, dafür steht genügend Zeit zur Verfügung.

Ist das Verfahren brauchbar? Wieviel schlechter ist es als ein Octree? Das könnte ich mit meinen Fähigkeiten wahrscheinlich gut umsetzen.