Алгоритм поиска ближайшей точки

18

У меня есть список нескольких сотен городов с их широтой / долготой. Учитывая другое местоположение (также в лат / лонг) мне нужно найти ближайший город.

Поскольку я не использую ГИС, к настоящему времени очевидным алгоритмом является создание цикла для всех городов, вычисляющего расстояние между точками.

Создание цикла практически выполнимо для меня, но есть какой-то простой в реализации алгоритм, позволяющий сделать это более эффективно? Или какая-нибудь легкая библиотека Java, которая может помочь решить это?

Примечания : Мне не нужно / не нужно полное ГИС-решение или тяжелая / сложная библиотека. Я предпочитаю менее хорошее, но простое и легкое решение, потому что это единственное, что мне нужно решить.

lujop
источник
Значит, не важно, что расстояние не будет правильным? И вы не хотите учитывать дороги, которые могут сделать один город дальше другого (диагональ против квадрата)?
Брэд Несом
Да дороги для меня не важны. Мне нужен ближайший город на линейном расстоянии, потому что это для прогнозов погоды.
Lujop
1
Прогнозы погоды? Я надеюсь, что у вас есть суперкомпьютер и штат обученных метеорологов.
Майкл Тодд
Прогнозы сделаны Майкл, только я должен взять ближайший :)
Lujop

Ответы:

24

Именно этот вопрос я исследовал 20 лет назад при разработке настольной ГИС. Нам нужно было находить расстояния между точками в интерактивном режиме; наша цель состояла в том, чтобы сделать вычисления менее чем за 1/2 секунды для тысяч точек. Тестирование (на 486 ПК с частотой 25 МГц!) Показало, что мы можем вычислить все расстояния в точности так, как вы описываете (с помощью простого очевидного алгоритма), так быстро, что нет смысла создавать более сложное решение, такое как структура дерева квадрантов. ,

Для вычисления расстояний до одной точки «зондирования» ваши варианты включают (а) проекцию всех точек с использованием эквидистантной проекции с центром в точке зонда или (b) принятие модели сферической земли и использование формулы Хаверсайна . Первое уместно, если вам нужна точность эллипсоидальной модели. В любом случае вычисления выполняются достаточно быстро и, вероятно, занимают менее 1000 тиков: вы можете запросить около миллиона точек в секунду с помощью одного процессора.

Достаточно быстро для вас? Если нет, то метод грубой силы легко распараллеливается и масштабируется напрямую с количеством процессоров: просто разделите точки между процессорами, а затем сделайте окончательное сравнение ближайшего, найденного каждым процессором.

Если вам нужно идти быстрее, вы можете использовать различные приближения для отображения точек. Например, если вы находитесь между -88 и +88 градусами широты, а ближайшая найденная точка находится на расстоянии 200 км, то любая точка, широта которой отличается от широты зонда более чем на 2 градуса, не может быть ближе (потому что где-нибудь на земля, один градус широты превышает около 110 км). Во многих случаях этот вид предварительной проверки может позволить вам обрабатывать сотни миллионов точек в секунду.

Whuber
источник
1
Для обсуждения формулы haversine см. Gis.stackexchange.com/q/4906/664
whuber
4

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

Учитывая вашу заявку, работа с эллипсоидальными расстояниями, вероятно, является чрезмерным излишним - вы, вероятно, имеете дело с прогнозами погоды, местонахождение которых едва достигает нескольких метров. Сферическая геометрия достаточно проста, чтобы вы могли легко сделать это в своем цикле.

Это может быть еще проще (например, используйте delta lat в качестве y и delta lon * cos (lat) в качестве x и найдите минимум x ^ 2 + y ^ 2). Вы используете косинус целевой широты, который вы рассчитываете только один раз. Это будет все более и более неточным для отдаленных городов, но они все равно будут отклонены, так что не имеет значения. Предполагая, что ваш ближайший город, как правило, находится в пределах пары сотен километров, шансы на другой результат (ближайший город) с использованием этого и более точной формулы весьма малы и будут происходить только в том случае, если различия достаточно малы, чтобы «какой прогноз был Точность "вероятно будет зависеть от других факторов в любом случае (то есть: потеря в шуме).

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


источник
1

Это в дополнение к тому, что уже было сказано, но я подумал, что хотел бы отметить важность выбора соответствующей структуры данных. Я написал свой собственный код для K-функции в .NET и обнаружил, что использование эффективных коллекций значительно ускорило процесс. Извините, я не знаю обозначения O для точных скоростей. Я использовал два словаря для координат x и y с идентификатором точки в качестве ключа. Я не знаю Java, поэтому ничего не могу предложить.

Ура, Дэвид

dslamb
источник