La plus longue distance entre Lat / Longs dans une liste

Question

J'ai une base de données entrées géocodées. Je dois déterminer les deux entrées sont les plus éloignés d'un sous-ensemble des entrées totales. Par exemple, je sélectionne une liste de 10 entrées puis, à partir de cette liste, déterminer quels deux endroits représentent la plus grande distance dans cette liste.

Je ne peux pas envelopper la tête autour de la façon d'aborder ce sujet. Je l'ai même pensé à utiliser radians, mais rien ne semble répondre à l'exigence.

Pour votre information, pile LAMP va ici ...

Answer 1

La requête suivante calcule la distance entre tous vos points et retourner les deux avec la plus grande distance:

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

Maintenant, je recommande de faire ces calculs avant la main et stocker le résultat dans un tableau distinct.

Answer 2

Par le regard de celui-ci, cela pourrait être résolu en trouvant d'abord la coque convexe de les points (en utilisant scan de Graham, par exemple), et de faire ensuite étriers rotatif pour le diamètre de ce

Answer 3

approche de la force Brute:

1. Trouvez le centre de votre liste de dix en faisant la moyenne des valeurs de latitude et de longitude.

2. Pour chaque (latitude, longitude) paire dans la base de données, en utilisant la formule de grand cercle pour calculer la distance du centre de l'étape (1)

3. Choisissez plus deux distances.

Optimisation Obvious: briser le monde pour N « carrés » (par exemple, 10 degrés de longitude, latitude 10 degrés) et pré-calculer la distance orthodromique entre les centres de chaque paire. Conservez ce dans la base de données. Maintenant, vous pouvez rechercher rapidement pour les paires les plus éloignés « carrés » et seul contrôle (latitude, longitude) à l'intérieur de ces tuiles.

Answer 4

Voici l'algorithme mis en œuvre en PHP pour la distance entre deux points en fonction de la latitude et la longitude.

Notez que si le « sous-ensemble des entrées » est grande, vous avez rapidement un bon nombre de calculs à faire. Si tel est le cas, vous pouvez envisager des distances pré-calcul entre les paires de la ville.

EDIT: Pourquoi l'optimisation de 10 degrés ne fonctionne pas:

Prenez quatre carrés comme indiqué ci-dessous

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

En ne mesurant les centres des carrés et en comparant ces distances, vous obtenez A et D sont plus espacés que A et C. Cependant, les villes 1 et 3 sont clairement plus espacés que 1 et 2.