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!