Ich habe eine Liste von ~ 5000 Punkten (angegeben als Längen- / Breitengradpaare), und ich möchte die nächsten 5 Punkte zu einem anderen Punkt finden, der vom Benutzer angegeben wurde.
Kann jemand einen effizienten Algorithmus vorschlagen, um das herauszufinden? Ich implementiere das in Ruby, also wenn es eine passende Bibliothek gibt, dann wäre das gut zu wissen, aber ich bin immer noch am Algorithmus interessiert!
UPDATE: Einige Leute haben nach genaueren Details zu dem Problem gefragt. Also hier geht es:
Sie können einen sehr schnellen Schätzer für die obere Grenze auf Distanz mit Manhattan-Entfernung (skaliert für den Breitengrad) erhalten. Dies sollte gut genug sein, um 99,9% der Kandidaten abzulehnen, wenn sie nicht nahe sind (EDIT : Seit damals sagst du uns, dass sie nah sind. In diesem Fall sollte deine Metrik distanziert sein, wie von Lars H angemerkt). Betrachten Sie das Äquivalent, um etwas außerhalb einer sphärischen Rechteck-Bounding-Box (als eine Annäherung an eine Kreis-Bounding-Box) abzulehnen. Ich mache Ruby nicht, also ist hier Algorithmus mit Pseudocode:
Geben Sie den Breitengrad, den Längengrad Ihres Referenzpunkts P (pa, po) und den anderen Punkt X (xa, xo) an. Precompute ka , der Breitengradfaktor für Längsdistanzen: ka (= cos (pa in °)) . (Streng genommen ist ka = Konstante eine linearisierte Näherung in der Nähe von P.)
Dann ist der Entfernungsschätzer: D(X,P) = ka*|xa-pa| + |xo-po| = ka*da + do
wobei | z | bedeutet abs (z). Im schlimmsten Fall überschätzt dies die wahre Distanz um einen Faktor von √2 (wenn da == do), daher berücksichtigen wir das wie folgt:
Machen Sie eine laufende Suche und behalten Sie Dmin, die fünftkleinste skalierte Manhattan-Entfernungsschätzung. Daher können Sie alle Punkte, für die D (X, P) & gt; √2 * Dmin (da sie mindestens weiter entfernt sein müssen als √ ((ka * da) ² + do²) - das sollte 99,9% der Punkte eliminieren). Behalten Sie eine Liste aller verbleibenden Kandidatenpunkte mit D (X, P) & lt; = √2 * Dmin. Aktualisieren Sie Dmin, wenn Sie eine neue fünftkleinste D-Prioritätswarteschlange oder eine Liste gefunden haben (Koord, D) sind gute Datenstrukturen. Beachten Sie, dass wir niemals die euklidische Entfernung berechnet haben, sondern nur die Multiplikation und Addition von Gleitkommazahlen.
(Betrachten wir Quadtree als ähnlich, außer dass wir alles ausfiltern, außer die Region, die uns interessiert, daher brauchen wir keine exakten Entfernungen im Voraus zu berechnen oder die Datenstruktur aufzubauen.)
Es würde helfen, wenn Sie uns die erwartete Ausbreitung in Breiten- und Längengraden (Grad, Minuten oder was?) mitteilen würden. Wenn alle Punkte nahe beieinander liegen, wird der Faktor √2 in diesem Schätzer zu konservativ sein und jeden Punkt als Kandidat markieren; ein Nachschlagetabellenbasierter Entfernungsschätzer wäre vorzuziehen.)
Pseudocode:
%Vor%Sie könnten die Suche beschleunigen, indem Sie den 2D-Raum mit einem Quadbaum oder einem kd-tree und dann, sobald Sie einen Blattknoten erreicht haben, vergleichen Sie die verbleibenden Entfernungen nacheinander, bis Sie die nächste Übereinstimmung gefunden haben.
Siehe auch diesen Blogbeitrag , der sich auf dieser andere Blogbeitrag , der beide die Suche nach nächsten Nachbarn mit kd-Bäumen in Ruby.
Da Ihre Liste ziemlich kurz ist, würde ich Brute-Force sehr empfehlen. Vergleichen Sie einfach alle 5000 mit dem benutzerdefinierten Punkt. Es wird O (n) sein und du wirst bezahlt.
Ansonsten sind ein Quad-Tree oder Kd-Baum die üblichen Ansätze zur räumlichen Unterteilung. Aber in Ihrem Fall werden Sie eine lineare Anzahl von Einfügungen in den Baum machen, und dann eine konstante Anzahl von logarithmischen Suchvorgängen ... ein bisschen eine Verschwendung, wenn Sie wahrscheinlich besser dran sind, nur eine lineare Anzahl von Distanzvergleiche und damit fertig sein.
Nun, wenn Sie die N nächsten Punkte finden wollen, suchen Sie nach den berechneten Entfernungen und nehmen das erste N, aber das ist immer noch O (n log n) ish.
BEARBEITEN: Es ist erwähnenswert, dass sich das Erstellen des räumlichen Baums lohnt, wenn Sie die Liste der Punkte für mehrere Abfragen erneut verwenden möchten.
Anstelle von reiner Brute-Force würde ich für 5000 Knoten die einzelnen x + y-Abstände für jeden Knoten und nicht den Abstand für die gerade Linie berechnen.
Sobald Sie diese Liste sortiert haben, wenn z. x + y für den 5. Knoten ist 38, Sie können jeden Knoten ausschließen, bei dem x oder y Abstand ist & gt; 38. Auf diese Weise können Sie viele Knoten ausschließen, ohne die Entfernung der geraden Linie berechnen zu müssen. Brute-Force berechnet dann den Abstand der geraden Linie für die verbleibenden Knoten.
Diese Algorithmen sind nicht einfach zu erklären, daher werde ich nur einige Hinweise in die richtige Richtung geben. Sie sollten nach Voronoi-Diagrammen suchen. Mit einem Voronoi-Diagramm können Sie leicht einen Graph in O (n ^ 2 log n) Zeit vorberechnen und den nächsten Punkt in O (log n) Zeit suchen.
Vorberechnung ist mit einem Cron-Job in der Nacht und die Suche ist live. Dies entspricht Ihrer Spezifikation.
Nun könntest du die k-engsten Paare von jedem deiner 5000 Punkte speichern und dann von dem nächsten Punkt aus dem Voronoi-Diagramm beginnen und die restlichen 4 Punkte suchen.
Aber seien Sie gewarnt, dass diese Algorithmen nicht sehr einfach zu implementieren sind.
Eine gute Referenz ist:
Da Sie diese wenigen Punkte haben, würde ich eine Brute-Force-Suche empfehlen, bei der alle Punkte gegeneinander mit einer Operation O(n^2) , mit n = 5000 oder etwa 25/2 Millionen Iterationen getestet werden eines geeigneten Algorithmus und speichern nur die relevanten Ergebnisse. Dies hätte eine Ausführungszeit von unter 100 ms in C, so dass wir höchstens ein oder zwei Sekunden in Ruby suchen.
Wenn der Benutzer einen Punkt auswählt, können Sie Ihre gespeicherten Daten verwenden, um die Ergebnisse in konstanter Zeit anzuzeigen.
BEARBEITEN Ich habe Ihre Frage erneut gelesen und es scheint, als ob der Benutzer seinen eigenen letzten Punkt angibt. In diesem Fall ist es schneller, eine O(n) lineare Suche durch Ihr Set durchzuführen, sobald der Benutzer einen Punkt angibt.
Wenn Sie dies mehrfach mit verschiedenen vom Benutzer eingegebenen Orten wiederholen müssen, aber keine Quad-Struktur implementieren möchten (oder keine Bibliotheksimplementierung finden können), können Sie ein lokalisierungssensitives Hashing verwenden ( Art von Ansatz, der ziemlich intuitiv ist:
dann, wenn ein Punkt gegeben ist (X, Y),
Sie sagen nur, dass ein nahegelegener Punkt einen ähnlichen x- und einen ähnlichen y-Wert haben muss ...