Vergleich von Lat Lange Koordinaten

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

  •  09-06-2019
  •  | 
  •  

Frage

Ich habe eine Liste von mehr als 15 tausend latitude und Länge Koordinaten.Gegeben X,Y-Koordinaten, was ist der Schnellste Weg, um die nächsten Koordinaten auf der Liste?

War es hilfreich?

Lösung

Sie wollen eine geometrische Konstruktion einer Voronoi-Diagramm.Dies teilt die Ebene in einer Reihe von Bereichen, eine für jeden Punkt, umfassen alle Punkte, die am nächsten sind für jedes Ihrer Punkte gegeben.

Der code für die exakte algorithmen zu erstellen, das Voronoi-Diagramm und ordnen Sie die Daten-Struktur-lookups sind zu groß, um fit in diesem kleinen edit-box.:)

@Linor:Das ist im wesentlichen, was Sie tun würde, nach der Erstellung eines Voronoi-Diagramm.Aber anstatt ein rechteckiges raster, Sie können wählen, Trennlinien, die eng mit dem Linien des Voronoi-Diagramm (auf diese Weise erhalten Sie weniger Bereiche, cross Trennlinien).Wenn Sie rekursiv teilen Sie Ihre Voronoi-Diagramm in der Hälfte entlang der besten Trennlinie für jeden unterdiagramm, Sie können dann die Baum-Suche für jeden Punkt, den Sie nachschlagen möchten.Dies erfordert etwas Arbeit nach vorne, aber spart Zeit später.Jede lookup würde in der Größenordnung von log N, wobei N die Anzahl der Punkte.16 Vergleiche ist viel besser als 15.000!

Andere Tipps

Ich habe das mal für eine Website.I. e.finden Sie den Händler innerhalb von 50 Meilen von zip-code.Verwendet habe ich das der Großkreis-Berechnung zu finden, die Koordinaten, die 50 Meilen nach Norden, 50 km östlich, 50 km südlich, und 50 km westlich.Das gab mir eine min-und max-lat und eine min und max lang.Von dort aus dann habe ich eine Datenbank Abfrage: 

select *
    from dealers
    where latitude  >= minlat
      and latitude  <= maxlat
      and longitude >= minlong
      and longitude <= maxlong

Seit einiger Ergebnisse werden immer noch mehr als 50 Meilen entfernt, dann habe ich die großen Kreis Formel einmal mehr auf, dass kleine Liste von Koordinaten.Dann druckte ich die Liste zusammen mit dem Abstand von der Ziel.

Natürlich, wenn Sie wollte, um die Suche für Punkte in der Nähe des internationalen Datum Linie oder die Polen, als dies nicht funktioniert.Aber es funktioniert für die sucht im inneren Nord-America!

Das Allgemeine Konzept die du beschreibst ist nächste-Nachbar-Suche, und es gibt eine ganze Reihe von Techniken, die sich mit der Lösung dieser Art von Abfragen, die entweder genau oder ungefähr.Die grundlegende Idee ist, eine räumliche Partitionierung Technik zur Reduzierung der Komplexität von O(n) pro Abfrage (ungefähr) O( log n ) pro Abfrage.

KD-Bäume, und die Varianten der KD-Bäume scheinen sehr gut zu funktionieren, aber quad-Bäume wird auch funktionieren.Die Qualität dieser Suche hängt davon ab, ob Sie Ihren Satz von 15.000 Datenpunkte statisch sind (Sie sind nicht hinzufügen viel von Datenpunkten, um die Referenz-set).Mount und Arya Arbeit auf dem Approximate Nearest Neighbour die Bibliothek ist sowohl einfach zu verwenden und zu verstehen, auch ohne eine gute Erdung in der Mathematik.Es gibt Ihnen auch eine gewisse Flexibilität in der Art und Toleranzen Ihrer Anfragen.

Vielmehr kommt es so oft wie Sie möchten, es zu tun, und welche Ressourcen vorhanden sind - wenn Sie einmal den test, dann die O(log N) Techniken sind gut.Wenn Sie es tausend mal auf einem server, den Bau einer bitmap-lookup-Tabelle würde schneller sein, entweder die direkt oder als eine erste Stufe von.2 GB bitmap abbilden kann, die ganze Welt-lat-lon, um eine 32bit-Wert in 0.011 Grad Pixel (1,2 km am äquator), und sollte passen in den Speicher.Wenn Sie nur eine einzige Land-oder ausschließen können, die Pole, Sie können eine kleinere Karte oder höhere Auflösung.Für 15.000 Punkte haben Sie wahrscheinlich eine viel kleinere Karte - ich-erste Größe, welche als einen ersten Schritt zu tun, lat-lon-to-PLZ-Suche, die erfordern eine höhere Auflösung.Je nach Anforderung verwenden Sie die zugeordnete Wert zeigen das Ergebnis direkt, oder zu kurze Liste der Kandidaten (die es erlauben würde, eine kleinere Karte, erfordert aber größere Weiterverarbeitung - Sie sind nicht in O(1) lookup Gebiet mehr).

