Längster Abstand zwischen Längen/Breiten in einer Liste

Question

Ich habe eine Datenbank mit geokodierten Einträgen. Ich muss feststellen, welche zwei Einträge von einer Teilmenge der gesamten Einträge am weitesten entfernt sind. Zum Beispiel wähle ich eine Liste von 10 Einträgen, dann aus dieser Liste, welche zwei Orte die größte Entfernung innerhalb dieser Liste darstellen.

Ich kann nicht meinen Kopf um, wie man sich nähert. Ich habe sogar überlegt, Radianten zu verwenden, aber nichts scheint die Anforderung zu erfüllen.

FYI, gehen LAMP-Stack hier ...

Answer 1

Die folgende Abfrage berechnet den Abstand zwischen all Ihren Punkten und gibt die beiden 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 Hand durchzuführen und das Ergebnis in einer separaten Tabelle zu speichern.

Answer 2

Brute-Force-Ansatz:

1. Finden Sie die Mitte der Liste der zehn durch 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 Abstand von der Mitte aus Schritt (1)

3. Wählen größten zwei Entfernungen zu berechnen.

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. Speichern Sie dies in der Datenbank. Jetzt können Sie schnell nach den am weitesten entfernten "Quadraten" suchen und nur die (Breiten-, Längen-) Paare innerhalb dieser Kacheln überprüfen.

Answer 3

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

Beachten Sie, dass, wenn die "Teilmenge der Gesamteinträge" groß ist, Sie schnell einige Berechnungen durchführen müssen. Wenn dies der Fall ist, sollten Sie die Entfernungen zwischen Stadtpaaren vorab berechnen.

EDIT: Warum 10-Grad-Optimierung funktioniert nicht:

vier Quadrate nehmen, wie unten

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

von nur Messung der Zentren der Quadrate und Vergleichen dieser Abstände gezeigt, erhalten Sie A und D weiter entfernt als A und C. Städte 1 und 3 liegen jedoch deutlich weiter auseinander als 1 und 2.

Answer 4

Durch die Optik könnte dies gelöst werden, indem zuerst die convex hull der Punkte (unter Verwendung Graham's scan, zum Beispiel), und dann tun rotating calipers für den Durchmesser auf diese.