Алгоритмическое решение для поиска ближайшего города по широте / долготе - PullRequest
Новая
       0

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

5 голосов
/ 25 января 2011

Обратите внимание, что есть и другие подобные вопросы, но 1) я не хочу полагаться на онлайн-сервис, 2) я ищу чистое алгоритмическое решение.

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

Решения, которые я могу придумать:

  1. Очевидный грубыйРешение проблемы силы, конечно, состоит в том, чтобы вычислить все возможные расстояния, используя формулу расстояние большого круга .Это также занимает много времени и составляет O (n).

  2. Модификация алгоритма KD-Tree может работать, но я в растерянности, так каккак изменить этот алгоритм для работы в не декартовых координатах, как в случае с широтой / долготой.Мы можем принять проекцию Меркатора , если это поможет.

  3. Использовать гео-базу данных, такую ​​как PostgreSQL.Это не работает для меня, точка.

Есть идеи?

Ответы [ 6 ]

4 голосов
/ 25 января 2011

Вы можете думать об этом как о проблеме 3D. Преобразуйте (широта, долгота) координаты в (x, y, z) координаты. Это нужно сделать только один раз для вашей базы данных.

Для каждой контрольной точки преобразуйте в (x, y, z) и вычислите квадраты расстояний chord (для скорости и простоты) до каждого города. Выберите ближайший. Я считаю, что ближайший город в 3-пространстве также будет самым близким городом с точки зрения расстояния большого круга.

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

С (x, y, z) -space, возможно, существует структура пространственного разделения, которую вы можете использовать, чтобы ограничить, какие города вам действительно нужно проверить. Я не думаю, что есть тот, который поможет непосредственно в (lat, lon) -пространстве. Но O (N) действительно не так уж и плохо. Кроме того, проблема векторизуется довольно хорошо.

2 голосов
/ 25 января 2011

Я думаю, что вы не можете сэкономить на вычислении матрицы расстояний между городами, просто используйте для нее формулу Формула Хаверсайна .Вычисление матрицы должно быть выполнено только один раз, и вы можете использовать ее позже каждый раз, когда вам это нужно, без какого-либо сложного преобразования.

Вы можете вычислить расстояние с MySQL также, если у вас нет доступа к PostgreSQL, например, смотрите1005 * эта статья о Google Code для деталей.Часть, касающаяся вашей проблемы, может быть обобщена в следующем SQL-запросе: 

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM cities ORDER BY distance LIMIT 1;
0 голосов
/ 29 июля 2012

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

Допустим, корень / голова начинается в Лондоне (выбран в качестве центра на обычной горизонтальной карте мира по Гринвичу): справа: центр города на правой половине карты мира. слева: центр города на левой половине карты мира.

Теперь распространяйте таким же образом, чтобы включить все города для включения. х, у будет частью данных. Выполняя итерацию по каждому узлу, мы можем сравнивать координаты ourCityX и ourCityY.

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

                  London

                /      \

            New York     Singapore
          /        \      /      \
      Florida     Cuba  Mumbai   Melborne

и так далее ...

Он основан на расстоянии, а НЕ на разнице широты ИЛИ долготы. Посмотрим, работает ли.

0 голосов
/ 25 января 2011

Вместо использования элементов широты и долготы, как насчет использования широты, долготы и расстояния от 0,0? Не могли бы вы использовать KD-дерево?

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

0 голосов
/ 25 января 2011

У меня была эта точная проблема, и я решил ее напрямую, используя R-Tree, то есть рассматривая широту / долготу, как если бы они были декартовыми координатами.

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

Тем не менее мне не понравилась эта неточность, и спросили на SO.Кто-то предложил решение, которое, я думаю, могло бы сработать, хотя я не нашел времени для его реализации:

  • Должен быть способ преобразовать координаты таким образом, чтобы компенсировать различные расстояния между меридианами- это оставляет разрывы на меридиане 180 ° и на полюсах для работы.
  • Используйте два указателя с различными системами координат: один регулярный и один, который вращается так, что его меридиан 180 ° перпендикулярен и противоположенодного в основной системе координат.Таким образом, разрывы в одной системе координат являются совершенно правильными точками в другой.
0 голосов
/ 25 января 2011

Около 2: просто начните с диапазона [-90..90, -180, 180].

Единственный нюанс: когда вы разбиваете весь диапазон выше на четыре меньших прямоугольника и вычисляете расстояние от текущей точки до каждого из них, вам необходимо учитывать возможность «переполнения».(точки (0, -179) и (0, 179) находятся ближе, чем кажется от их долготы)

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

...