Longest Distance Between Lat / Longs em uma lista

Question

Eu tenho um banco de dados de entradas georreferenciados. Preciso para determinar quais duas entradas são o mais afastadas a partir de um subconjunto das entradas totais. Por exemplo, eu selecionar uma lista de 10 entradas, em seguida, a partir dessa lista, determinar quais dois lugares representam a maior distância dentro dessa lista.

Eu não posso envolver minha cabeça em torno de como abordar isso. Eu considerei usando radianos mesmo, mas nada parece atender ao requisito.

FYI, LAMP pilha vai aqui ...

Answer 1

A consulta a seguir irá calcular a distância entre todos os seus pontos e retornar os dois com a maior distância:

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

Agora eu recomendando fazendo esses cálculos antes da mão e armazenar o resultado em uma tabela separada.

Answer 2

Ao que parece, isso poderia ser resolvido pela primeira constatação a convexo casco de os pontos (usando varredura de Graham, por exemplo), e em seguida, fazendo pinças rotativas para o diâmetro em que

.

Answer 3

abordagem de força bruta:

1. Encontre o centro da sua lista de dez pela média dos valores de latitude e longitude.

2. Para cada (latitude, longitude) par no seu banco de dados, usar o grande círculo fórmula para calcular a distância a partir do centro a partir do passo (1)

3. Escolha dois maiores distâncias.

optimização Óbvio: quebrar o mundo em que N "quadrados" (por exemplo, 10 graus de longitude e latitude 10 graus) e pré-calcular a distância de círculo entre os centros de cada um de emparelhamento. Armazenar esta no banco de dados. Agora você pode rapidamente olhar para os "quadrados" mais afastadas e só verificar (latitude, longitude) pares dentro dessas telhas.

Answer 4

Aqui está algoritmo implementado no PHP para a distância entre dois pontos baseado em latitude e longitude.

Note que, se o "subconjunto de entradas totais" é grande, você tem rapidamente algumas computações para fazer. Se for esse o caso, você pode querer considerar distâncias pré-cálculo entre pares de cidades.

EDIT: Por 10 otimização grau não funciona:

Tome quatro praças como mostrado abaixo

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

Por apenas medindo os centros dos quadrados e comparando essas distâncias, você recebe um e D estão mais afastados do que A e C. No entanto, cidades 1 e 3 são claramente mais distante do que 1 e 2.