1 基本介绍
在PR四叉树中,每个节点代表一个矩形区域,并且每个节点要么没有子节点,要么有四个子节点,分别代表该矩形区域的四个象限
![](https://img-blog.csdnimg.cn/17c11622bc4d4268b16acf3767522819.png)
2 数据结构
PR四叉树的每个节点通常包含以下几个元素:
- 区域(矩形):节点所代表的二维空间范围。
- 点:存储在该区域内的点(通常只允许存储一个点,但也有变种)。
- 四个子节点:分别代表左上、右上、左下、右下四个象限。
3 插入
- 从根节点开始。
- 判断要插入的点是否在当前节点的区域内。
- 如果在,查看当前节点是否已经存储了点。
- 如果没有,存储这个点。
- 如果有,把当前区域分割成四个象限,然后把当前点和新点分别放入相应的象限。
- 递归进行这个过程。
3.1.1 举例
假设我们有以下几个点:(1, 1), (2, 2), (3, 3),我们想要在一个 4x4 的区域内用 PR 四叉树来存储它们
- 初始状态:
- 插入(1,1)
- 直接存储在根节点
![](https://img-blog.csdnimg.cn/60a8962fc3c44b08a10d238c7c3c1818.png)
- 插入 (2, 2)
- 将根节点分割成四个 2x2 的区域。将 (1, 1) 放入左下区域,(2, 2) 放入右上区域
![](https://img-blog.csdnimg.cn/cfba49c1310d4f119178327b3276a779.png)
- 插入(3,3)
- 同样放在右上,但由于右上已经有点(2,2),所以再次分割
![](https://img-blog.csdnimg.cn/15d92b479dd245349bfcdfe17f634bbb.png)
-
![](https://img-blog.csdnimg.cn/238985d140b14b5f854e2be6d36b90aa.jpeg)
参考内容:GIS空间数据库(21)PR四叉树索引 | 麻辣GIS (malagis.com)