python - 空间索引/查询(寻找k个最近点)

Question

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

我认为这是一个很常见的问题，我不想重新发明轮子。我正在学习四叉树。这似乎是解决这个空间问题的好方法。

我正在使用这些工具:

• python 2.5
• MySQL
• MongoDB

构建四叉树并不难:http://donar.umiacs.umd.edu/quadtree/points/pointquad.html但是，一旦我创建了树并将其保存到数据库(MySQL 或 MongoDb)中，我该如何运行查询？

我需要运行这样的查询:

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

执行此操作的标准和通用方法是什么？

编辑 1:

我已将 +10k 点加载到 MongoDB(地理空间索引)中，乍一看它运行良好。不管怎样，我找到了PostGis :

PostGIS is an extension to the PostgreSQL object-relational database system which allows GIS (Geographic Information Systems) objects to be stored in the database.

所以我想我会试试 PostGis。

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

Answer 1

MongoDB 有 support for spatial indexes built-in ，所以您需要做的就是使用正确的格式加载您的点，创建空间索引，然后运行您的查询。

举个简单的例子，我在 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 } }

接下来，查询给定位置 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 } }

自 one degree of latitude is approximately 111.12km ，您将使用 $maxDistance: 0.08999 来代表您的应用程序的 10 公里。

已更新 默认情况下，MongoDB 采用“理想化的平坦地球模型”，但这会导致不准确，因为经度线会聚在两极。 MongoDB versions 1.7+ support spherical distance calculations , 这提供了更高的精度。

这是使用球面距离运行上述查询的示例。 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..