安装
rtree可以看做是二维或者多维空间中的b树
如果不知道b树的建议先去看看b树
rtree的原理
两篇文章相同的
Python rtree官方文档
rtree中的基本单位是一个个小的矩形
在这个库中是一个类: rtree.index.Item
我这里主要写一下Pythonrtree的使用
初始化对象
from rtree import indexidx = index.Index()
插入数据: insert(self, id, coordinates, obj=None), 没有返回值
其中id是一个长整数,coordinates 是形如(xmin, ymin, xmax. ymax)的元组或者列表也可以,都是double类型的浮点数,和python的float相对应(python只有float,相当于c++中的double)
obj是可选的选项,可以是任意的一个Python对象,实际原理就是先将Python对象序列化以后再存储起来
idx.insert(0,(0,0,1,1), obj={1:4}) add方法和insert方法完全一样
In [226]: ctypes.c_double(10.0/3)Out[226]: c_double(3.3333333333333335)In [227]: 10.0/3Out[227]: 3.3333333333333335
大家看,c_double和python的float是相一致的,尽管放心
删除数据: delete(self, id, coordinates); 没有返回值
idx.delete(0,(0,0,1,1))
这个函数既需要id,又需要坐标值
如果没有目标点满足,不会报错,,也不会删除
如果有多个目标点满足的话,仅会删除一个(目测和插入顺序相关,但是请避免这种事情的发生)
查找区域内的元素intersection(self, coordinates, objects=False): 返回是一个生成器
In [243]: list(c.intersection((0,0,2,2), objects=False))Out[243]: [0, 0, 1]In [244]: list(c.intersection((0,0,2,2), objects=True))Out[244]: [, , ]In [245]: list(c.intersection((0,0,2,2), objects=False))Out[245]: [0, 0, 1]
仅仅是边界甚至是一个顶点有重叠也算是重叠,比如(0,0,1,1)和(1,1,2,2)算重叠
objects=False返回的是id, "raw"返回的是object,附带的python对象
True返回的是item对象,有['handle', 'owned', 'id', 'object', 'bounds']五个元素,后三种分别是id,object,范围, 前面的不太清楚,owned是一个布尔类型,handle是一个对象
In [249]: a = list(c.intersection((0,0,2,2), objects=True))[0]In [250]: a.boundsOut[250]: [0.0, 1.0, 0.0, 1.0]In [251]: a.idOut[251]: 0In [252]: a.objectOut[252]: 'b'In [253]: a.ownedOut[253]: False
奇怪的是a.bounds是一个(xmin, xmax, ymin, ymax)的形式
查找最近的元素nearest(self, coordinates, num_results=1, objects=False): 返回的是一个python 生成器
寻找最近的点,num_result是返回的点的个数,如果有多个点的距离相等,那么这些点都返回
返回的点按照从短到长来依次排列
据我实验,num_result=0和num_result=1等同,num_result=-1,-2...的时候全部的点都会列出来
据我推测,两个矩形之间的距离是这样计算的:两个矩形区域a,b;分别取一点p,q,距离d=min(pq),
我用Python实现了一个这个方法
def getRangeDistance(range1, range2): """返回两个区间的最短距离,有重叠为0""" if min(range1) > max(range2): result = min(range1) - max(range2) return result if min(range2) > max(range1): result = min(range2) - max(range1) return result return 0def getRectangleDistance(coordinates1, coordinates2): """获得两个矩形之间距离的最短值""" (xmin1, ymin1, xmax1, ymax1) = coordinates1 (xmin2, ymin2, xmax2, ymax2) = coordinates2 tmp1 = getRangeDistance((xmin1, xmax1), (xmin2, xmax2)) tmp2 = getRangeDistance((ymin1, ymax1), (ymin2, ymax2)) distance = (tmp1 **2 + tmp2 **2) ** 0.5 return distance
实验结果如下
In [283]: list(c.nearest((10,10,19,19), num_results=-2))Out[283]: [1, 0, 0, 3]In [284]: list(f.nearest((0,0,0.9,0.9), num_results=0))Out[284]: []In [285]: list(c.nearest((0,0,0.9,0.9), num_results=1))Out[285]: [0, 0]In [286]: list(c.nearest((0,0,0.9,0.9), num_results=2))Out[286]: [0, 0]In [287]: list(c.nearest((0,0,0.9,0.9), num_results=3))Out[287]: [0, 0, 1]In [288]: list(c.nearest((0,0,0.9,0.9), num_results=4))Out[288]: [0, 0, 1, 3]In [289]: list(c.nearest((0,0,0.9,0.9), num_results=5))Out[289]: [0, 0, 1, 3]
当是空树时候无论如何都会返回一个空的生成器
查找某个范围内的对象个数 count(self, coordinates): 返回是一个长整数
In [291]: c.count((1,1,2,2))Out[291]: 3L
获得r树的范围get_bounds(self, coordinate_interleaved=None), 获得的是整个r树的范围
:param coordinate_interleaved: If True, the coordinates are turnedin the form [xmin, ymin, ..., kmin, xmax, ymax, ..., kmax],otherwise they are returned as[xmin, xmax, ymin, ymax, ..., ..., kmin, kmax]. If not specified,the :attr:`interleaved` member of the index is used, whichdefaults to True.
None的时候是由self.interleaved决定的,这个是r树生成时的参数默认是True
获得节点信息levels(self), 返回是一个列表,元素是(id, child_ids, bounds)
虽然名字叫做叶子节点但是实际上并不能搞得清楚是什么意思
In [295]: c.leaves()Out[295]: [(0, [0, 0, 1, 3], [-1.0, -1.0, 2.0, 2.0])]
太少了,看不清楚,再多加几个看一看
n [296]: for i in range(4,100): ...: c.insert(i,(i,i,i+0.5,i+0.5)) ...: In [297]: c.leaves()Out[297]: [(0, [0, 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99], [-1.0, -1.0, 99.5, 99.5])]
什么鬼,再加几个
for i in range(4,10000): ...: c.insert(i,(i,i,i+0.5,i+0.5))
过程略,
最后的结论就是这些id是叶子节点的上一层节点的信息,一个叶子节点至少有50个元素;所以至多应该是100个,最后的四个元素的列表是这个区域的范围
dumps是序列化,但是我们不要用这个对树进行序列化,因为叶子节点会丢失掉,这个只是调用的Python的pickle的dump序列化而已;序列化是序列内存空间的,就好像你序列化一个二叉树的一个节点,但是这个节点不包括他的子子节点内容,所以你在另一个文件中载入这个序列化,就不能知道他的子节点的内容信息,要用rtree自带的存储方法,
就到这吧