GIS算法：4_空间检索RTree原理

RTree主要是为了快速进行空间检索。

*关于它的释义如下：

R树是用来做空间数据存储的树状数据结构。例如给地理位置，矩形和多边形这类多维数据创建索引。R树是由Antonin Guttman于1984年提出的。人们随后发现它在理论和应用方面都非常实用。在现实生活中，R树可以用来存储地图上的空间信息，例如餐馆地址，或者地图上用来构造街道、建筑、湖泊边缘和海岸线的多边形。然后可以用它来回答“查找距离我2千米以内的博物馆”，“检索距离我2千米以内的所有路段”（然后显示在导航系统中）或者“查找（直线距离）最近的加油站”这类问题。R树还可以用来加速使用包括大圆距离在内的各种距离度量方式的最邻近搜索。

RTree适用于二维平面，也可应用于三维空间，它的原理类似于BTree，使用层次结构将空间分成几大块最小外接矩形（MBR），这些MBR加起来，包括了空间中的所有对象。在检索的时候，先检索这些MBR，再检索命中的MBR中的节点。

一则可以避免全部遍历，以提升性能；二则可以多线程并行处理检索，以节约时间。

RTree查询很快，但生成比较慢，因为内部需要根据算法建立一棵最适于空间检索的RTree。

常用的软件，如ArcGIS或QGIS的空间检索工具都内嵌了RTree，常用的库包jts和shapely也都带有RTree方法。使用的时候，直接引用就可以。