查找交叉點

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