Weiteste Distanz zwischen Lat / Longs in einer Liste

Question

Ich habe eine Datenbank von geocodierte. Ich muss, um zu bestimmen, welche zwei Einträge der am weitesten von einer Teilmenge der Gesamt Einträge voneinander entfernt sind. Wählen Sie zum Beispiel ich eine Liste von 10 Einträgen dann aus dieser Liste, festzustellen, welche zwei Stellen den größten Abstand innerhalb dieser Liste vertreten.

Ich kann nicht wickeln meinen Kopf herum, wie dies zu nähern. Ich habe mit Radiant als auch, aber nichts scheint die Anforderung zu erfüllen.

FYI, LAMP-Stack geht hier ...

Answer 1

Die folgende Abfrage wird die Entfernung zwischen allen Punkten berechnen und die beide mit dem größten Abstand zurück:

SELECT coor1.longitude as lon1,
       coor1.latitude as lat1,
       coor2.longitude as lon2,
       coor2.latitude as lat2,
       (ACOS(
         COS(RADIANS(coor1.latitude))  * 
         COS(RADIANS(coor1.longitude)) *
         COS(RADIANS(coor2.latitude))  *
         COS(RADIANS(coor2.longitude)) + 
         COS(RADIANS(coor1.latitude))  *
         SIN(RADIANS(coor1.longitude)) *
         COS(RADIANS(coor2.latitude))  *
         SIN(RADIANS(coor2.longitude)) +
         SIN(RADIANS(coor1.latitude))  * 
         SIN(RADIANS(coor2.latitude))
         ) * 6378                        --- Use 3963.1 for miles
       ) 
AS DistanceKM
FROM coordinates coor1,
     coordinates coor2
WHERE NOT (coor1.longitude = coor2.longitude AND coor1.latitude = coor2.latitude)
ORDER BY DistanceKM DESC
LIMIT 1;                                 --- Only the biggest

Jetzt empfehle ich diese Berechnungen vor der Hand und Speichern des Ergebnisses in einer separaten Tabelle zu tun.

Answer 2

Mit den Blicken von ihm, könnte dies, indem zuerst gelöst werden, finden Sie die konvexe Hülle die Punkte (unter Verwendung von Graham Scan , zum Beispiel), und dann Drehen für den Durchmesser auf, dass Sattel

Answer 3

Brute-Force-Ansatz:

1. in der Mitte der Liste der zehn finden, indem Sie die Breiten- und Längenwerte gemittelt werden.

2. Für jede (Breite, Länge) Paar in Ihrer Datenbank, verwenden Sie die großen Kreis Formel Entfernung vom Zentrum von Schritt zu berechnen (1)

3. Pick größte zwei Distanzen.

Offensichtliche Optimierung: brechen die Welt in N „Quadrate“ (beispielsweise 10 Grad Länge, 10 Grad nördlicher Breite) und vorge berechnen die Großkreisentfernung zwischen den Mittelpunkten jeder Paarung. Bewahren Sie diese in der Datenbank. Jetzt können Sie schnell für die am weitesten wegschauen „Quadrate“ und nur Prüfung (Breite, Länge) Paare innerhalb dieser Fliesen.

Answer 4

Hier ist der Algorithmus zwischen zwei Punkten in PHP für den Abstand implementiert basierend auf Breite und Länge.

Beachten Sie, dass, wenn die „Teilmenge der gesamten Einträge“ groß ist, Sie schnell schon einige Berechnungen zu tun haben. Wenn das der Fall ist, können Sie Vorausberechnen Abstände zwischen Städtepaaren betrachten.

EDIT: Warum 10-Grad-Optimierung funktioniert nicht:

Nehmen Sie vier Quadrate, wie unten

gezeigt

-------------------
|        |        |
|   A    |   B    |
|        |        |
|_______1|________|
|        |2       |
|   C    |   D    |
|        |        |
|_______3|________|

Mit dem nur die Zentren der Quadrate messen und diese Abstände zu vergleichen, erhalten Sie A und D sind weiter voneinander entfernt als A und C jedoch Städte 1 und 3 sind deutlich weiter auseinander als 1 und 2.