空间索引/查询(查找k个最近的点) [英] Spatial index/query (finding k nearest points)

问题描述

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

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

我正在使用以下工具:

• Python 2.5
• MySQL
• MongoDb

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

我需要运行以下查询:

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

执行此操作的标准方法和常用方法是什么?

我已经将+ 10k点加载到MongoDB(地理空间索引)中，乍一看效果很好.无论如何，我已经找到了 PostGis :

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

所以我想尝试一下PostGis.

我还找到了 SimpleGeo .您可以将点/地点存储在云中，然后通过API查询它们:解决方案

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

I have +10k points (latitude, longitude) and I'm building an app that shows you the k nearest points to a user's location.

I think this is a very common problem and I don't want to reinvent the wheel. I'm learning about Quadtrees. It seems to be a good approach to solve this spatial problem.

I'm using these tools:

• Python 2.5
• MySQL
• MongoDb

Building the Quadtree is not that hard: http://donar.umiacs.umd.edu/quadtree/points/pointquad.html But once I've created the tree and saved it to a db (MySQL or MongoDb), how I run the query?

I need to run queries like these:

1. Find all points within 10 km of the user's location.
2. Find the 6 (or at least 6) nearest points to the user's location.

What's the standard and common approach to do it?

EDIT 1:

I've loaded the +10k points into MongoDB (Geospatial indexing) and it works fine at first glance. Anyway I've found 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.

So I think I'll give PostGis a try.

I've also found SimpleGeo. You can store points/places in the cloud and then query them via an API: https://simplegeo.com/docs/tutorials/python#how-do-radial-nearby-query

解决方案

MongoDB has support for spatial indexes built-in, so all you'd need to do is load your points using the correct format, create the spatial index, and then run your queries.

For a quick example, I loaded the center points for all 50 states in the mongo shell:

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

Next, to query for the 6 nearest points to a given location:

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

Next, to query for all points within 10km of a given location. Since I'm calculating the nearest states, I'll use 888km (which is approximately 8 degrees of latitude):

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

Since one degree of latitude is approximately 111.12km, you'd use a $maxDistance: 0.08999 to represent 10km for your application.

Updated By default MongoDB assumes an "idealized flat earth model" but this results in inaccuracies since longitude lines converge at the poles. MongoDB versions 1.7+ support spherical distance calculations, which provides the increased precision.

Here is an example of running the above query using spherical distance. the maxDistance is in radians, so we need to divide by the earth's average radius:

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

这篇关于空间索引/查询(查找k个最近的点)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！