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

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

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

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

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

Благодарность!


c++ qt approximation hash data-structures
person maxpayne    schedule 24.03.2011    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

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

person Björn Pollex    schedule 24.03.2011

arrow_upward
1
arrow_downward

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

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

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

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

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

Тип данных leafnode

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

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

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

Это популярная задача — http://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor

person siddardha    schedule 25.03.2011