空间索引/查询（寻找k个最近点）

3 投票

3 回答

3476 浏览

数据工程师

提问于 2025-04-16 17:47

我有超过一万个点（经度和纬度），正在开发一个应用程序，可以显示离用户位置最近的k个点。

我觉得这是一个很常见的问题，我不想重新发明轮子。我在学习四叉树（Quadtrees），看起来这是解决这个空间问题的一个好方法。

我使用的工具有：

Python 2.5
MySQL
MongoDb

建立四叉树并不难：http://donar.umiacs.umd.edu/quadtree/points/pointquad.html。但是一旦我创建了树并将其保存到数据库（MySQL或MongoDb），我该如何查询呢？

我需要运行这样的查询：

找到用户位置10公里范围内的所有点。
找到离用户位置最近的6个（或者至少6个）点。

有什么标准和常见的方法来做到这一点吗？

编辑 1：

我已经把超过一万个点加载到MongoDB（地理空间索引），看起来一切正常。无论如何，我发现了PostGis：

PostGIS是一个扩展，用于PostgreSQL对象关系数据库系统，允许在数据库中存储地理信息系统（GIS）对象。

所以我想我会试试PostGis。

我还发现了SimpleGeo。你可以在云端存储点/地点，然后通过API查询它们：https://simplegeo.com/docs/tutorials/python#how-do-radial-nearby-query

mongodb 数据库优化地理信息系统四叉树空间索引 postgis 空间查询最近邻查询

3 个回答

如果你想使用MongoDB，建议你仔细阅读他们的文档。默认的模型是平面地球。这意味着经度和纬度的每一度长度是一样的。

我引用一下：“目前的实现假设地球是平的，这意味着纬度（y）和经度（x）的一度在任何地方代表的距离都是一样的。这个说法在赤道上是对的，因为在赤道上它们的长度大约都是69英里或111公里。但是，在10gen办公室的坐标{ x : -74 , y : 40.74 }，一度经度大约是52英里或83公里（纬度不变）。这就意味着，向北走1英里会比向东走1英里看起来更近。”

你需要使用他们的“新球形模型”。要注意：你需要按照（经度，纬度）的顺序来使用——再次提醒，仔细阅读他们的文档。

回答于 2025-04-16 由 Python大师

分享举报

你可以看看维基百科上的kdtree条目。这种数据结构在处理超过两个维度的数据时特别有用（和四叉树不一样）。我推荐kd树，因为里面有用Python写的代码，可以用来创建和查询这个树。

回答于 2025-04-16 由 Python大师

分享举报

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

然后，查询某个地点周围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..

回答于 2025-04-16 由 Python大师

分享举报

空间索引/查询（寻找k个最近点）

3 个回答

撰写回答