Ich muss einen nächsten Nachbarn Interpolationsprogramm machen.Sortieren und Suchen von Koordinaten für die Interpolation in C++
My Eingang wäre die x, y und y-Koordinaten eines Punktes, beispielsweise x = 0,5, y = 0,3, z = 0,1
Der Ausgang am nächsten Punkt die Geschwindigkeit gemessen werden würde verfügbar. Da ich vier Vektoren x, y, z und V habe, sucht das Programm nach dem nächsten Knoten. Nehmen wir an, es ist x[5239], y[5239], z[5239] (entspricht x = .501 y = .299 z = .1) und gibt V[5239] aus.
Ich dachte über ein paar Referenzpunkte (nennen wir sie p und q). Und meine Idee ist, die Entfernung aller Knoten in Bezug auf p und q zu berechnen. Dann sortiere die Vektoren nach der Entfernung des Knotens zu p und q (dazu müsste ich einen Verweis auf den ursprünglichen Index behalten, um V[i] finden zu können). Danach könnte ich eine binäre Suche verwenden, wobei ich den Abstand des gegebenen Punktes in Bezug auf p und q benutze, um den nächsten Knoten zu finden.
Eine andere Sache, die ich fand, könnte Hash-Tabellen sein. Welches wäre effizienter, wenn die Anzahl der Elemente in meinen Vektoren ~ 96.000 ist und die Anzahl der Interpolationen, die ich ausführen muss, auch so viele sein kann.
Wie würde ich die Indizes (wie die Matlab-Sortierfunktion) im Auge behalten? Welche Art von Sortieralgorithmus würden Sie in diesem Fall empfehlen?
Danke
Ich denke, Sie wären viel besser dran mit einem [octree] (https://en.wikipedia.org/wiki/Octree). Beachten Sie, dass sich der "nächste Nachbar" eines bestimmten Punkts möglicherweise nicht in derselben Zelle befindet - Sie müssen also benachbarte Zellen berücksichtigen. –
https://en.wikipedia.org/wiki/Spatial_database#Spatial_index kann auch eine gute Quelle sein. –
Ich würde Ihren Beitrag verwenden, um mit der Codierung zu beginnen, und wenn es Fehler gibt, dann kann es – efekctive