R-Tree

一、R-Tree树介绍

R树是一种空间索引结构，由对象的边界框与 id 来进行索引和查找，对空间中的物体进行查找时可以加快查找速度。R树对几何物体与信息进行查找时有特别明显的优势，边界框的形势如（llx,lly,rux,ruy）或者（llx,rux,lly,ruy）的一个最小边界矩形（MBR）。

R树是一种平衡树，树中的每个非叶子节点保存的是对象的边界框，而叶子节点保存的是我们插入的对象。对于R树的各种实现来说，每个节点的默认容量（也就是每个节点中保存的最大节点数量）影响着查找与搜索的效率。

二、python中Rtree的使用

python中有rtree的库，名字就叫做rtree，在使用时先构造rtree的索引，然后向索引中插入我们的对象和边界框，需要注意的是，往rtree中插入的对象必须是可以pickled的对象。

在python中rtree的默认值为100，当插入的数量大于100时，rtree就会分裂出一个新的节点来进行存储，并且会增加一层。

注：边界框的插入有特定的规则，当rtree的 interleaved 值为True时（默认值为True），最小边界框的形式如：

[xmin, ymin, ..., kmin, xmax, ymax, ..., kmax]

当interleaved的值为False时，最小边界框的形式如：

[xmin, xmax, ymin, ymax, ..., ..., kmin, kmax]

rtree的查询结果返回的是一个迭代器，我们可以拿到插入时的id、边界框，对象。

import rtree

tree = rtree.Rtree()
print(tree)
index = 0
for i in range(100):
    coord = (i-1, i-1, i, i)
    obj = i    # 我们插入的对象
    tree.insert(index, coord, obj)
    index += 1
print(tree)

# rtree的查找，边界框，是否查找对象：默认为False不查找
result = tree.intersection((0,0,1,1),objects=True)
# 结果是一个迭代器
result = list(result)
print(result)