Hallo

Ich habe mal wieder ein kleines Problem, für das ich eine schnelle Lösung brauche:
Zur Zeit arbeite ich an einer Datenstuktur, mit der ich in einer Punktwolke schnell nach dem Nachbarn eines gegebenen Punkts suche. Dafür unterteile ich den Raum in kleine Würfel. Wenn ich nun einen Punkt habe, kann ich in konstanter Zeit bestimmen, in welchem Würfel er sich befindet. Wenn ich in diesem Würfel keine Nachbarn finde, suche ich in den 27 umliegenden Würfeln und danach in den 37, die die nachste Hülle bilden.

Leider habe ich bisher keinen Ausdruck gefunden, der mit die Koordinaten der jeweiligen Hüllen ausgibt. Für die erste Hülle also etwas wie (-1,-1,-1),(-1,-1,),..., also im Endeffekt (-1,-1,-1) bis (1,1,1) ausser der (0,0,0), da ich den Würfel schon durchsucht habe. Bei der nächsten Hülle wirds dann ähnlich, also (-2,-2,-2)...(2,2,2) ausser den Tuppeln, in denen keine 2 (oder -2) vorkommt.

Bisher berechne ich alle Tuppel und prüfe dann, ob der Maximalwert stimmt. Das ist wahrscheinlich nicht die schnellste Methode, also wollte ich euch fragen, ob ihr eine Möglichkeit kennt, ohne grosse Tests, diese Relaivkoordinaten in Abhängigkeit der Hülle zu berechnen.

Nikolas