Algorithmus zum Finden von Punkten in der Nähe?

StackOverflow https://stackoverflow.com/questions/838344

Frage

Welcher Algorithmus ist bei einem Satz von mehreren Millionen Punkten mit XY-Koordinaten der beste Algorithmus, um schnell die 1000 nächstgelegenen Punkte von einem Standort aus zu finden?„Schnell“ bedeutet hier etwa 100 ms auf einem Heimcomputer.

Brutale Gewalt würde bedeuten, Millionen von Multiplikationen durchzuführen und diese dann zu sortieren.Während selbst eine einfache Python-App dies in weniger als einer Minute erledigen könnte, ist es für eine interaktive Anwendung immer noch zu lang.

Der Begrenzungsrahmen für die Punkte ist bekannt, sodass eine Aufteilung des Raums in ein einfaches Raster möglich wäre.Allerdings sind die Punkte etwas ungleichmäßig verteilt, sodass ich vermute, dass die meisten Gitterquadrate leer wären und dann plötzlich einige von ihnen einen großen Teil der Punkte enthalten würden.

Bearbeiten:Muss nicht genau sein, kann tatsächlich ziemlich ungenau sein.Es wäre keine große Sache, wenn die Top 1000 beispielsweise nur ein paar zufällige Punkte aus den Top 2000 wären.

Bearbeiten:Die Punktemenge ändert sich selten.

War es hilfreich?

Lösung

Wie wäre es mit Quadtree ?

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

Sie können dann beginnen an den Punkten in Rechtecken in der Nähe der Stelle suchen, und nach außen verschieben, bis Sie Ihre 1000 Punkte gefunden zu haben.

-Code dafür könnte etwas komplex, vielleicht sollten Sie zunächst mit dem einfachen Gitter versuchen und sehen, ob es schnell genug ist.

Andere Tipps

Quadtrees sind nett, aber BSP Bäume in O (log n) Zeit garantiert laufen . Ich denke, Quadtrees erfordert ein endlichen Begrenzungsvolumen, und und es gibt einige Fälle, in denen degenerierten Quadtrees kläglich scheitern, wie wenn eine große Anzahl von Punkten den gleichen relativ kleinen Raum einnehmen.

Dass gesagt wird, Quadtrees ist wohl einfacher zu implementieren und sehr effektiv in den meisten alltäglichen Situationen. Es ist, was UPS in ihren Routing-Algorithmen verwendet, weil es der Nachteile nicht erhebliche Probleme in der Praxis darstellen können, wahrscheinlich, weil Städte neigen dazu, über die Region von Interesse verteilt werden.

Sie möchten eine Struktur wie ein Quad Baum verwenden, oder eine RTree. Dies sind mehrdimensionale Indexstrukturen.

Der Schlüssel ist eine gute „raumfüllende Kurve“ verwendet wird, das ist, was die Nähe von Punkten definieren hilft. Eine einfache raumfüllende Kurve ist eine Zorder, aber Sie würden wie eine Hilbert-Kurve in etwas mehr interessiert.

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

Ich weiß nicht, von irgendwelchen vorverpackten Implementierungen dieses Zeug. Ich implementierte vor kurzem meine eigene RTree in zwei Dimensionen, die nur Bulkbeladung und sucht (über einen vorgesehenen Begrenzungsrahmen) unterstützt.

Ein Nachteil hierbei ist, dass Sie Ihre Punkte haben in einem endlichen Bereich enthalten sein. Es weiß, dass es raumfüllende Kurven, die für Räume arbeiten, die nicht endlich sind, aber ich weiß nichts über sie.

Neben den Quadtree und BSP Baum Vorschläge, sollten Sie nachschauen nächsten Nachbarn suchen . Die Wahl des Algorithmus basiert darauf, wie oft Sie Ihre Basis-Datensatz hinzufügen. Wenn Sie das Hinzufügen und Entfernen oft sind Baum Lösungen überlegen. Wenn die Daten mehr statisch ist, nächste Nachbar der Suche und voronoi Diagramme können besser viel schneller und skaliert werden.

Wenn die Menge der Punkte selten ändert, könnten Sie auch ein Voronoi-Diagramm betrachten verwenden. Ich bin nicht sicher, ob das hilft der Suche nach dem zuerst Punkt schneller, aber es sollte es viel einfacher, die nächsten 999 Punkte zu finden.

Ich gehe davon aus, dass sich die Punkte in einer Datenbank oder an einem durchsuchbaren indizierten Ort befinden?Wenn ja, sollte es ziemlich schnell gehen.Von dem angegebenen Punkt aus können Sie einen Bereich auf der x- und y-Achse festlegen und alle Standorte innerhalb dieses Bereichs ermitteln (d. h.Geben Sie die obere linke Ecke x(a) und y(b) und die unterste rechte Ecke x(c) und y(d) an.

Führen Sie dann eine Abfrage für Punkte durch, bei denen y >= b UND y <= d UND x >= a UND x <=c.Dies geht schnell, vorausgesetzt, Sie haben separate Indizes für die X- und Y-Koordinaten.(vorausgesetzt, der Ursprung ist oben links 0,0).

Anschließend können Sie diesen Bereich um z vergrößern (oder verkleinern, wenn das Ergebnis sehr groß ist), bis die Anzahl der Punkte in der Ergebnismenge >= 1000 beträgt.Durch einige Probeläufe sollten Sie in der Lage sein, eine Standardabweichung und andere statistische Zahlen zu ermitteln, anhand derer Sie zunächst die Größe des Rechtecks ​​bestimmen können.Ihr Programm kann sich basierend auf den erzielten Ergebnissen auch selbst darauf einstellen.

Sobald Sie den groben Datensatz haben, ist es ziemlich einfach, den Abstand zwischen jedem Punkt und dem Quellpunkt zu berechnen.

Ich weiß, ihr gesagt worden, nicht die schnellste ist, wenn man wirklich von wirklich wollen schnelle Ergebnisse sehen ich diesen Beitrag von Google fand ich dachte, dass ich meine SQL-Lösung hinzufügen würde, die ich in Form einer gespeicherten proc vor einer Weile verwendet . Es sucht nach Standorten in der Nähe von der einen coord und gibt sie nach Entfernung.

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

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

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top