查找交叉点

Question

给定一个场景，其中有数百万个可能重叠的边界框，其大小可变，宽度小于5km。

使用参数findIntersections（Longitude，Latitude，Radius）创建一个快速函数，输出是边界框id的列表，其中每个边界框原点位于函数参数维度的外围。

如何优雅地解决这个问题？

Answer 1

这是通过使用一个R-tree数据结构

DBS像MySQL或PostgreSQL正常完成具有使用R树引擎盖下快速检索一个一定距离以内的位置在地图上的一个点GIS模块。

从http://en.wikipedia.org/wiki/R-tree：

R-树树数据结构 类似于B树，而是用于 用于空间的访问方法，即，用于 索引多维 信息;例如，地理数据的坐标（X，Y）为 。 A R-tree 的常见实际用法可能是：“查找我目前 位置的2个 公里（1.2英里）内的所有博物馆”。

的数据结构分割空间 分级嵌套的，并且可能 重叠，最小边界 矩形（MBR，否则称为 边界框，即，“矩形”，在什么 的“R” R-树代表）。

的Priority R-Tree（PR-树）是具有最大运行时间变体：

"O((N/B)^(1-1/d)+T/B) I/Os, where N is the number of d-dimensional (hyper-) 
rectangles stored in the R-tree, B is the disk block size, and T is the output 
size." 

在实践中，大多数现实世界的查询将有一个情况要快得多平均运行时间。

仅供参考，除了张贴的其他伟大的代码，有没有像SpatiaLite和SQLite R-tree module

Answer 2

PostGIS一些很酷的东西是一个开源GIS extention PostgreSQL的。

他们有ST_Intersects和ST_Intersection功能可用。

如果你有兴趣，你可以挖过来，看看它是如何实现的有：

http://svn.osgeo.org/postgis/trunk/postgis/

Answer 3

这似乎是一个更好的更一般的方法GiST的

http://en.wikipedia.org/wiki/GiST