2

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

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

我正在使用这些工具：

  • 蟒蛇2.5
  • MySQL
  • 蒙古数据库

构建四叉树并不难：http : //donar.umiacs.umd.edu/quadtree/points/pointquad.html 但是一旦我创建了树并将其保存到数据库（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

4

3 回答 3

6

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 内的所有点。由于我正在计算最近的州，因此我将使用 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.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..
于 2011-05-17T05:34:28.167 回答
2

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

于 2011-05-17T04:18:38.790 回答
1

如果您想使用 MongoDB，请仔细阅读他们的文档。默认模型是flat earth。它假定经度与纬度具有相同的长度。

我引用：“”“当前的实现假设一个平坦地球的理想化模型，这意味着纬度 (y) 和经度 (x) 的弧度在任何地方都表示相同的距离。这仅在它们都在的赤道处是正确的等于 69 英里或 111 公里。但是，在 { x : -74 , y : 40.74 } 处的 10gen 办事处，经度的一个弧度约为 52 英里或 83 公里（纬度不变）。这意味着向北 1 英里的地方似乎比东边 1 英里的地方更近。"""

你需要他们的“新球形模型”。请注意：您需要按顺序使用 (longtitude, latitude) - 再次仔细阅读他们的文档。

于 2011-05-19T03:32:35.247 回答