Как реализовать поиск по близости значений широты и долготы?

Question

мое приложение (мобильное приложение на основе Qt) получает данные с сервера в следующем формате: широта, долгота, описание.

Мне нужно сохранить эти данные в структуре данных для быстрого поиска позже. Теперь у меня есть карта, и когда пользователь нажимает на точку на карте, я получаю широту, долготу этой точки. Используя эти 2 значения, мне нужно быстро просканировать мою структуру данных и получить соответствующее описание. Моя проблема в том, что широта и долгота, которые я получаю при нажатии на карте, является приблизительной (это сенсорное устройство, поэтому я никогда не получаю точный широта и долготу), поэтому, если я выполняю линейный поиск по структуре данных, я никогда не найду эти значения. Кроме того, если данных слишком много, линейный поиск будет очень медленным.

1. Какую структуру данных я должен использовать для хранения lat + long + description (мне приходит в голову хэш ... но я понятия не имею, как объединить long + lat в ключ)

2. Как выполнить приблизительный поиск в структуре данных?

спасибо!

Answer 1

Поскольку ваша задача состоит только из двух измерений, мы можем использовать двоичное дерево. Где каждый лист может иметь максимум «N» точек (широта, долгота - это точка). Только узлы листа будут иметь точки.

Тип данных точки

class Point
{
  float Latitude;
  float Longitude;
  string Description;
}

Тип данных внутреннего узла (NonLeaf Node)

class Node
{
   Float MaxLatitude;
   Float MinLatitude;
   Float MaxLongitude;
   Float MinLongitude;
}

Тип данных листового узла

class LeafNode
{
   Point points[K]; // Array of points
}

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

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

Это популярная проблема - http://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor

Answer 2

Структура данных, которую вы ищете, это kd-tree .Если вы действительно хотите хеширование, и допускается небольшая ошибка, вы можете изучить этот документ (pdf) , в котором описан подход к хешированию на основе расстояния.один работает лучше для вас.Я реализовал алгоритм в этой статье, и он не сработал для моей проблемы (возможно, потому что мои точки данных были распределены не очень равномерно).В вашем случае это может отличаться, поэтому вам придется попробовать.