Самая длинная дистанция между лат/длинными в списке

Question

У меня есть база данных геокодированных записей. Мне нужно определить, какие две записи наиболее удалены от подмножества всех записей. Например, я выбираю список из 10 записей, затем из этого списка определяет, какие два места представляют наибольшее расстояние внутри этого списка.

Я не могу окутать голову, как подойти к этому. Я уже рассматривал использование радианов, но, похоже, ничто не соответствует этому требованию.

FYI, стек ЛАМПЫ собирается здесь ...

Answer 1

Следующий запрос рассчитает расстояние между всеми вашими точками и вернет два с наибольшим расстоянием:

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 

Теперь я рекомендую выполнить эти расчеты перед началом работы и сохранить результат в отдельной таблице.

Answer 2

перебора подхода:

1. Найти центр списка десять усреднения значений широты и долготы.

2. Для каждого (широта, долгота) пары в вашей базе данных, используйте большую формулу круга, чтобы вычислить расстояние от центра со стадии (1)

3. Pick величайшие два расстояния.

Очевидная оптимизация: сломать мир, чтобы N «квадраты» (например, 10 градусов долготы, 10 градусов северной широты) и предварительно вычислить расстояние по дуге большого круга между центрами каждого спаривания. Сохраните это в базе данных. Теперь вы можете быстро найти самые дальние «квадраты» и только проверить пары (широта, долгота) внутри этих фрагментов.

Answer 3

Здесь the algorithm реализован в PHP для расстояния между двумя точками на основе широты и долготы.

Обратите внимание, что если «подмножество итоговых записей» велико, вы можете быстро провести немало вычислений. Если это так, вы можете подумать о предварительном расчете расстояний между парами городов.

EDIT: Почему оптимизация 10 градусов не работает:

Возьмите четыре квадрата, как показано ниже

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

только измерения центров квадратов и сравнивая эти расстояния, вы получаете А и D является кроме А и С. Однако города 1 и 3, очевидно, дополнительно отделены от 1 и 2.

Answer 4

По внешнему виду это можно решить, сначала найдя convex hull точек (например, используя Graham's scan), а затем сделав rotating calipers для диаметра на этом.