空间索引/查询(找到k个最近点)

Question

我有+ 10k点(纬度,经度),我正在构建一个应用程序,向您显示距离用户位置最近的k点.

我认为这是一个非常普遍的问题,我不想重新发明轮子.我正在学习四叉树.这似乎是解决这个空间问题的好方法.

我正在使用这些工具:

• Python 2.5
• MySQL的
• MongoDB的

构建Quadtree并不难:http://donar.umiacs.umd.edu/quadtree/points/pointquad.html但是一旦我创建了树并将其保存到db(MySQL或MongoDb),我如何运行查询？

我需要运行这样的查询:

1. 查找距离用户所在位置10公里范围内的所有点.
2. 找到用户所在位置的6个(或至少6个)最近点.

这样做的标准和常用方法是什么？

编辑1:

我已经将+ 10k点加载到MongoDB(地理空间索引)中,乍一看它运行正常.无论如何我发现PostGis:

PostGIS是PostgreSQL对象 - 关系数据库系统的扩展,它允许GIS(地理信息系统)对象存储在数据库中.

所以我想我会试试PostGis.

我也找到了SimpleGeo.您可以在云中存储点/位置,然后通过API查询它们:https://simplegeo.com/docs/tutorials/python#how-do-radial-nearby-query

Answer 1

MongoDB 支持内置的空间索引,因此您需要做的就是使用正确的格式加载点,创建空间索引,然后运行查询.

举一个简单的例子,我在mongo shell中加载了所有50个状态的中心点:

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

接下来,查询给定位置10km范围内的所有点.由于我正在计算最近的状态,我将使用888km(大约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.12km,因此您可以使用a $maxDistance: 0.08999代表10km的应用程序.

更新默认情况下,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..