Longest Distanza tra Lat / Longs in un elenco

Question

Ho un database di voci geocodificate. Ho bisogno di determinare quale due voci sono le più lontane a parte un sottoinsieme delle voci totali. Ad esempio, seleziono una lista di 10 voci, allora, da quella lista, determinare quali due luoghi rappresentano la distanza più grande all'interno di tale lista.

Non posso avvolgere la mia testa intorno a come affrontare questo. Ho considerato usando radianti anche, ma nulla sembra soddisfare il requisito.

Cordiali saluti, stack LAMP andando qui ...

Answer 1

La query seguente calcola la distanza tra tutti i punti e tornare i due con il più grande distanza:

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

Ora mi raccomandare a fare quei calcoli prima mano e memorizzare il risultato in una tabella separata.

Answer 2

Con gli sguardi di esso, questo potrebbe essere risolto trovando prima il convesso di i punti (utilizzando scansione di Graham, per esempio), e poi facendo rotazione pinze per il diametro su quel

Answer 3

approccio forza bruta:

1. Trova il centro della vostra lista di dieci dalla media dei valori di latitudine e longitudine.

2. Per ogni (latitudine, longitudine) coppia nel database, utilizzare il grande cerchio formula per calcolare la distanza dal centro dal punto (1)

3. Pick più grandi due distanze.

ottimizzazione Ovvio: rompere il mondo per N "piazze" (ad esempio, 10 gradi di longitudine, 10 gradi di latitudine) e pre-calcolare la distanza ortodromica tra i centri di di ogni accoppiamento. Conservare questo nel database. Ora si può guardare rapidamente per la più lontana "piazze" e unico controllo (latitudine, longitudine) le coppie all'interno di quelle mattonelle.

Answer 4

Ecco l'algoritmo implementato in PHP per la distanza tra due punti in base a latitudine e longitudine.

Si noti che se il "sottoinsieme di voci in totale" è grande, si dispone subito un bel paio di calcoli da fare. Se questo è il caso, si può prendere in considerazione le distanze tra coppie di città pre-calcolo.

EDIT: Perché ottimizzazione 10 gradi non funziona:

Prendere quattro quadrati come illustrato di seguito

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

Misurando solo i centri dei quadrati e confrontando quelle distanze, si ottiene A e D sono più distanti di A e C. Tuttavia, le città 1 e 3 sono chiaramente più distanti di 1 e 2.