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

我有+ 10k点（纬度，经度），我正在构建一个应用程序，向您显示与用户位置相关的k个最近点。空间索引/查询（查找k个最近点）

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

我使用这些工具：

Python 2.5的
MySQL的
MongoDB的

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

，我需要这样的运行查询：

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

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

编辑1：

我已经加载了+ 10K点到MongoDB的（地理空间索引）和它的第一眼工作正常。反正我发现PostGis：

PostGIS的是扩展到PostgreSQL对象关系型数据库系统，使GIS（地理信息系统）对象存储在数据库中。

所以我想我会给PostGis一个尝试。

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

来源

2011-05-17 ccarpenterg

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

对于一个简单的例子，我加载的中心点为所有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..

来源

2011-05-17 05:34:28 samplebias

+1。使用具有空间扩展名的数据库要容易得多。有[MySQL中的空间扩展]（http://dev.mysql.com/doc/refman/5.6/en/spatial-extensions.html），另请参见[here]（http://stackoverflow.com/questions/1006654 /最快的距离查对给定纬度 - 经度）。 – MarkJ 2011-05-17 11:46:59

'$ maxDistance'的单位是什么？关于这个答案有一个很大的几何球形几何气味......它似乎没有考虑到这样一个事实：**经度**在赤道上约111公里，在**处减少到** ZERO **公里极。 – 2011-05-19 03:13:19

我的例子只是为了证明存在Mongo空间扩展。我提供的链接显示了如何使用平面或球面距离功能（取决于所用软件的版本）。 – samplebias 2011-05-19 03:28:05

您可能想要查看wikipedia中的kdtree条目。当你有两个以上的维度时，这将会很有用（与四叉树不同）。我建议使用kd-tree，因为该条目有创建和查询树的python代码。

来源

2011-05-17 04:18:38

如果你想使用MongoDB的，然后仔细阅读their docs。默认模型是扁平地球。 它假设一定的经度与纬度具有相同的长度。

我引用了：“”“目前的实现假设了一个理想化的平坦地球模型，这意味着纬度（y）和经度（x）的arcdegree在任何地方都代表相同的距离。它们大约相当于69英里或111公里，然而，在{x：-74，y：40.74}的10个办公室，一个经度大约是52英里或83公里（纬度不变），这意味着1英里的距离似乎比东面1英里还要近。“”“”

你需要他们的“新球形模型”。被警告：你需要按顺序使用（经度，纬度） - 再次仔细阅读他们的文档。

来源

2011-05-19 03:32:35

我知道这个：order（lng，lat），spherical（$ nearSphere，$ centerSphere，$ box保持不变），距离使用弧度。 – ccarpenterg 2011-05-19 03:53:58

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

回答

相关问题