Ich möchte einen schnellen Algorithmus finden, um die x nächsten Punkte zu einem gegebenen Punkt in einer Ebene zu finden.
Wir haben es tatsächlich mit nicht zu vielen Punkten (zwischen 1.000 und 100.000) zu tun, aber ich brauche die x nächsten Punkte für jeden dieser Punkte. (wobei x normalerweise zwischen 5 und 20 liegt.)
Ich muss es in C # schreiben.
Ein bisschen mehr Kontext zum Anwendungsfall: Diese Punkte sind Koordinaten auf einer Karte. (Ich weiß, das bedeutet, dass wir nicht gerade über ein Flugzeug sprechen, aber ich hoffe, dass man sich mit Projektionsproblemen nicht herumschlagen muss.) Am Ende sollten Punkte, die viele andere Punkte in der Nähe haben, in Rot angezeigt werden, Punkte, die nicht zu viel haben nahe beieinander liegende Punkte sollten grün angezeigt werden. Zwischen diesen beiden Extremen liegen die Punkte auf einem Farbverlauf.
Was Sie brauchen, ist eine Datenstruktur, die für die Organisation von Punkten in einer Ebene geeignet ist. Der K-D-Baum wird oft in solchen Situationen verwendet. Siehe k-d Baum auf Wikipedia.
Hier habe ich eine allgemeine Beschreibung von Geometrischen Algorithmen
gefundenIch habe eine Java-Implementierung eines KD-Baumes nach C # portiert. Siehe Benutzer: Ojd / KD-Tree auf RoboWiki. Sie können den Code dort herunterladen oder direkt CySoft.Collections.zip herunterladen meine Homepage (nur Download, keine Doku).
Für einen bestimmten Punkt (nicht alle von ihnen) und da die Anzahl der Punkte nicht extrem ist, könnten Sie den Abstand von jedem Punkt berechnen:
%Vor%(Ich habe x = 20 verwendet)
Die Berechnung basiert auf Doppeln, also sollte die FPU hier einen ordentlichen Job machen können. Beachten Sie, dass Sie möglicherweise eine bessere Leistung erzielen, wenn Point eine Klasse und keine Struktur ist.
Sie müssen eine Abstandsfunktion erstellen, dann die Entfernung für jeden Punkt berechnen und die Ergebnisse sortieren und das erste x nehmen.
Wenn die Ergebnisse 100% genau sein müssen, können Sie die Standard-Distanzfunktion verwenden:
d = SQRT ((x2 - x1) ^ 2 + (y2 - y1) ^ 2)
Um das effizienter zu machen. Nehmen wir an, die Entfernung ist k. Nimm alle Punkte mit x-Koordinaten zwischen x-k und x + k. ähnlich nehmen, y-k und y + k. Sie haben also alle überschüssigen Koordinaten entfernt. Jetzt mache Abstand durch (x-x1) ^ 2 + (y-y1) ^ 2. Machen Sie einen Min-Heap von k Elementen auf ihnen, und fügen Sie sie zum Heap hinzu, wenn der neue Punkt & lt; min (Haufen). Sie haben jetzt die k minimalen Elemente im Heap.