Welche sortierbare Datenstruktur für Sortierung nach räumlicher Distanz
-
Ich habe eine sehr große Menge an Punktkoordinaten (mehrere Millionen Punkte aus Laserscandaten).
Jetzt möchte ich Punkte entfernen welche zu nah beieinander liegen so dass ich diese quasi ausdünne.
Dazu muss ich ja jeden Punkt mit jeweils allen anderen Punkten vergleichen und deren Abstand auswerten.
Also eine enorme Menge an Vergleichen.
Wenn man nun die Punkte sortiert wie bei einem 1D-Array kann man ja durch die Sortierung Bereiche eingrenzen welche zum Vergleich mit dem Punkt überhaupt in Frage kommen.
Allerdings habe ich ja hier nicht nur 1 Koordinate sondern 3 - wie soll ich das sortieren?
Hab mir vorgestellt eine Art Hashlist welche für die verschiedenen Bereiche des 3D-Raumes eine bestimmte Hashsumme berechnet, so dass dann nach dieser sortiert werden kann aber keine Ahnung wie man das umsetzen kann.Also konkret die Frage:
Welche Datenstruktur und welchen Aufbau nehme ich damit ich die Anzahl der nötigen Punktvergleiche effektiv verringern kann?Danke schonmal im Voraus für die Antworten.
-
-
Oder auch ein k-D-Baum. Das "nächster Nachbar"-Problem kann man damit auch lösen.
-
Dankeschön - werde mir diese Datenstrukturen mal ansehen.