Сравнение лат, длинные координаты

Question

У меня есть список из более чем 15 тысяч координат широты и долготы. При любых координатах X, Y какой самый быстрый способ найти ближайшие координаты в списке?

Answer 1

Я сделал это один раз для веб-сайта. То есть найти дилера в пределах 50 миль от вашего почтового индекса. Я использовал расчет большого круга , чтобы найти координаты, которые были в 50 милях к северу, в 50 милях к востоку, в 50 милях к югу и в 50 милях к западу. Это дало мне минимальный и максимальный лат и минимальный и максимальный длинный. Затем я сделал запрос к базе данных:

select *
    from dealers
    where latitude  >= minlat
      and latitude  <= maxlat
      and longitude >= minlong
      and longitude <= maxlong

Поскольку некоторые из этих результатов все еще будут на расстоянии более 50 миль, я использовал формулу большого круга еще раз в этом небольшом списке координат. Затем я распечатал список вместе с расстоянием от цели.

Конечно, если вы хотите искать точки возле международной линии дат или полюсов, это не сработает. Но он отлично работает для поиска в Северной Америке!

Answer 2

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

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

@ Линор: По сути, это то, что вы будете делать после создания диаграммы Вороного. Но вместо создания прямоугольной сетки вы можете выбрать разделительные линии, которые точно соответствуют линиям диаграммы Вороного (таким образом вы получите меньше областей, которые пересекают разделительные линии). Если вы рекурсивно разделите свою диаграмму Вороного пополам вдоль наилучшей разделительной линии для каждой поддиаграммы, вы можете затем выполнить поиск по дереву для каждой точки, которую хотите найти. Это требует немного работы заранее, но экономит время позже. Каждый поиск будет порядка log N, где N - количество точек. 16 сравнений намного лучше, чем 15 000!

Answer 3

Общая концепция, которую вы описываете, это поиск ближайшего соседа , и существует целый ряд методов, которые имеют дело с решением этих типов запросов, точно или приблизительно. Основная идея состоит в том, чтобы использовать метод пространственного разделения, чтобы уменьшить сложность с O (n) на запрос до (приблизительно) O (log n) на запрос.

KD-деревья и варианты KD-деревьев, кажется, работают очень хорошо, но квад-деревья также будут работать. Качество этих поисков зависит от того, статичен ли ваш набор из 15 000 точек данных (вы не добавляете много точек данных в набор ссылок). Работа Маунта и Арьи над библиотекой Approximate Nearest Neighbour проста в использовании и понимании даже без хорошего понимания математики. Это также дает вам некоторую гибкость в типах и допусках ваших запросов.

Answer 4

Это скорее зависит от того, сколько раз вы хотите это сделать и какие ресурсы доступны - если вы делаете тест один раз, то методы O (log N) хороши. Если вы делаете это тысячу раз на сервере, создание таблицы поиска растровых изображений будет быстрее, либо получая результат напрямую, либо в качестве первого этапа. 2 ГБ растрового изображения могут отображать весь мир в 32-битное значение с пикселями 0,011 градуса (1,2 км на экваторе) и должны помещаться в память. Если вы работаете только в одной стране или можете исключить полюса, у вас может быть карта меньшего размера или более высокое разрешение. Для 15 000 точек у вас, вероятно, есть карта намного меньшего размера - я сначала оценил ее в качестве первого шага к поиску по почтовому индексу, который требует более высокого разрешения. В зависимости от требований вы используете сопоставленное значение, чтобы указать непосредственно на результат или на короткий список кандидатов (что позволило бы карту меньшего размера, но потребовала бы большей последующей обработки - вы больше не находитесь на территории поиска O (1) ).

Answer 5

Это можно решить несколькими способами. Сначала я бы подошел к этой проблеме, создав сеть Делоне , соединяющую ближайшие точки друг с другом. Это можно сделать с помощью команды v.delaunay в ГИС-приложении с открытым исходным кодом GRASS . Вы можете решить проблему в GRASS, используя один из множества модулей сетевого анализа в GRASS. В качестве альтернативы вы можете использовать бесплатную пространственную РСУБД PostGIS для выполнения дистанционных запросов. Пространственные запросы PostGIS значительно более мощные, чем в MySQL, поскольку они не ограничены операциями BBOX. Например:

SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;

Поскольку вы используете долготу и широту, вы, вероятно, захотите использовать функции Spheroid-Distance . Благодаря пространственному индексу PostGIS очень хорошо масштабируется для больших наборов данных.

Answer 6

Исходя из ваших разъяснений, я бы использовал геометрическую структуру данных, такую ​​как KD-дерево или R-дерево. MySQL имеет тип данных SPATIAL, который делает это. Другие языки / рамки / базы данных имеют библиотеки для поддержки этого. По сути, такая структура данных встраивает точки в дерево прямоугольников и выполняет поиск в дереве с использованием радиуса. Это должно быть достаточно быстро, и я считаю, что это проще, чем построение диаграммы Вороного. Я предполагаю, что есть некоторый порог, выше которого вы бы предпочли дополнительную производительность диаграммы Вороного, так что вы будете готовы заплатить дополнительную сложность.

Answer 7

Вы не указали, что подразумевали под самым быстрым. Если вы хотите быстро получить ответ без написания какого-либо кода, я бы дал фильтр gpsbabel radius .

Answer 8

Просто чтобы быть противоположным, ты имеешь в виду близкое расстояние или (вождение) время? В городских районах я бы с удовольствием проехал 5 миль (5 минут) по шоссе, а не 4 мили (20 минут остановка и движение) в другом направлении.

Таким образом, если вам нужна «ближайшая» метрика, я бы изучил базы данных ГИС с метриками времени в пути.

Answer 9

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

for each point p
  get cell that contains p
  add point to that cell's list

и поискать вещи очень просто:

given a query point p
  get cell that contains p
  check points in that cell (and its 8 neighbors), against query point p

Алехо

Answer 10

Спасибо всем за ответы.

@ Tom, @Chris Upchurch: координаты довольно близки друг к другу, и они находятся на относительно небольшой площади, около 800 кв. Км. Думаю, я могу предположить, что поверхность плоская. Мне нужно обрабатывать запросы снова и снова, и ответ должен быть достаточно быстрым для большего опыта работы в Интернете.