Sie nicht angeben, was Sie bedeutete die Schnellste.Wenn Sie erhalten möchten die Antwort schnell ohne code schreiben zu müssen, ich würde die gpsbabel radius filter ein zu gehen.

Basierend auf Ihren wünschen, würde ich verwenden Sie eine geometrische Datenstruktur wie ein KD-Baum in einem R-Baum.MySQL hat eine RÄUMLICHE Daten, die Art, die dies tut.Andere Sprachen/frameworks/Datenbanken haben Bibliotheken, die dies unterstützen.Im Grunde, wie eine Daten-Struktur bettet die Punkte in einem Baum von Rechtecken, und sucht in der Struktur mit einem radius.Dies sollte schnell genug sein, und ich glaube, dass ist einfacher als der Bau einer Voronoi-Diagramm.Ich denke, es ist eine Schwelle, oberhalb derer Sie würden es vorziehen, die Hinzugefügt Leistung von einem Voronoi-Diagramm, so dass Sie bereit sein werden zu zahlen die zusätzliche Komplexität.

Dies kann gelöst werden in mehrere Möglichkeiten.Ich würde den ersten Ansatz dieses problem durch die Erzeugung eines Delaunay Netzwerk anschließen nächsten Punkte zu einander.Dies kann erreicht werden, mit der v. delaunay-Befehl in der open-source-GIS-Anwendung GRAS.Sie könnten vollständig das problem im GRAS mit den vielen network analysis Module im GRAS.Alternativ können Sie den kostenlosen Geo-RDBMS PostGIS zu tun die Entfernung Abfragen.Die PostGIS-spatial-Abfragen sind deutlich leistungsfähiger als die in MySQL, so sind Sie nicht gezwungen, BBOX Operationen.Zum Beispiel:

SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;

Da Sie über Längen-und Breitengrade, die Sie wahrscheinlich verwenden möchten Sphäroid-Abstand-Funktionen.Mit einem räumlichen index, PostGIS skaliert sehr gut für große datasets.

Auch wenn Sie ein voronoi-Diagramm, bedeutet, das noch Sie brauchen, um zu vergleichen, die Ihren x -, y-Koordinaten zu alle 15 tausend erstellte Bereiche.Um das zu erleichtern, ist die erste Sache, tauchte in meinem Geist war zwar zu erstellen, eine Art Gitter über die möglichen Werte, so dass Sie können leicht zu platzieren und x/y-Koordinate in eine der Boxen in einem raster, wenn das gleiche gilt für die Liste der Bereiche, die Sie sollten schnell schrumpfen der möglichen Kandidaten für den Vergleich (weil das raster wäre eher rechteckig ist, ist es möglich, für ein Gebiet zu werden, in mehreren raster-Positionen).

Vorzeitige Optimierung ist die Wurzel allen übels.

15K Koordinaten sind nicht so viel.Warum nicht iterieren über die 15K-Koordinaten und sehen, ob das wirklich ein performance-problem?Sie könnte sparen eine Menge Arbeit und vielleicht ist es nie zu langsam wird gar nicht merken.

Wie groß ein Bereich, sind diese Koordinaten spread out over?Welche Breite Sie an?Wie viel Genauigkeit Sie benötigen?Wenn Sie ziemlich nahe zusammen sind, können Sie wahrscheinlich ignorieren die Tatsache, dass die Erde rund ist-und so behandeln dies als eine kartesische Ebene, anstatt über Unordnung mit sphärischen geometrie und der große Kreis Entfernungen.Natürlich, wie Sie weiter vom äquator entfernt, Grad der longitute kleiner im Vergleich zu Breitengrade, also irgendeine Art von Skalierung angebracht sein.

Starten Sie mit einem ziemlich einfachen Abstand Formel und ein brute-force-Suche und sehen, wie lange das dauert und ob sich die Ergebnisse genau genug, bevor Sie sich der Lust.

Danke an alle für die Antworten.

@Tom, @Chris Upchurch:Die Koordinaten sind ziemlich in der Nähe jedes andere, und Sie sind in einem relativ kleinen Gebiet von etwa 800 qkm.Ich denke, ich kann annehmen, dass die Oberfläche flach sein.Ich brauche, um die Anforderungen immer und immer wieder, und die Antwort sollte schneller sein, genug für mehr web-Erfahrung.

Ein Gitter ist sehr einfach, und sehr schnell.Es ist im Grunde nur ein 2D-array von Listen.Jeder array-Eintrag stellt die Punkte, die fallen innerhalb einer grid-Zelle.Sehr einfach zu set die grid bis:

for each point p
  get cell that contains p
  add point to that cell's list

und es ist sehr leicht, sich die Dinge:

given a query point p
  get cell that contains p
  check points in that cell (and its 8 neighbors), against query point p

Alejo

Nur contrairian, meinen Sie in der Nähe in der Distanz oder (Fahr -) Zeit?In einer Stadt würde ich gerne fahren 5 Meilen (5min) auf der Autobahn als 4 Meilen (20min stop-and-go) in eine andere Richtung.

Also wenn es eine "nächste" Metrik, die Sie benötigen, ich würde schauen in GIS-Datenbanken mit Reise-Zeit-Metrik.

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