Más larga que la distancia entre Lat / Longs en una lista

Question

Tengo una base de datos de entradas geocodificadas. Necesito para determinar que dos entradas son los más alejados de un subconjunto de las entradas totales. Por ejemplo, selecciono una lista de 10 entradas a continuación, de dicha lista, determinan que dos lugares representan la mayor distancia dentro de esa lista.

No puedo hacerme a la forma de abordar esto. He considerado el uso de radianes incluso, pero nada parece cumplir el requisito.

Para su información, LAMP ir aquí ...

Answer 1

La siguiente consulta calculará la distancia entre todos sus puntos y volver a los dos con la mayor distancia:

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

Ahora recomendar hacer esos cálculos antes de la mano y almacenar el resultado en una tabla separada.

Answer 2

Por lo visto, esto podría ser resuelto mediante la búsqueda de la primera convexa casco de los puntos (utilizando exploración de Graham, por ejemplo), y luego hacer giratoria pinzas para el diámetro en esa

Answer 3

método de fuerza bruta:

1. Encuentra el centro de su lista de diez promediando los valores de latitud y longitud.

2. Para cada (latitud, longitud) par en su base de datos, usar la gran fórmula círculo para calcular la distancia desde el centro de la etapa (1)

3. Escoja mayores dos distancias.

optimización evidente: romper el mundo en el que "cuadrados" N (por ejemplo, 10 grados de longitud, 10 grados de latitud) y pre-calculan la distancia ortodrómica entre los centros de cada uno de emparejamiento. Almacenar esto en la base de datos. Ahora se puede buscar rápidamente el más lejos "cuadrados" y único freno (latitud, longitud) pares dentro de los azulejos.

Answer 4

Aquí es el algoritmo implementado en PHP para la distancia entre dos puntos basado en latitud y longitud.

Tenga en cuenta que si el "subconjunto de entradas totales" es grande, tiene rápidamente un buen número de cálculos que hacer. Si ese es el caso, es posible que desee considerar distancias entre pares de ciudades pre-cálculo.

EDIT: ¿Por qué la optimización del grado 10 no funciona:

Tome cuatro cuadrados como se muestra a continuación

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

Por única medición de los centros de los cuadrados y la comparación de esas distancias, se obtiene A y D son más separados que A y C. Sin embargo, ciudades 1 y 3 son claramente más separados que 1 y 2.