Indice espacial / consulta (encontrando k puntos mas cercanos)

Tengo + 10k puntos (latitud, longitud) y estoy creando una aplicación que muestra los k puntos más cercanos a la ubicación de un usuario.

Creo que este es un problema muy común y no quiero reinventar la rueda. Estoy aprendiendo acerca de Quadtrees. Parece ser un buen enfoque para resolver este problema espacial.

Estoy usando estas herramientas:

Crear el Quadtree no es tan difícil: http://donar.umiacs.umd.edu/quadtree/points/pointquad.html Pero una vez que he creado el árbol y lo he guardado en una base de datos (MySQL o MongoDb), cómo corro ¿la consulta?

Necesito ejecutar consultas como estas:

  1. Encuentra todos los puntos dentro de los 10 km de la ubicación del usuario.
  2. Encuentra los 6 (o al menos 6) puntos más cercanos a la ubicación del usuario.

¿Cuál es el enfoque estándar y común para hacerlo?

EDITAR 1:

He cargado los puntos + 10k en MongoDB (indexación geoespacial) y funciona bien a primera vista. De todos modos he encontrado PostGis :

PostGIS es una extensión del sistema de base de datos relacional de objetos PostgreSQL que permite que los objetos GIS (Sistemas de información geográfica) se almacenen en la base de datos.

Así que creo que voy a darle una oportunidad a PostGis.

También he encontrado SimpleGeo . Puede almacenar puntos / lugares en la nube y luego consultarlos a través de una API: https://simplegeo.com/docs/tutorials/python#how-do-radial-nearby-query

MongoDB tiene soporte para índices espaciales integrados , por lo que todo lo que necesita hacer es cargar sus puntos con el formato correcto, crear el índice espacial y luego ejecutar sus consultas.

Para un ejemplo rápido, cargué los puntos centrales de los 50 estados en la consola de 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}}) > ... 

A continuación, para consultar los 6 puntos más cercanos a una ubicación determinada :

 > 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 } } 

A continuación, para consultar todos los puntos dentro de los 10 km de una ubicación determinada . Como estoy calculando los estados más cercanos, usaré 888 km (que es aproximadamente 8 grados de latitud):

 > 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 } } 

Dado que un grado de latitud es de aproximadamente 111.12 km , usaría una $maxDistance: 0.08999 para representar 10 km para su aplicación.

Actualizado de forma predeterminada, MongoDB asume un “modelo de tierra plana idealizada”, pero esto produce imprecisiones ya que las líneas de longitud convergen en los polos. Las versiones 1.7+ de MongoDB admiten cálculos de distancia esféricos , lo que proporciona una mayor precisión.

Aquí hay un ejemplo de cómo ejecutar la consulta anterior usando una distancia esférica. la maxDistance es en radianes, por lo que necesitamos dividirnos por el radio promedio de la tierra:

 > 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.. 

Es posible que desee ver la entrada de kdtree en wikipedia. Esto sería útil cuando también tiene más de dos dimensiones (a diferencia de los quadtrees). Sugiero el árbol kd porque la entrada tiene un código python para crear y consultar el árbol.

Si quieres usar MongoDB, entonces lee sus documentos cuidadosamente. El modelo por defecto es tierra plana . Se supone que un grado de longitud tiene la misma longitud que un grado de latitud .

Cito: “” “La implementación actual asume un modelo idealizado de una tierra plana, lo que significa que un grado de arco de latitud (y) y longitud (x) representa la misma distancia en todas partes. Esto solo es cierto en el ecuador donde ambos están igual a 69 millas o 111 km. Sin embargo, en las oficinas de 10gen en {x: -74, y: 40.74} un arco de longitud es de aproximadamente 52 millas o 83 km (la latitud no cambia). Esto significa que algo 1 milla al norte Parecería más cerca que algo 1 milla al este. “” ”

Necesitas su “nuevo modelo esférico”. Tenga cuidado: debe usar (longtitude, latitude) en ese orden; una vez más, lea atentamente sus documentos.