Пространственный индекс / запрос (поиск k ближайших точек) - PullRequest
Новая
       61

Пространственный индекс / запрос (поиск k ближайших точек)

2 голосов
/ 17 мая 2011

У меня + 10k точек (широта, долгота), и я создаю приложение, которое показывает вам k ближайших точек к местоположению пользователя.

Я думаю, что это очень распространенная проблема, и я не хочу изобретать велосипед. Я изучаю Quadtrees. Кажется, это хороший подход для решения этой пространственной проблемы.

Я использую эти инструменты:

  • Python 2.5
  • MySQL
  • MongoDb

Построить Quadtree не так сложно: http://donar.umiacs.umd.edu/quadtree/points/pointquad.html Но как только я создал дерево и сохранил его в БД (MySQL или MongoDb), как мне выполнить запрос?

Мне нужно выполнить такие запросы:

  1. Найти все точки в пределах 10 км от местоположения пользователя.
  2. Найдите 6 (или не менее 6) ближайших точек к местоположение пользователя.

Каков стандартный и общий подход к этому?

РЕДАКТИРОВАТЬ 1:

Я загрузил + 10 тыс. Баллов в MongoDB (Геопространственное индексирование), и на первый взгляд все работает нормально. В любом случае я нашел PostGis :

PostGIS является расширением системы объектно-реляционной базы данных PostgreSQL, которая позволяет хранить объекты ГИС (географические информационные системы) в базе данных.

Думаю, я попробую PostGis.

Я также нашел SimpleGeo . Вы можете хранить точки / места в облаке и затем запрашивать их через API: https://simplegeo.com/docs/tutorials/python#how-do-radial-nearby-query

Ответы [ 3 ]

6 голосов
/ 17 мая 2011

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

Для быстрого примера я загрузил центральные точки для всех 50 состояний в оболочке mongo: 

> db.places.ensureIndex({loc: "2d"})
> db.places.save({name: "AK", loc: {long: -152.2683, lat: 61.3850}})
> db.places.save({name: "AL", loc: {long: -86.8073, lat: 32.7990}})
> db.places.save({name: "AR", loc: {long: -92.3809, lat: 34.9513}})
> db.places.save({name: "AS", loc: {long: -170.7197, lat: 14.2417}})
> ...

Далее, чтобы запросить 6 ближайших точек к указанному местоположению : 

> db.places.find({loc: { $near: {long: -90, lat: 50}}}).limit(6)
{"name" : "WI", "loc" : { "long" : -89.6385, "lat" : 44.2563 } }
{"name" : "MN", "loc" : { "long" : -93.9196, "lat" : 45.7326 } }
{"name" : "MI", "loc" : { "long" : -84.5603, "lat" : 43.3504 } }
{"name" : "IA", "loc" : { "long" : -93.214, "lat" : 42.0046 } }
{"name" : "IL", "loc" : { "long" : -89.0022, "lat" : 40.3363 } }
{"name" : "ND", "loc" : { "long" : -99.793, "lat" : 47.5362 } }

Далее, чтобы запросить все точки в пределах 10 км от заданного местоположения .Поскольку я вычисляю ближайшие состояния, я буду использовать 888 км (что примерно равно 8 градусам широты): 

> db.places.find({loc: { $near: {long: -90, lat: 50}, $maxDistance: 8}})
{"name" : "WI", "loc" : { "long" : -89.6385, "lat" : 44.2563 } }
{"name" : "MN", "loc" : { "long" : -93.9196, "lat" : 45.7326 } }

Поскольку один градус широты равен приблизительно 111.12км , вы бы использовали $maxDistance: 0.08999 для представления 10 км для вашего приложения.

Обновлено По умолчанию MongoDB предполагает "идеализированную модель плоской земли", но это приводит к неточностям, посколькулинии долготы сходятся на полюсах. MongoDB версии 1.7+ поддерживает вычисления сферического расстояния , что обеспечивает повышенную точность.

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

> db.runCommand({geoNear: "places", near: [-90, 50], spherical: true, 
                 maxDistance: 800/6378});
(summarizing results as they're too verbose to include)
"MN"  dis: 0.087..
"WI"  dis: 0.100..
"ND"  dis: 0.120..
2 голосов
/ 17 мая 2011

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

1 голос
/ 19 мая 2011

Если вы хотите использовать MongoDB, внимательно прочитайте их документы . Модель по умолчанию - плоская земля . Предполагается, что градус долготы имеет ту же длину, что и градус широты .

Я цитирую: "" "Текущая реализация предполагает идеализированную модель плоской земли, означающую, что арочные градусы широты (y) и долготы (x) представляют одинаковое расстояние везде. Это верно только для экватора, где оба равны примерно 69 милям или 111 км. Однако в офисах 10gen в {x: -74, y: 40.74} одна степень долготы составляет около 52 миль или 83 км (широта не меняется). к северу казалось бы ближе, чем 1 миля к востоку. "" "

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

...