网站建设总体设计北京摇号网站维护
数据结构笔记：R树-CSDN博客
1 基本介绍
- 使用Sort-Tile-Recursive (STR) 算法创建的仅查询的R-tree空间索引
- 该树索引每个几何图形的边界框。树在初始化时直接构建，且一旦创建后不能添加或移除节点
- 所有操作返回输入几何图形的索引
- 边界框限于二维并且是轴对齐的
- 几何图形中存在的任何Z值在树内索引时都会被忽略。
2 创建R树
STRtree(geoms, node_capacity)| geoms | 几何对象序列 |
| node_capacity | 树中每个父节点的最大子节点数，默认为10 |
3 属性
3.1 geometries
- 以用于构建树的顺序存储在树中的几何图形
from shapely import *
tree = STRtree([Point(i, i) for i in range(10)])
tree.geometries
'''
array([<POINT (0 0)>, <POINT (1 1)>, <POINT (2 2)>, <POINT (3 3)>,<POINT (4 4)>, <POINT (5 5)>, <POINT (6 6)>, <POINT (7 7)>,<POINT (8 8)>, <POINT (9 9)>], dtype=object)
'''4 方法
4.1 nearest
- 基于二维笛卡尔空间中的距离，返回树中每个输入几何图形的最近几何图形的索引
- 当输入几何图形与树几何图形相交时，此距离将为0
- 如果树中存在多个等距离或相交的几何图形，每个输入几何图形只返回一个结果，基于访问树几何图形的顺序；
- 此顺序可能是不确定的
from shapely import *
tree = STRtree([Point(i, i) for i in range(10)])'''
查询单个几何形状
'''
tree.nearest(Point(2.2,2.2))
#2
print(tree.geometries[2])
#POINT (2 2)'''
查询多个几何形状
'''
tree.nearest([Point(2.2, 2.2), Point(4.4, 4.4)])
#array([2, 4], dtype=int64)'''
如果存在等距的情况，只返回一个
'''
tree.nearest(Point(2.5,2.5))
#2
4.2 query
query(geometry, predicate=None, distance=None)- 返回每个输入几何图形与树几何图形的所有组合的整数索引
- 如果输入几何图形是标量，则返回形状为(n, )的数组，包含匹配树几何图形的索引
- 如果输入几何图形是array_like，则返回形状为(2,n)的数组，其中子数组对应于输入几何图形的索引和与每个相关联的树几何图形的索引
- 如果提供了谓词，则首先基于输入几何图形的边界框查询树几何图形，然后进一步过滤满足当比较输入几何图形与树几何图形时的谓词的那些几何图形
| geometry | 入查询树的几何图形 |
| predicate | 用于测试来自树的在输入几何图形的边界框内的几何图形的谓词 当你要查询一个形状与哪些其他形状有特定空间关系时， |
4.2.1 举例
- 单个几何形状
from shapely import *
points = [Point(0, 0), Point(1, 1), Point(2,2), Point(3, 3)]
tree = STRtree(points)tree.query(box(0, 0, 1, 1))
#array([0, 1], dtype=int64)
'''
表示查询几何体和创建R树的几何体中索引0，1的点有交集
'''- 多个几何形状
tree.query([box(0, 0, 1, 1), box(2, 2, 3, 3)])
'''
array([[0, 0, 1, 1],[0, 1, 2, 3]], dtype=int64)第一行表示 第几个查询几何体
第二行表示对应的查询几何体和创建R树的几何体的哪个索引有交集
'''tree.query([box(0, 0, 1, 1), box(2, 2, 3, 3)]).T
'''
array([[0, 0],[0, 1],[1, 2],[1, 3]], dtype=int64)这样每一行就是第几个查询集合体，对应创建R树的第几个几何体
'''- 带predicate
| None | 不应用任何特定的空间关系过滤，只考虑边界框的相交性 |
| intersects | 相交 |
| within | 如果查询的几何形状完全位于树中某个几何形状的内部，则返回True |
| contains | 与within相反，如果树中的几何形状完全包含于查询的几何形状，则返回True |
| overlaps | 如果查询的几何形状与树中的几何形状部分重叠，则返回True 用于面与面或线与线的关系判断 |
| crosses | 两个几何形状相交在某种程度上“穿过”对方，但不完全包含对方 通常用于不同维度的几何形状，如一条线穿过一个多边形，或者一条线与另一条线在某一点相交 |
| touches | 如果查询的几何形状与树中的几何形状仅在边界上有接触，而内部没有任何共享点，则返回True |
| covers | 如果查询的几何形状的边界和内部的所有点都包含在树中的几何形状的边界和内部，则返回True 【within 不允许在边界，covers可以】 |
| covered_by | 与covers相反 |
tree.query(box(0, 0, 1, 1),predicate='contains')
#array([], dtype=int64)4.3 query_nearest 最近几何图形的索引
基于二维笛卡尔空间中的距离，返回树中每个输入几何图形的最近几何图形的索引
【个人感觉，相当于nearest promax？】
query_nearest(geometry, max_distance=None, return_distance=False, exclusive=False, all_matches=True)4.3.1 主要参数
| geometry | 输入查询树的几何图形 |
| max_distance | 查询树中最近项目的最大距离。必须大于0 |
| return_distance | 如果为True，除了索引外还会返回距离 |
| exclusive | 如果为True，等于输入几何图形的最近树几何图形将不会被返回 |
| all_matches | 如果为True，每个输入几何图形的所有等距和相交几何图形都将被返回。如果为False，只返回第一个最近几何图形 |
4.3.2 举例
from shapely import *
points = [Point(0, 0), Point(1, 1), Point(2,2), Point(3, 3)]
tree = STRtree(points)- 单个点
tree.query_nearest(Point(0.25, 0.25))
#array([0], dtype=int64)- 多个点
返回的内容和query是一样的解释方法
tree.query_nearest([Point(2.5, 2.5), Point(1, 1)])
'''
array([[0, 0, 1],[2, 3, 1]], dtype=int64)
'''- all_matches
即使all_matches为False，返回的内容和nearest还是不一样；nearest返回的是一维数组，这边还是二维
tree.query_nearest([Point(2.5, 2.5), Point(1, 1)],all_matches=False)
'''
array([[0, 1],[2, 1]], dtype=int64)
'''- return_distance
tree.query_nearest(Point(0.25, 0.25),return_distance=True)
#(array([0], dtype=int64), array([0.35355339]))