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

https://stackoverflow.com/questions/35870

09-06-2019
|

Вопрос

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

Решение

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

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

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

Другие советы

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

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

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

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

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

KD-деревья и варианты KD-деревьев, кажется, работают очень хорошо, но квад-деревья также будут работать. Качество этих поисков зависит от того, статичен ли ваш набор из 15 000 точек данных (вы не добавляете много точек данных в набор ссылок). Работа Mount и Arya над библиотекой «Приблизительный ближайший сосед» проста в использовании и понять, даже без хорошего заземления в математике. Это также дает вам некоторую гибкость в типах и допусках ваших запросов.

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

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

Основываясь на ваших разъяснениях, я бы использовал геометрическую структуру данных, такую как KD-дерево или R-дерево.У MySQL есть ПРОСТРАНСТВЕННЫЙ тип данных, который делает это.На других языках / фреймворках / базах данных есть библиотеки для поддержки этого.По сути, такая структура данных встраивает точки в дерево прямоугольников и выполняет поиск по дереву, используя радиус.Это должно быть достаточно быстро, и я считаю, что это проще, чем построение диаграммы Вороного.Я предполагаю, что есть какой-то порог, выше которого вы предпочли бы дополнительную производительность диаграммы Вороного, так что вы будете готовы заплатить за дополнительную сложность.

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

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

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

Даже если вы создадите диаграмму Вороного, это все равно означает, что вам нужно сравнить свои координаты x, y со всеми 15 тысячами созданных областей. Чтобы сделать это проще, первое, что пришло мне в голову, это создать некую сетку по возможным значениям, чтобы вы могли легко разместить координаты х / у в одном из полей сетки, если это Для списка областей вы должны быстро уменьшить возможные кандидаты для сравнения (поскольку сетка будет более прямоугольной, область может находиться в нескольких позициях сетки).

Преждевременная оптимизация - корень всех зол.

15K координат не так уж много. Почему бы не перебрать координаты 15K и посмотреть, действительно ли это проблема с производительностью? Вы можете сэкономить много работы, и, возможно, она никогда не станет слишком медленной, чтобы даже не заметить.

На какой площади расположены эти координаты? На какой широте они? Какую точность вы требуете? Если они довольно близко друг к другу, вы, вероятно, можете игнорировать тот факт, что Земля круглая, и просто рассматривать это как декартову плоскость, а не возиться со сферической геометрией и большим круговым расстоянием. Конечно, когда вы удаляетесь от экватора, градусы долготы становятся меньше по сравнению с градусами широты, поэтому может быть уместен некоторый коэффициент масштабирования.

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

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

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

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

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

Alejo

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow