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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алехо

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

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

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

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

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