Самое длинное расстояние между широтой и долготой в списке

Question

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

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

К вашему сведению, сюда идет стек LAMP...

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

Судя по всему, эту проблему можно решить, сначала найдя выпуклая оболочка точек (используя Скан Грэма, например), а затем делая вращающиеся суппорты для диаметра на этом.

Answer 3

Грубый силовой подход:

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

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

3. Выберите два наибольших расстояния.

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

Answer 4

Вот алгоритм реализовано в PHP для определения расстояния между двумя точками на основе широты и долготы.

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

РЕДАКТИРОВАТЬ:Почему оптимизация на 10 градусов не работает:

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

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

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