Algorithmus zum Finden von Punkten in der Nähe?

Question

Bei einem Satz von mehreren Millionen Punkten mit x, y-Koordinaten ist der Algorithmus der Wahl, um schnell die Top 1000 der nächstgelegenen Punkte von einem Ort zu finden. "Schnell" bedeutet hier ungefähr 100ms auf einem Heimcomputer.

Brute Kraft würde bedeuten, Millionen von Multiplikationen zu tun und sie dann zu sortieren. Während dies in nur einer einfachen Python-App in weniger als einer Minute möglich ist, ist es für eine interaktive Anwendung immer noch zu lang.

Die Bounding Box für die Punkte wird bekannt sein, so dass die Partitionierung in ein einfaches Raster möglich wäre. Die Punkte sind jedoch etwas ungleich verteilt, daher vermute ich, dass die meisten Gitterquadrate leer sind und plötzlich einige von ihnen einen großen Teil der Punkte enthalten würden.

Edit: Muss nicht genau sein, kann tatsächlich sehr ungenau sein. Es wäre keine große Sache, wenn die Top 1000 tatsächlich nur einige zufällige Punkte von den Top 2000 wären.

Bearbeiten: Satz von Punkten ändert sich selten.

Answer 1

Wie wäre es mit quadtree?

Sie teilen Bereich Rechtecke, wenn der Bereich mit niedriger Dichte von Punkten hat, sind Rechtecke groß, und wenn der Bereich hoher Dichte von Punkten hat, werden Rechtecke klein sein. Sie unterteilen jedes Rechteck rekursiv in vier Unterrechtecke, bis die Rechtecke klein genug sind oder wenige Punkte enthalten.

Sie können dann beginnen, Punkte in Rechtecken in der Nähe des Ortes zu betrachten und nach außen zu gehen, bis Sie Ihre 1000 Punkte gefunden haben.

Code dafür könnte etwas komplex werden, also sollten Sie vielleicht zuerst mit dem einfachen Gitter versuchen und sehen, ob es schnell genug ist.

Answer 2

Quadtrees sind nett, aber BSP trees sind garantiert in O (log n) Zeit laufen. Ich denke, Quadtrees erfordern ein endliches Begrenzungsvolumen, und es gibt einige degenerierte Fälle, in denen Quadtrees kläglich versagen, beispielsweise wenn eine große Anzahl von Punkten den gleichen relativ kleinen Platz einnehmen.

Das gesagt, Quadretrees sind wohl einfacher zu implementieren und ziemlich effektiv in den meisten gängigen Situationen. UPS verwendet diese Algorithmen in ihren Routing-Algorithmen, da diese Nachteile in der Praxis keine größeren Probleme darstellen, wahrscheinlich weil Städte sich in der Region von Interesse ausbreiten.

Answer 3

Ich nehme an, dass die Punkte in einer Datenbank oder einem durchsuchbaren indizierten Speicherort sind? Wenn es so ist, sollte es ziemlich schnell sein. Von dem gegebenen Punkt aus können Sie einen Bereich auf der x- und y-Achse haben und alle Positionen innerhalb dieses Bereichs erhalten (dh die obere linke Ecke x (a) und y (b) und die rechte untere Ecke x (c) und y angeben) (d)).

Dann eine Abfrage, wo für Punkte, wo y> = b UND y < = d UND x> = a UND x < = c. Dies wird schnell davon ausgehen, dass Sie Indizes für die x- und y-Koordinaten separat haben. (angenommen, der Ursprung ist 0,0 oben links).

Sie können diesen Bereich dann um z erhöhen (oder verringern, wenn das Ergebnis sehr groß ist), bis die Anzahl der Punkte in der Ergebnismenge> = 1000 ist. Durch einige Testläufe sollten Sie eine Standardabweichung und andere statistische Zahlen, mit denen Sie die Größe des Rechtecks ​​bestimmen können, mit dem Sie beginnen möchten. Ihr Programm kann sich auch selbst darauf einstellen, basierend auf den Ergebnissen, die es erhält.

Sobald Sie die groben Daten festgelegt haben, ist es ziemlich einfach, die Entfernung zwischen jedem Punkt und dem Quellpunkt zu berechnen.

Answer 4

Sie möchten eine Struktur wie einen Quadbaum oder einen RTree verwenden. Dies sind multidimensionale Indexstrukturen.

Der Schlüssel verwendet eine gute "raumfüllende Kurve", die hilft, die Nähe von Punkten zu definieren. Eine einfache raumfüllende Kurve ist eine Zoder, aber Sie wären eher an einer Hilbert-Kurve interessiert.

http://en.wikipedia.org/wiki/Space_filling_curve

Ich weiß nicht von irgendwelchen vorverpackten Implementierungen dieses Zeug. Ich habe vor kurzem meinen eigenen RTree in 2 Dimensionen implementiert, der nur Massenladen und Suchen unterstützt (über eine bereitgestellte Begrenzungsbox).

Ein Nachteil hier ist, dass Ihre Punkte in einer endlichen Region enthalten sein müssen. Dort gibt es raumfüllende Kurven, die für nicht endliche Räume funktionieren, von denen ich aber nichts weiß.

Answer 5

Wenn sich die Menge der Punkte selten ändert, können Sie auch ein Voronoi-Diagramm verwenden. Ich bin mir nicht sicher, ob das hilft, den ersten Punkt schneller zu finden, aber es sollte es viel einfacher machen, die nächsten 999 Punkte zu finden.

Answer 6

Zusätzlich zu den QuadTree und BSP-Baum-Vorschlägen sollten Sie nearest neighbour searching nachschlagen. Die Auswahl des Algorithmus hängt davon ab, wie oft Sie das Basisdatenset hinzufügen. Wenn Sie häufig hinzufügen und entfernen, sind Baumlösungen überlegen. Wenn die Daten statischer sind, können Suche nach Nächsten und Voronoi-Diagramme viel schneller und besser skalieren.

Answer 7

ich weiß, es wurde gesagt, als sei nicht der schnellste, wenn Sie WIRKLICH schnelle Ergebnisse wollen, indem ich diesen Beitrag von google gefunden habe, dachte ich, dass ich meine SQL-Lösung hinzufügen würde, die ich vor einiger Zeit in Form einer gespeicherten verwendet habe Proz. Es sucht nach Orten in der Nähe der Koordinate und gibt sie nach Entfernung zurück.

Ich hoffe, es hilft jemand :)

CREATE PROCEDURE [dbo].[getstores] @lat float, @lng float AS 
DECLARE @radius float, @DegToRad float 
SET @DegToRad = 57.29577951 
SET @radius = 25000 
SELECT TOP 10 
    name 
    ,sto_lat 
    ,sto_lng 
    ,postcode 
    ,ROUND((ACOS((SIN(@lat/57.2958) * SIN(sto_lat/@DegToRad)) +(COS(@lat/@DegToRad) * COS(sto_lat/@DegToRad) *COS(sto_lng/@DegToRad - @lng/@DegToRad))))* 6387.7, 2) AS distance 
FROM store 
WHERE (sto_lat >= @lat - (@radius/111)) 
And (sto_lat <= @lat + (@radius/111)) 
AND (sto_lng >= @lng - (@radius/111)) 
AND (sto_lng <= @lng + (@radius/111)) 
AND (
    ISNUMERIC(sto_lat) = 1 
    AND 
    ISNUMERIC(sto_lat) = 1 
) 
ORDER BY distance 

ANMERKUNG: Ich habe bereits erklärt, dass dies für diese Frage nicht die beste Lösung ist einfach vielleicht für jemanden, der diese auf Google wie mich