空间数据索引 RTree 完全解析及 Java 实现

本文主要是介绍空间数据索引 RTree 完全解析及 Java 实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

最近在看空间数据索引的一些算法，感觉这哥们写的非常棒，特地转载过来。

第一部分 空间数据的背景介绍

空间数据的建模

基于实体的模型（基于对象）Entity-based models (or object based)

• 0-dimensional objects : 一般使用点 point 来表示那些对于不需要使用到形状信息的实体。
• 1-dimensional objects or linear objects: 用于表示一些路网的边，一般用于表示道路 road。 (polyline)
• 2-dimensional objects or surfacic objects: 用于表示有区域面积的实体。 (polygon)

常用的空间数据查询方式

• 窗口查询：给定一个查询窗口（通常是一个矩形），返回与查询窗口相重叠的物体。



点查询：给定一个点，返回包含这个点的所有几何图形。

空间数据获取的方法

• 通常，我们不选择去索引几何物体本身，而是采用最小限定箱 MBB（minimum bounding box ) 作为不规则几何图形的 key 来构建空间索引。

  • 在二维的情况下，我们称之为最小限定矩形。MBR(minimum bounding retangle)
    

  • 三维的情况下，我们称最新限定箱 MBB(minimum bounding box)
    

• 通过索引操作对象的 MBB 来进行查询一共分为两步

  • Filtering: 过滤掉 MBB 不相交的数据集，剩下的 MBB 被索引到的称为一个数据的超集。
    

  • Refinement: 测试实际的几何形状会不会满足查询条件，精确化。
    

  • 如何用数据表示一个 MBR

    通常，我们只需要两个点就可限定一个矩形，也就是矩形某个对角线的两个点就可以决定一个唯一的矩形。通常我们使用（左下，右上两个点表示）或者使用右上左下，都是可以的。



表示一个点的数据：

public class Point{ //用一个类来表示一个点public Float x;public Float y
}

表示一个 MBR 的数据

 
public class MBR{public Point BottomLeft;public Point TopRight;
}

• 如何判断两个 MBR 是否相交？ > 如果一个 MBR 的 TopLeft 或者 BottomRight 的（x，y）位于另一个 MBR 的 xRange 和 yRangle 里面，则说明这两个 MBR 相交。

 

 

R 树

对于 B/B+-Trees 由于它的线性特点，通常用来索引一维数据。（比它大的往一边走，比它小的往一边走，但只是在一个维度下进行比较）。
B 树是一棵平衡树，它是把一维直线分为若干段线段，当我们查找满足某个要求的点的时候，只要去查找它所属的线段即可。这种思想其实就是先找一个大的空间，再逐步缩小所要查找的空间，最终在一个自己设定的最小不可分空间内找出满足要求的解。一个典型的 B 树查找如下：




要查找某一满足条件的点，先去找到满足条件的线段，然后遍历所在线段上的点，即可找到答案。B 树是一种相对来说比较复杂的数据结构，尤其是在它的删除与插入操作过程中，因为它涉及到了叶子结点的分解与合并。

简介

B 树是解决低纬度数据（通常一维，也就是一个数据维度上进行比较），R 树很好的解决了这种高维空间搜索问题。它把 B 树的思想很好的扩展到了多维空间，采用了 B 树分割空间的思想（如果 B 树在一维的线段进行分割，R 树就是在二维甚至多维度的空间），并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R 树就是一棵用来存储高维数据的平衡树。


我们说过，B 树是采用切分线段来缩小数据查询范围的一种思想，我们又说了，R 树是 b 树的多维版，以及 R 树也采用了 B 树的这一种分割的思想，那么，如果说线段的分割是一维的分割。那二维的分割就应该是区域的分割，而三维的就是几何空间的分割了。要注意的是 R 树并不只是二维空间数据的索引而已，它还可以索引三维甚至更高维。

一个三维的 R 树


此外 R 树还可以退化成一维，但是分割的线段存在重叠问题，效果不如 Btree。


R 树的数据结构

如上所述，R 树是 B 树在高维空间的扩展，是一棵平衡树。每个 R 树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。

根据 R 树的这种数据结构，当我们需要进行一个高维空间查询时，我们只需要遍历少数几个叶子结点所包含的指针（即缩小到某个区域下去进行查询，还是采用缩小范围的思想），查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案，效率显著提高。下图 1 是 R 树的一个简单实例：





解释一下这张图。

• 首先我们假设所有数据都是二维空间下的几何形状，图中仅仅标志了 R8，R9，R10 区域中的数据，其他的叶子节点仅仅用 MBB 表示。为了实现 R 树结构，我们用一个最小边界矩形恰好框住这个不规则区域，这样，我们就构造出了一个区域：R8。R8 的特点很明显，就是正正好好框住所有在此区域中的数据。其他实线包围住的区域，如 R9，R10，R11 等都是同样的道理。这样一来，我们一共得到了 12 个最最基本的最小矩形。这些矩形都将被存储在子结点中。
• 下一步操作就是进行高一层次的处理。我们发现 R8，R9，R10 三个矩形距离最为靠近，因此就可以用一个更大的矩形 R3 恰好框住这 3 个矩形。
• 同样道理，R15，R16 被 R6 恰好框住，R11，R12 被 R4 恰好框住，等等。所有最基本的最小边界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住这些矩形。

用地图的例子来解释，就是所有的数据都是餐厅所对应的地点，先把相邻的餐厅划分到同一块区域，划分好所有餐厅之后，再把邻近的区域划分到更大的区域，划分完毕后再次进行更高层次的划分，直到划分到只剩下两个最大的区域为止。要查找的时候就方便了。

下面就可以把这些大大小小的矩形存入我们的 R 树中去了。根结点存放的是两个最大的矩形，这两个最大的矩形框住了所有的剩余的矩形，当然也就框住了所有的数据。下一层的结点存放了次大的矩形，这些矩形缩小了范围。每个叶子结点都是存放的最小的矩形，这些矩形中可能包含有 n 个数据。

以餐厅为例，假设我要查询广州市天河区天河城附近一公里的所有餐厅地址怎么办？

• 打开地图（也就是整个 R 树），先选择国内还是国外（也就是根结点）。
• 然后选择华南地区（对应第一层结点），选择广州市（对应第二层结点），
• 再选择天河区（对应第三层结点），
• 最后选择天河城所在的那个区域（对应叶子结点，存放有最小矩形），遍历所有在此区域内的结点，看是否满足我们的要求即可。

R 树的查找规则跟查地图很像吧？对应下图：



一个更具体的使用场景

假设我们有一个地图路网要进行道路的快速索引，那么我们可以将每一条路的最小 MBB 作为 R 树的数据单元来进行构建 R 树。


每一条路使用一个最小 MBB 来进行包裹，使它成为 R 树的叶子结点（也就是那些数据结点）


（这里采用的是 R 树的改进版本 R*树）然后对于建立起来的 R 树在进行查找道路的使用就可以使用我们那种“缩小范围”的查找思想。从上往下一层一层查找。


一棵 R 树满足如下的性质：

• 1. 除非它是根结点之外，所有叶子结点包含有 m 至 M 个记录索引（条目）。作为根结点的叶子结点所具有的记录个数可以少于 m。通常，m=M/2。
• 2. 对于所有在叶子中存储的记录（条目），I 是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意：此处所说的“矩形”是可以扩展到高维空间的）。
• 3. 每一个非叶子结点拥有 m 至 M 个孩子结点，除非它是根结点。
• 4. 对于在非叶子结点上的每一个条目，i 是最小的可以在空间上完全覆盖这些条目所代表的点的矩形（同性质 2）。
• 5. 所有叶子结点都位于同一层，因此 R 树为平衡树。

结点的结构

先来探究一下叶子结点的结构。叶子结点所保存的数据形式为：(I, tuple-identifier)。

其中，tuple-identifier 表示的是一个存放于数据库中的 tuple，也就是一条记录，它是 n 维的。I 是一个 n 维空间的矩形，并可以恰好框住这个叶子结点中所有记录代表的 n 维空间中的点。I=(I0,I1,…,In-1)。其结构如下图所示：



Rectangle 代表可以包裹 E1,E2,E3,E4.E5 的最小限度框。


R 树的操作

搜索

R 树的搜索操作很简单，跟 B 树上的搜索十分相似。它返回的结果是所有符合查找信息的记录条目。而输入是什么？输入不仅仅是一个范围了，它更可以看成是一个空间中的矩形。也就是说，我们输入的是一个搜索矩形。
先给出伪代码：

Function：Search
描述：假设 T 为一棵 R 树的根结点，查找所有搜索矩形 S 覆盖的记录条目。

• S1:[查找子树] 如果 T 是非叶子结点，如果 T 所对应的矩形与 S 有重合，那么检查所有 T 中存储的条目，对于所有这些条目，使用 Search 操作作用在每一个条目所指向的子树的根结点上（即 T 结点的孩子结点）。
• S2:[查找叶子结点] 如果 T 是叶子结点，如果 T 所对应的矩形与 S 有重合，那么直接检查 S 所指向的所有记录条目。返回符合条件的记录。

我们通过下图来理解这个 Search 操作。


红色查询区域与 P3 子树 P4 子树相重叠，所以根据“缩小空间”的思想，只需要遍历 P3 和 P4 所在子树就行而无需遍历 P1，P2.

插入

插入操作存在的情况

R 树的插入操作也同 B 树的插入操作类似。当新的数据记录需要被添加入叶子结点时，若叶子结点溢出，那么我们需要对叶子结点进行分裂操作。显然，叶子结点的插入操作会比搜索操作要复杂。插入操作需要一些辅助方法才能够完成。
来看一下伪代码：

【Function：Insert】
描述：将新的记录条目 E 插入给定的 R 树中。

 

• 本文地址：https://www.6aiq.com/article/1545489399899
• 本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出

 

• I1：[为新记录找到合适插入的叶子结点]开始 ChooseLeaf 方法选择叶子结点 L 以放置记录 E。
• I2：[添加新记录至叶子结点] 如果 L 有足够的空间来放置新的记录条目，则向 L 中添加 E。如果没有足够的空间，则进行 SplitNode 方法以获得两个结点 L 与 LL，这两个结点包含了所有原来叶子结点 L 中的条目与新条目 E。
• I3：[将变换向上传递] 开始对结点 L 进行 AdjustTree 操作，如果进行了分裂操作，那么同时需要对 LL 进行 AdjustTree 操作。
• I4：[对树进行增高操作] 如果结点分裂，且该分裂向上传播导致了根结点的分裂，那么需要创建一个新的根结点，并且让它的两个孩子结点分别为原来那个根结点分裂后的两个结点。

【Function：ChooseLeaf】
描述：选择叶子结点以放置新条目 E。

• CL1：[Initialize]设置 N 为根结点。
• CL2：[叶子结点的检查] 如果 N 为叶子结点，则直接返回 N。
• CL3：[选择子树] 如果 N 不是叶子结点，则遍历 N 中的结点，找出添加 E.I 时扩张最小的结点，并把该结点定义为 F。如果有多个这样的结点，那么选择面积最小的结点。
• CL4：[下降至叶子结点] 将 N 设为 F，从 CL2 开始重复操作。

---

【Function：AdjustTree】
描述：叶子结点的改变向上传递至根结点以改变各个矩阵。在传递变换的过程中可能会产生结点的分裂。

• AT1：[初始化] 将 N 设为 L。
• AT2：[检验是否完成] 如果 N 为根结点，则停止操作。
• AT3：[调整父结点条目的最小边界矩形] 设 P 为 N 的父节点，EN 为指向在父节点 P 中指向 N 的条目。调整 EN.I 以保证所有在 N 中的矩形都被恰好包围。
• AT4：[向上传递结点分裂] 如果 N 有一个刚刚被分裂产生的结点 NN，则创建一个指向 NN 的条目 ENN。如果 P 有空间来存放 ENN，则将 ENN 添加到 P 中。如果没有，则对 P 进行 SplitNode 操作以得到 P 和 PP。
• AT5：[升高至下一级] 如果 N 等于 L 且发生了分裂，则把 NN 置为 PP。从 AT2 开始重复操作。

有足够的空间插入的情况，由于插入的 x 所在的区域 P2 的数据条目仍然有足够的空间容纳条目 x，且 x 的区域面积即 MBR 也位于区域 P2 之内，所以这种情况下，我们认为 x 拥有足够的插入空间。



需要增大 MBR 的插入情况，由于插入的 y 所在的区域 P2 的数据条目仍然有足够的空间容纳条目 y，但是 y 的区域面积即 MBR 并不完全位于 P2 的区域之内，因此我们在插入数据 y 后会导致 P2 区域的相应扩大。



需要进行分裂的插入情况，由于插入的 w 所在的区域 P1 的数据条目已经没有足够的空间容纳条目 w，因为假设我们定义 R 树的阶 m=4，而区域 P1 已经容纳了四个条目「A，B，C，K」了，插入 w 后孩子数为 5，以及超过 m=4 了，所以要进行分类操作，来保证树的平衡性。



采用分裂算法（下面会进行介绍）对结点（或者说区域）P2 进行合理地分裂。使其分裂成 P1（包含 A，B）和 P5（包含 k，w）两个结点。并且需要向上传递这种分裂。由于分裂之后原来根结点「P1，P2，P3，P4」变成了「P1，P2，P3，P，P5」，因此根结点的孩子数由 4 变成 5，超过了阶数 m=4.所以根结点要（采用我们的分裂算法）进行分裂，分裂成 Q1（包含 P1，P5，P2）和 Q2（包含 P3，P4）两个结点，由于此时分裂已经传递到根结点，所以生成新的根结点记录 Q1，Q2。



如何合理地分裂到两个组



挑选种子有多个方法，这里 Quadratic（二次方）方案，对于所有条目中的每一对 E1 和 E2，计算可以包裹着 E1，E2 的最小限定框 J=MBR(E1, E2) ，然后计算增量 d= J-E1-E2.计算结束后选择 d 最大的一对（即增量最大）。（这里为什么要这样呢：之所以要挑选 d 最大的一对，是因为如果 d 较大，说明挑选出来的两对条目基于对角线离得比较远，这样的好处就是分裂后的两个分组可以尽量不重叠）





挑选出 seed1 和 seed2 之后，就将剩下的要分配的分裂条目分个这两个 seed 使它们各称为一个组。而这个分配的原则就是离谁比较“近”就和谁一组。这里的“近”指的是任何一个条目 MBB--E 和 seed1，seed2 分别计算可以包裹着 E 和 seed1 的最小限定框 J1=MBR(E，seed1)， 可以包裹着 E 和 seed2 的最小限定框 J2=MBR(E，seed2)。再分别计算增量 d1=J1-E-seed1，d2=J2-E-seed2。d1，d2 哪个小就说明哪个“近”。



（-_-）!!!所以分裂的具体情况还是很复杂的，真想不懂这些大神怎么会想得到这些。除了上述 Quadratic 的分裂算法之外还有其他的分裂算法，如下图中间图，但是分裂的效果都不如 R*树（R 树的改进版）的算法好。




删除

R 树的删除操作与 B 树的删除操作会有所不同，不过同 B 树一样，会涉及到压缩等操作。相信读者看完以下的伪代码之后会有所体会。R 树的删除同样是比较复杂的，需要用到一些辅助函数来完成整个操作。
伪代码如下：

【Function：Delete】
描述：将一条记录 E 从指定的 R 树中删除。
D1：[找到含有记录的叶子结点] 使用 FindLeaf 方法找到包含有记录 E 的叶子结点 L。如果搜索失败，则直接终止。
D2：[删除记录] 将 E 从 L 中删除。
D3：[传递记录] 对 L 使用 CondenseTree 操作
D4：[缩减树] 当经过以上调整后，如果根结点只包含有一个孩子结点，则将这个唯一的孩子结点设为根结点。

【Function：FindLeaf】
描述：根结点为 T，期望找到包含有记录 E 的叶子结点。
FL1：[搜索子树] 如果 T 不是叶子结点，则检查每一条 T 中的条目 F，找出与 E 所对应的矩形相重合的 F（不必完全覆盖）。对于所有满足条件的 F，对其指向的孩子结点进行 FindLeaf 操作，直到寻找到 E 或者所有条目均以被检查过。
FL2：[搜索叶子结点以找到记录] 如果 T 是叶子结点，那么检查每一个条目是否有 E 存在，如果有则返回 T。

【Function：CondenseTree】
描述：L 为包含有被删除条目的叶子结点。如果 L 的条目数过少（小于要求的最小值 m），则必须将该叶子结点 L 从树中删除。经过这一删除操作，L 中的剩余条目必须重新插入树中。此操作将一直重复直至到达根结点。同样，调整在此修改树的过程所经过的路径上的所有结点对应的矩形大小。
CT1：[初始化] 令 N 为 L。初始化一个用于存储被删除结点包含的条目的链表 Q。
CT2：[找到父条目] 如果 N 为根结点，那么直接跳转至 CT6。否则令 P 为 N 的父结点，令 EN 为 P 结点中存储的指向 N 的条目。
CT3：[删除下溢结点] 如果 N 含有条目数少于 m，则从 P 中删除 EN，并把结点 N 中的条目添加入链表 Q 中。
CT4：[调整覆盖矩形] 如果 N 没有被删除，则调整 EN.I 使得其对应矩形能够恰好覆盖 N 中的所有条目所对应的矩形。
CT5：[向上一层结点进行操作] 令 N 等于 P，从 CT2 开始重复操作。
CT6：[重新插入孤立的条目] 所有在 Q 中的结点中的条目需要被重新插入。原来属于叶子结点的条目可以使用 Insert 操作进行重新插入，而那些属于非叶子结点的条目必须插入删除之前所在层的结点，以确保它们所指向的子树还处于相同的层。

R 树删除记录过程中的 CondenseTree 操作是不同于 B 树的。我们知道，B 树删除过程中，如果出现结点的记录数少于半满（即下溢）的情况，则直接把这些记录与其他叶子的记录“融合”，也就是说两个相邻结点合并。然而 R 树却是直接重新插入。
具体的例子



假设结点最大条目数为 4，最小条目数为 2。在这张图中，我们的目标是删除记录 c。首先使用 FindLeaf 操作找到 c 所处在的叶子结点的位置——R11。当 c 从 R11 删除时，R11 就只有一条记录了，少于最小条目数 2，出现下溢，此时要调用 CondenseTree 操作。这样，c 被删除，R11 剩余的条目——指向记录 d 的指针——被插入链表 Q。然后向更高一层的结点进行此操作。这样 R12 会被插入链表中。原理是一样的，在这里就不再赘述。


有一点需要解释的是，我们发现这个删除操作向上传递之后，根结点的条目 R1 也被插入了 Q 中，这样根结点只剩下了 R2。别着急，重新插入操作会有效的解决这个问题。我们插入 R3，R12，d 至它原来所处的层。这样，我们发现根结点只有一个条目了，此时根据 Inert 中的操作，我们把这个根结点删除，它的孩子结点，即 R5，R6，R7，R3 所在的结点被置为根结点。至此，删除操作结束。

另一个例子再次理解删除





















第二部分 R 树的 Java 实现

UML



package rtree;/*** @ClassName Point* @Description n维空间中的点，所有的维度被存储在一个float数组中*/
public class Point implements Cloneable {private float[] data;public Point(float[] data) {if (data == null) {throw new IllegalArgumentException("Coordinates cannot be null."); // ★坐标不能为空}if (data.length < 2) {throw new IllegalArgumentException("Point dimension should be greater than 1."); // ★点的维度必须大于1}this.data = new float[data.length];System.arraycopy(data, 0, this.data, 0, data.length); // 复制数组}public Point(int[] data) {if (data == null) {throw new IllegalArgumentException("Coordinates cannot be null."); // ★坐标不能为空}if (data.length < 2) {throw new IllegalArgumentException("Point dimension should be greater than 1."); // ★点的维度必须大于1}this.data = new float[data.length];for (int i = 0; i < data.length; i++) {this.data[i] = data[i]; // 复制数组}}@Override // 重写clone接口protected Object clone() {float[] copy = new float[data.length];System.arraycopy(data, 0, copy, 0, data.length);return new Point(copy);}@Override // 重写tostring（）方法public String toString() {StringBuffer sBuffer = new StringBuffer("(");for (int i = 0; i < data.length - 1; i++) {sBuffer.append(data[i]).append(",");}sBuffer.append(data[data.length - 1]).append(")"); // 最后一位数据后面不再添加逗号，追加放在循环外面return sBuffer.toString();}/** ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ ★ 测试 ★* ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★*/public static void main(String[] args) {float[] test = { 1.2f, 2f, 34f };Point point1 = new Point(test);System.out.println(point1);int[] test2 = { 1, 2, 3, 4 };point1 = new Point(test2);System.out.println(point1);int[] test3 = { 11, 22 }; // 二维的点point1 = new Point(test3);System.out.println(point1);}/*** @return 返回Point的维度*/public int getDimension() {return data.length;}/*** @param index* @return 返回Point坐标第i位的float值*/public float getFloatCoordinate(int index) {return data[index];}/*** @param index* @return 返回Point坐标第i位的int值*/public int getIntCoordinate(int index) {return (int) data[index];}@Overridepublic boolean equals(Object obj) {if (obj instanceof Point) // 如果obj是point的实例{Point point = (Point) obj;if (point.getDimension() != getDimension()) // 维度相同的点才能比较throw new IllegalArgumentException("Points must be of equal dimensions to be compared.");for (int i = 0; i < getDimension(); i++) {if (getFloatCoordinate(i) != point.getFloatCoordinate(i))return false;}}if (!(obj instanceof Point))return false;return true;}
}

Rectangle

package rtree;/*** 外包矩形* * @ClassName Rectangle* @Description*/
public class Rectangle implements Cloneable // 继承克隆接口
{private Point low; // 左下角的点private Point high; // 右上角的点public Rectangle(Point p1, Point p2) // 初始化时，第一个参数为左下角，第二个参数为右上角{if (p1 == null || p2 == null) // 点对象不能为空{throw new IllegalArgumentException("Points cannot be null.");}if (p1.getDimension() != p2.getDimension()) // 点的维度应该相等{throw new IllegalArgumentException("Points must be of same dimension.");}// 先左下角后右上角for (int i = 0; i < p1.getDimension(); i++) {if (p1.getFloatCoordinate(i) > p2.getFloatCoordinate(i)) {throw new IllegalArgumentException("坐标点为先左下角后右上角");}}low = (Point) p1.clone();high = (Point) p2.clone();}/*** 返回Rectangle左下角的Point* * @return Point*/public Point getLow() {return (Point) low.clone();}/*** 返回Rectangle右上角的Point* * @return Point*/public Point getHigh() {return high;}/*** @param rectangle* @return 包围两个Rectangle的最小Rectangle*/public Rectangle getUnionRectangle(Rectangle rectangle) {if (rectangle == null) // 矩形不能为空throw new IllegalArgumentException("Rectangle cannot be null.");if (rectangle.getDimension() != getDimension()) // 矩形维度必须相同{throw new IllegalArgumentException("Rectangle must be of same dimension.");}float[] min = new float[getDimension()];float[] max = new float[getDimension()];for (int i = 0; i < getDimension(); i++) {// 第一个参数是当前矩形的坐标值，第二个参数是传入的参数的矩形的坐标值min[i] = Math.min(low.getFloatCoordinate(i), rectangle.low.getFloatCoordinate(i));max[i] = Math.max(high.getFloatCoordinate(i), rectangle.high.getFloatCoordinate(i));}return new Rectangle(new Point(min), new Point(max));}/*** @return 返回Rectangle的面积*/public float getArea() {float area = 1;for (int i = 0; i < getDimension(); i++) {area *= high.getFloatCoordinate(i) - low.getFloatCoordinate(i);}return area;}/*** @param rectangles* @return 包围一系列Rectangle的最小Rectangle*/public static Rectangle getUnionRectangle(Rectangle[] rectangles) {if (rectangles == null || rectangles.length == 0)throw new IllegalArgumentException("Rectangle array is empty.");Rectangle r0 = (Rectangle) rectangles[0].clone();for (int i = 1; i < rectangles.length; i++) {r0 = r0.getUnionRectangle(rectangles[i]); // 获得包裹矩形r0与r[i]的最小边界的矩形再赋值给r0}return r0; // 返回包围一系列Rectangle的最小Rectangle}@Override// 重写clone()函数protected Object clone() {Point p1 = (Point) low.clone();Point p2 = (Point) high.clone();return new Rectangle(p1, p2);}@Override// 重写tostring()方法public String toString() {return "Rectangle Low:" + low + " High:" + high;}/** ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ ★ 测试 ★* ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★*/public static void main(String[] args) {// 新建两point再根据两个point构建一个Rectanglefloat[] f1 = { 1.3f, 2.4f };float[] f2 = { 3.4f, 4.5f };Point p1 = new Point(f1);Point p2 = new Point(f2);Rectangle rectangle = new Rectangle(p1, p2);System.out.println(rectangle);// Point point = rectangle.getHigh();// point = p1;// System.out.println(rectangle);float[] f_1 = { -2f, 0f };float[] f_2 = { 0f, 2f };float[] f_3 = { -2f, 1f };float[] f_4 = { 3f, 3f };float[] f_5 = { 1f, 0f };float[] f_6 = { 2f, 4f };p1 = new Point(f_1);p2 = new Point(f_2);Point p3 = new Point(f_3);Point p4 = new Point(f_4);Point p5 = new Point(f_5);Point p6 = new Point(f_6);Rectangle re1 = new Rectangle(p1, p2);Rectangle re2 = new Rectangle(p3, p4);Rectangle re3 = new Rectangle(p5, p6);// Rectangle re4 = new Rectangle(p3, p4); //输入要先左下角，再右上角System.out.println(re1.isIntersection(re2));System.out.println(re1.isIntersection(re3));System.out.println(re1.intersectingArea(re2));System.out.println(re1.intersectingArea(re3));}/*** 两个Rectangle相交的面积* * @param rectangle*            Rectangle* @return float*/public float intersectingArea(Rectangle rectangle) {if (!isIntersection(rectangle)) // 如果不相交，相交面积为0{return 0;}float ret = 1;// 循环一次，得到一个维度的相交的边，累乘多个维度的相交的边，即为面积for (int i = 0; i < rectangle.getDimension(); i++) {float l1 = this.low.getFloatCoordinate(i);float h1 = this.high.getFloatCoordinate(i);float l2 = rectangle.low.getFloatCoordinate(i);float h2 = rectangle.high.getFloatCoordinate(i);// rectangle1在rectangle2的左边if (l1 <= l2 && h1 <= h2) {ret *= (h1 - l1) - (l2 - l1);}// rectangle1在rectangle2的右边else if (l1 >= l2 && h1 >= h2) {ret *= (h2 - l2) - (l1 - l2);}// rectangle1在rectangle2里面else if (l1 >= l2 && h1 <= h2) {ret *= h1 - l1;}// rectangle1包含rectangle2else if (l1 <= l2 && h1 >= h2) {ret *= h2 - l2;}}return ret;}/*** @param rectangle* @return 判断两个Rectangle是否相交*/public boolean isIntersection(Rectangle rectangle) {if (rectangle == null)throw new IllegalArgumentException("Rectangle cannot be null.");if (rectangle.getDimension() != getDimension()) // 进行判断的两个矩形维度必须相等{throw new IllegalArgumentException("Rectangle cannot be null.");}for (int i = 0; i < getDimension(); i++) {/** 当前矩形左下角的坐标值大于传入矩形右上角的坐标值 || 当前矩形右上角角的坐标值小于传入矩形左下角的坐标值*/if (low.getFloatCoordinate(i) > rectangle.high.getFloatCoordinate(i)|| high.getFloatCoordinate(i) < rectangle.low.getFloatCoordinate(i)) {return false; // 没有相交}}return true;}/*** @return 返回Rectangle的维度*/private int getDimension() {return low.getDimension();}/*** 判断rectangle是否被包围* * @param rectangle* @return*/public boolean enclosure(Rectangle rectangle) {if (rectangle == null) // 矩形不能为空throw new IllegalArgumentException("Rectangle cannot be null.");if (rectangle.getDimension() != getDimension()) // 判断的矩形必须维度相同throw new IllegalArgumentException("Rectangle dimension is different from current dimension.");// 只要传入的rectangle有一个维度的坐标越界了就不被包含for (int i = 0; i < getDimension(); i++) {if (rectangle.low.getFloatCoordinate(i) < low.getFloatCoordinate(i)|| rectangle.high.getFloatCoordinate(i) > high.getFloatCoordinate(i))return false;}return true;}@Override// 重写equals方法public boolean equals(Object obj) {if (obj instanceof Rectangle) {Rectangle rectangle = (Rectangle) obj;if (low.equals(rectangle.getLow()) && high.equals(rectangle.getHigh()))return true;}return false;}
}

RTNode

 
package rtree;import java.util.List;
import rtree.Constants;/*** @ClassName RTNode* @Description*/
public abstract class RTNode {protected RTree rtree; // 结点所在的树protected int level; // 结点所在的层protected Rectangle[] datas; // 相当于条目protected RTNode parent; // 父节点protected int usedSpace; // 结点已用的空间protected int insertIndex; // 记录插入的搜索路径索引protected int deleteIndex; // 记录删除的查找路径索引/*** 构造函数初始化*/public RTNode(RTree rtree, RTNode parent, int level) {this.rtree = rtree;this.parent = parent;this.level = level;datas = new Rectangle[rtree.getNodeCapacity() + 1];// 多出的一个用于结点分裂usedSpace = 0;}/*** @return 返回父节点*/public RTNode getParent() {return parent;}/*** -->向结点中添加Rectangle，即添加条目* * @param rectangle*/protected void addData(Rectangle rectangle) {// 如果节点已用空间==r树的节点容量if (usedSpace == rtree.getNodeCapacity()) {throw new IllegalArgumentException("Node is full.");}datas[usedSpace++] = rectangle;}/*** -->删除结点中的第i个条目* * @param i*/protected void deleteData(int i) {if (datas[i + 1] != null) // 如果为中间节点（非尾节点），采用拷贝数组的方式链接条目{System.arraycopy(datas, i + 1, datas, i, usedSpace - i - 1);datas[usedSpace - 1] = null;} else // 如果为末尾节点，将节点置空datas[i] = null;// 删除之后已用节点自减usedSpace--;}/*** 压缩算法 叶节点L中刚刚删除了一个条目，如果这个结点的条目数太少下溢， 则删除该结点，同时将该结点中剩余的条目重定位到其他结点中。* 如果有必要，要逐级向上进行这种删除，调整向上传递的路径上的所有外包矩形，使其尽可能小，直到根节点。* * @param list*            存储删除结点中剩余条目*/protected void condenseTree(List<RTNode> list) {if (isRoot()) {// 根节点只有一个条目了，即只有左孩子或者右孩子 ，// 将唯一条目删除，释放根节点，将原根节点唯一的孩子设置为新根节点if (!isLeaf() && usedSpace == 1) {RTDirNode root = (RTDirNode) this;RTNode child = root.getChild(0);root.children.remove(this);child.parent = null;rtree.setRoot(child);}} else {RTNode parent = getParent();// 计算节点最小容量，用于判断是否引起下溢int min = Math.round(rtree.getNodeCapacity() * rtree.getFillFactor());if (usedSpace < min) {parent.deleteData(parent.deleteIndex);// 其父节点中删除此条目((RTDirNode) parent).children.remove(this);this.parent = null;list.add(this);// 之前已经把数据删除了} else {parent.datas[parent.deleteIndex] = getNodeRectangle();}parent.condenseTree(list);}}/*** 分裂结点的平方算法* <p>* 1、为两个组选择第一个条目--调用算法pickSeeds()来为两个组选择第一个元素，分别把选中的两个条目分配到两个组当中。<br>* 2、检查是否已经分配完毕，如果一个组中的条目太少，为避免下溢，将剩余的所有条目全部分配到这个组中，算法终止<br>* 3、调用pickNext来选择下一个进行分配的条目--计算把每个条目加入每个组之后面积的增量，选择两个组面积增量差最大的条目索引,* 如果面积增量相等则选择面积较小的组，若面积也相等则选择条目数更少的组<br>* * @param rectangle*            导致分裂的溢出Rectangle* @return 两个组中的条目的索引*/protected int[][] quadraticSplit(Rectangle rectangle) {if (rectangle == null) {throw new IllegalArgumentException("Rectangle cannot be null.");}datas[usedSpace] = rectangle; // 先添加进去int total = usedSpace + 1; // 结点总数// 标记访问的条目int[] mask = new int[total];for (int i = 0; i < total; i++) {mask[i] = 1;}// 分裂后每个组只是有total/2个条目int c = total / 2 + 1;// 每个结点最小条目个数int minNodeSize = Math.round(rtree.getNodeCapacity() * rtree.getFillFactor());// 至少有两个if (minNodeSize < 2)minNodeSize = 2;// 记录没有被检查的条目的个数int rem = total;int[] group1 = new int[c];// 记录分配的条目的索引int[] group2 = new int[c];// 记录分配的条目的索引// 跟踪被插入每个组的条目的索引int i1 = 0, i2 = 0;int[] seed = pickSeeds();group1[i1++] = seed[0];group2[i2++] = seed[1];rem -= 2;mask[group1[0]] = -1;mask[group2[0]] = -1;while (rem > 0) {// 将剩余的所有条目全部分配到group1组中，算法终止if (minNodeSize - i1 == rem) {for (int i = 0; i < total; i++)// 总共rem个{if (mask[i] != -1)// 还没有被分配{group1[i1++] = i;mask[i] = -1;rem--;}}// 将剩余的所有条目全部分配到group1组中，算法终止} else if (minNodeSize - i2 == rem) {for (int i = 0; i < total; i++)// 总共rem个{if (mask[i] != -1)// 还没有被分配{group2[i2++] = i;mask[i] = -1;rem--;}}} else {// 求group1中所有条目的最小外包矩形Rectangle mbr1 = (Rectangle) datas[group1[0]].clone();for (int i = 1; i < i1; i++) {mbr1 = mbr1.getUnionRectangle(datas[group1[i]]);}// 求group2中所有条目的外包矩形Rectangle mbr2 = (Rectangle) datas[group2[0]].clone();for (int i = 1; i < i2; i++) {mbr2 = mbr2.getUnionRectangle(datas[group2[i]]);}// 找出下一个进行分配的条目double dif = Double.NEGATIVE_INFINITY;double areaDiff1 = 0, areaDiff2 = 0;int sel = -1;for (int i = 0; i < total; i++) {if (mask[i] != -1)// 还没有被分配的条目{// 计算把每个条目加入每个组之后面积的增量，选择两个组面积增量差最大的条目索引Rectangle a = mbr1.getUnionRectangle(datas[i]);areaDiff1 = a.getArea() - mbr1.getArea();Rectangle b = mbr2.getUnionRectangle(datas[i]);areaDiff2 = b.getArea() - mbr2.getArea();if (Math.abs(areaDiff1 - areaDiff2) > dif) {dif = Math.abs(areaDiff1 - areaDiff2);sel = i;}}}if (areaDiff1 < areaDiff2)// 先比较面积增量{group1[i1++] = sel;} else if (areaDiff1 > areaDiff2) {group2[i2++] = sel;} else if (mbr1.getArea() < mbr2.getArea())// 再比较自身面积{group1[i1++] = sel;} else if (mbr1.getArea() > mbr2.getArea()) {group2[i2++] = sel;} else if (i1 < i2)// 最后比较条目个数{group1[i1++] = sel;} else if (i1 > i2) {group2[i2++] = sel;} else {group1[i1++] = sel;}mask[sel] = -1;rem--;}} // end whileint[][] ret = new int[2][];ret[0] = new int[i1];ret[1] = new int[i2];for (int i = 0; i < i1; i++) {ret[0][i] = group1[i];}for (int i = 0; i < i2; i++) {ret[1][i] = group2[i];}return ret;}/*** 1、对每一对条目E1和E2，计算包围它们的Rectangle J，计算d = area(J) - area(E1) - area(E2);<br>* 2、Choose the pair with the largest d* * @return 返回两个条目如果放在一起会有最多的冗余空间的条目索引*/protected int[] pickSeeds() {double inefficiency = Double.NEGATIVE_INFINITY;int i1 = 0, i2 = 0;// 两个for循环对任意两个条目E1和E2进行组合for (int i = 0; i < usedSpace; i++) {for (int j = i + 1; j <= usedSpace; j++)// 注意此处的j值{Rectangle rectangle = datas[i].getUnionRectangle(datas[j]);double d = rectangle.getArea() - datas[i].getArea() - datas[j].getArea();if (d > inefficiency) {inefficiency = d;i1 = i;i2 = j;}}}return new int[] { i1, i2 }; // 返回拥有最小d的一对条目}/*** @return 返回包含结点中所有条目的最小Rectangle*/public Rectangle getNodeRectangle() {if (usedSpace > 0) {Rectangle[] rectangles = new Rectangle[usedSpace];System.arraycopy(datas, 0, rectangles, 0, usedSpace);return Rectangle.getUnionRectangle(rectangles); // 返回包含这一系列矩形的最小矩形} else {return new Rectangle(new Point(new float[] { 0, 0 }), new Point(new float[] { 0, 0 }));}}/*** @return 是否根节点*/public boolean isRoot() {return (parent == Constants.NULL);}/*** @return 是否非叶子结点*/public boolean isIndex() {return (level != 0);}/*** @return 是否叶子结点*/public boolean isLeaf() {return (level == 0);}/*** <b>步骤CL1：</b>初始化――记R树的根节点为N。<br>* <b>步骤CL2：</b>检查叶节点――如果N是个叶节点，返回N<br>* <b>步骤CL3：</b>选择子树――如果N不是叶节点，则从N中所有的条目中选出一个最佳的条目F，* 选择的标准是：如果E加入F后，F的外廓矩形FI扩张最小，则F就是最佳的条目。如果有两个* 条目在加入E后外廓矩形的扩张程度相等，则在这两者中选择外廓矩形较小的那个。<br>* <b>步骤CL4：</b>向下寻找直至达到叶节点――记Fp指向的孩子节点为N，然后返回步骤CL2循环运算， 直至查找到叶节点。* <p>* * @param Rectangle* @return RTDataNode*/protected abstract RTDataNode chooseLeaf(Rectangle rectangle);/*** R树的根节点为T，查找包含rectangle的叶子结点* <p>* 1、如果T不是叶子结点，则逐个查找T中的每个条目是否包围rectangle，若包围则递归调用findLeaf()<br>* 2、如果T是一个叶子结点，则逐个检查T中的每个条目能否匹配rectangle<br>* * @param rectangle* @return 返回包含rectangle的叶节点*/protected abstract RTDataNode findLeaf(Rectangle rectangle);}

RTDataNode

package rtree;import java.util.ArrayList;
import java.util.List;import rtree.Constants;/*** @ClassName RTDataNode* @Description 叶子结点*/
public class RTDataNode extends RTNode {public RTDataNode(RTree rTree, RTNode parent) {super(rTree, parent, 0);}/*** -->叶节点中插入Rectangle 在叶节点中插入Rectangle，插入后如果其父节点不为空则需要向上调整树直到根节点；* 如果其父节点为空，则是从根节点插入 若插入Rectangle之后超过结点容量则需要分裂结点 【注】插入数据后，从parent处开始调整数据* * @param rectangle* @return*/public boolean insert(Rectangle rectangle) {if (usedSpace < rtree.getNodeCapacity()) // 已用节点小于节点容量{datas[usedSpace++] = rectangle;RTDirNode parent = (RTDirNode) getParent();if (parent != null)// 调整树，但不需要分裂节点，因为 节点小于节点容量，还有空间parent.adjustTree(this, null);return true;}// 超过结点容量else {RTDataNode[] splitNodes = splitLeaf(rectangle);RTDataNode l = splitNodes[0];RTDataNode ll = splitNodes[1];if (isRoot()) {// 根节点已满，需要分裂。创建新的根节点RTDirNode rDirNode = new RTDirNode(rtree, Constants.NULL, level + 1);rtree.setRoot(rDirNode);// getNodeRectangle()返回包含结点中所有条目的最小RectanglerDirNode.addData(l.getNodeRectangle());rDirNode.addData(ll.getNodeRectangle());ll.parent = rDirNode;l.parent = rDirNode;rDirNode.children.add(l);rDirNode.children.add(ll);} else {// 不是根节点RTDirNode parentNode = (RTDirNode) getParent();parentNode.adjustTree(l, ll);}}return true;}/*** 叶子节点的分裂 插入Rectangle之后超过容量需要分裂* * @param rectangle* @return*/public RTDataNode[] splitLeaf(Rectangle rectangle) {int[][] group = null;switch (rtree.getTreeType()) {case Constants.RTREE_LINEAR:break;case Constants.RTREE_QUADRATIC:group = quadraticSplit(rectangle);break;case Constants.RTREE_EXPONENTIAL:break;case Constants.RSTAR:break;default:throw new IllegalArgumentException("Invalid tree type.");}RTDataNode l = new RTDataNode(rtree, parent);RTDataNode ll = new RTDataNode(rtree, parent);int[] group1 = group[0];int[] group2 = group[1];for (int i = 0; i < group1.length; i++) {l.addData(datas[group1[i]]);}for (int i = 0; i < group2.length; i++) {ll.addData(datas[group2[i]]);}return new RTDataNode[] { l, ll };}@Overridepublic RTDataNode chooseLeaf(Rectangle rectangle) {insertIndex = usedSpace;// 记录插入路径的索引return this;}/*** 从叶节点中删除此条目rectangle* <p>* 先删除此rectangle，再调用condenseTree()返回删除结点的集合，把其中的叶子结点中的每个条目重新插入；* 非叶子结点就从此结点开始遍历所有结点，然后把所有的叶子结点中的所有条目全部重新插入* * @param rectangle* @return*/protected int delete(Rectangle rectangle) {for (int i = 0; i < usedSpace; i++) {if (datas[i].equals(rectangle)) {deleteData(i);// 用于存储被删除的结点包含的条目的链表QList<RTNode> deleteEntriesList = new ArrayList<RTNode>();condenseTree(deleteEntriesList);// 重新插入删除结点中剩余的条目for (int j = 0; j < deleteEntriesList.size(); j++) {RTNode node = deleteEntriesList.get(j);if (node.isLeaf())// 叶子结点，直接把其上的数据重新插入{for (int k = 0; k < node.usedSpace; k++) {rtree.insert(node.datas[k]);}} else {// 非叶子结点，需要先后序遍历出其上的所有结点List<RTNode> traverseNodes = rtree.traversePostOrder(node);// 把其中的叶子结点中的条目重新插入for (int index = 0; index < traverseNodes.size(); index++) {RTNode traverseNode = traverseNodes.get(index);if (traverseNode.isLeaf()) {for (int t = 0; t < traverseNode.usedSpace; t++) {rtree.insert(traverseNode.datas[t]);}}}}}return deleteIndex;} // end if} // end forreturn -1;}@Overrideprotected RTDataNode findLeaf(Rectangle rectangle) {for (int i = 0; i < usedSpace; i++) {if (datas[i].enclosure(rectangle)) {deleteIndex = i;// 记录搜索路径return this;}}return null;}}

RTDirNode

package rtree;import java.util.ArrayList;
import java.util.List;
import rtree.Constants;/*** @ClassName RTDirNode* @Description 非叶节点*/
public class RTDirNode extends RTNode {/*** 孩子结点集*/protected List<RTNode> children;// 构造函数public RTDirNode(RTree rtree, RTNode parent, int level) {super(rtree, parent, level); // 调用父类的构造函数children = new ArrayList<RTNode>(); // 新建一个RTNode类型的结点数组}/*** @param index* @return 对应索引下的孩子结点*/public RTNode getChild(int index) {return children.get(index);}@Override/*-->选择叶子结点*/public RTDataNode chooseLeaf(Rectangle rectangle) {int index;switch (rtree.getTreeType()) {case Constants.RTREE_LINEAR:case Constants.RTREE_QUADRATIC:case Constants.RTREE_EXPONENTIAL:index = findLeastEnlargement(rectangle); // 获得面积增量最小的结点的索引break;case Constants.RSTAR:if (level == 1)// 即此结点指向叶节点{index = findLeastOverlap(rectangle); // 获得最小重叠面积的结点的索引} else {index = findLeastEnlargement(rectangle); // 获得面积增量最小的结点的索引}break;default:throw new IllegalStateException("Invalid tree type.");}insertIndex = index;// 记录插入路径的索引return getChild(index).chooseLeaf(rectangle); // 非叶子节点的chooseLeaf（）实现递归调用}/*** @param rectangle* @return -->返回最小重叠面积的结点的索引， 如果重叠面积相等则选择加入此Rectangle后面积增量更小的，*         如果面积增量还相等则选择自身面积更小的*/private int findLeastOverlap(Rectangle rectangle) {float overlap = Float.POSITIVE_INFINITY;int sel = -1;for (int i = 0; i < usedSpace; i++) {RTNode node = getChild(i);float ol = 0; // 用于记录每个孩子的datas数据与传入矩形的重叠面积之和for (int j = 0; j < node.datas.length; j++) {// 将传入矩形与各个矩形重叠的面积累加到ol中，得到重叠的总面积ol += rectangle.intersectingArea(node.datas[j]);}if (ol < overlap) {overlap = ol;// 记录重叠面积最小的sel = i;// 记录第几个孩子的索引}// 如果重叠面积相等则选择加入此Rectangle后面积增量更小的,如果面积增量还相等则选择自身面积更小的else if (ol == overlap) {double area1 = datas[i].getUnionRectangle(rectangle).getArea() - datas[i].getArea();double area2 = datas[sel].getUnionRectangle(rectangle).getArea() - datas[sel].getArea();if (area1 == area2) {sel = (datas[sel].getArea() <= datas[i].getArea()) ? sel : i;} else {sel = (area1 < area2) ? i : sel;}}}return sel;}/*** @param rectangle* @return -->面积增量最小的结点的索引，如果面积增量相等则选择自身面积更小的*/private int findLeastEnlargement(Rectangle rectangle) {double area = Double.POSITIVE_INFINITY; // double类型的正无穷int sel = -1;for (int i = 0; i < usedSpace; i++) {// 增量enlargement = 包含（datas[i]里面存储的矩形与查找的矩形）的最小矩形的面积 -// datas[i]里面存储的矩形的面积double enlargement = datas[i].getUnionRectangle(rectangle).getArea() - datas[i].getArea();if (enlargement < area) {area = enlargement; // 记录增量sel = i; // 记录引起增量的【包含（datas[i]里面存储的矩形与查找的矩形）的最小矩形】里面的datas[i]的索引} else if (enlargement == area) {sel = (datas[sel].getArea() < datas[i].getArea()) ? sel : i;}}return sel;}/*** --> 插入新的Rectangle后从插入的叶节点开始向上调整RTree，直到根节点* * @param node1*            引起需要调整的孩子结点* @param node2*            分裂的结点，若未分裂则为null*/public void adjustTree(RTNode node1, RTNode node2) {// 先要找到指向原来旧的结点（即未添加Rectangle之前）的条目的索引datas[insertIndex] = node1.getNodeRectangle();// 先用node1覆盖原来的结点children.set(insertIndex, node1);// 替换旧的结点if (node2 != null) {insert(node2);// 插入新的结点}// 还没到达根节点else if (!isRoot()) {RTDirNode parent = (RTDirNode) getParent();parent.adjustTree(this, null);// 向上调整直到根节点}}/*** -->非叶子节点插入* * @param node* @return 如果结点需要分裂则返回true*/protected boolean insert(RTNode node) {// 已用结点小于树的节点容量，不需分裂，只需插入以及调整树if (usedSpace < rtree.getNodeCapacity()) {datas[usedSpace++] = node.getNodeRectangle();children.add(node);// 新加的node.parent = this;// 新加的RTDirNode parent = (RTDirNode) getParent();if (parent != null) // 不是根节点{parent.adjustTree(this, null);}return false;} else {// 非叶子结点需要分裂RTDirNode[] a = splitIndex(node);RTDirNode n = a[0];RTDirNode nn = a[1];if (isRoot()) {// 新建根节点，层数加1RTDirNode newRoot = new RTDirNode(rtree, Constants.NULL, level + 1);// 把两个分裂的结点n和nn添加到根节点newRoot.addData(n.getNodeRectangle());newRoot.addData(nn.getNodeRectangle());newRoot.children.add(n);newRoot.children.add(nn);// 设置两个分裂的结点n和nn的父节点n.parent = newRoot;nn.parent = newRoot;// 最后设置rtree的根节点rtree.setRoot(newRoot);// 新加的} else {// 如果不是根结点，向上调整树RTDirNode p = (RTDirNode) getParent();p.adjustTree(n, nn);}}return true;}/*** -->非叶子结点的分裂* * @param node* @return*/private RTDirNode[] splitIndex(RTNode node) {int[][] group = null;switch (rtree.getTreeType()) {case Constants.RTREE_LINEAR:break;case Constants.RTREE_QUADRATIC:group = quadraticSplit(node.getNodeRectangle());children.add(node);// 新加的node.parent = this;// 新加的break;case Constants.RTREE_EXPONENTIAL:break;case Constants.RSTAR:break;default:throw new IllegalStateException("Invalid tree type.");}// 新建两个非叶子节点RTDirNode index1 = new RTDirNode(rtree, parent, level);RTDirNode index2 = new RTDirNode(rtree, parent, level);int[] group1 = group[0];int[] group2 = group[1];// 为index1添加数据和孩子for (int i = 0; i < group1.length; i++) {index1.addData(datas[group1[i]]);index1.children.add(this.children.get(group1[i]));// 新加的// 让index1成为其父节点this.children.get(group1[i]).parent = index1;// 新加的}for (int i = 0; i < group2.length; i++) {index2.addData(datas[group2[i]]);index2.children.add(this.children.get(group2[i]));// 新加的this.children.get(group2[i]).parent = index2;// 新加的}return new RTDirNode[] { index1, index2 };}@Override// 寻找叶子protected RTDataNode findLeaf(Rectangle rectangle) {for (int i = 0; i < usedSpace; i++) {if (datas[i].enclosure(rectangle)) {deleteIndex = i;// 记录搜索路径RTDataNode leaf = children.get(i).findLeaf(rectangle); // 递归查找if (leaf != null)return leaf;}}return null;}}

Rtree

package rtree;import java.util.ArrayList;
import java.util.List;import rtree.Constants;/*** @ClassName RTree* @Description*/
public class RTree {private RTNode root; // 根节点private int tree_type; // 树类型private int nodeCapacity = -1; // 结点容量private float fillFactor = -1; // 结点填充因子 ，用于计算每个结点最小条目个数private int dimension; // 维度public RTree(int capacity, float fillFactor, int type, int dimension) {this.fillFactor = fillFactor;tree_type = type;nodeCapacity = capacity;this.dimension = dimension;root = new RTDataNode(this, Constants.NULL); // 根节点的父节点为NULL}/*** @return RTree的维度*/public int getDimension() {return dimension;}/** 设置跟节点 */public void setRoot(RTNode root) {this.root = root;}/*** @return 填充因子*/public float getFillFactor() {return fillFactor;}/*** @return 返回结点容量*/public int getNodeCapacity() {return nodeCapacity;}/*** @return 返回树的类型*/public int getTreeType() {return tree_type;}/*** --> 向Rtree中插入Rectangle 1、先找到合适的叶节点 2、再向此叶节点中插入* * @param rectangle*/public boolean insert(Rectangle rectangle) {if (rectangle == null)throw new IllegalArgumentException("Rectangle cannot be null.");if (rectangle.getHigh().getDimension() != getDimension()) // 矩形维度与树的维度不一致{throw new IllegalArgumentException("Rectangle dimension different than RTree dimension.");}RTDataNode leaf = root.chooseLeaf(rectangle);return leaf.insert(rectangle);}/*** 从R树中删除Rectangle* <p>* 1、寻找包含记录的结点--调用算法findLeaf()来定位包含此记录的叶子结点L，如果没有找到则算法终止。<br>* 2、删除记录--将找到的叶子结点L中的此记录删除<br>* 3、调用算法condenseTree<br>* * @param rectangle* @return*/public int delete(Rectangle rectangle) {if (rectangle == null) {throw new IllegalArgumentException("Rectangle cannot be null.");}if (rectangle.getHigh().getDimension() != getDimension()) {throw new IllegalArgumentException("Rectangle dimension different than RTree dimension.");}RTDataNode leaf = root.findLeaf(rectangle);if (leaf != null) {return leaf.delete(rectangle);}return -1;}/*** 从给定的结点root开始遍历所有的结点* * @param node* @return 所有遍历的结点集合*/public List<RTNode> traversePostOrder(RTNode root) {if (root == null)throw new IllegalArgumentException("Node cannot be null.");List<RTNode> list = new ArrayList<RTNode>();list.add(root);if (!root.isLeaf()) {for (int i = 0; i < root.usedSpace; i++) {List<RTNode> a = traversePostOrder(((RTDirNode) root).getChild(i));for (int j = 0; j < a.size(); j++) {list.add(a.get(j));}}}return list;}public static void main(String[] args) throws Exception {// 结点容量：4、填充因子：0.4、树类型：二维RTree tree = new RTree(4, 0.4f, Constants.RTREE_QUADRATIC, 2);// 每一行的四个数构成两个点（一个矩形）float[] f = { 5, 30, 25, 35, 15, 38, 23, 50, 10, 23, 30, 28, 13, 10, 18, 15, 23, 10, 28, 20, 28, 30, 33, 40, 38,13, 43, 30, 35, 37, 40, 43, 45, 8, 50, 50, 23, 55, 28, 70, 10, 65, 15, 70, 10, 58, 20, 63, };// 插入结点for (int i = 0; i < f.length;) {Point p1 = new Point(new float[] { f[i++], f[i++] });Point p2 = new Point(new float[] { f[i++], f[i++] });final Rectangle rectangle = new Rectangle(p1, p2);tree.insert(rectangle);Rectangle[] rectangles = tree.root.datas;System.out.println("level:" + tree.root.level);for (int j = 0; j < rectangles.length; j++)System.out.println(rectangles[j]);}System.out.println("---------------------------------");System.out.println("Insert finished.");// 删除结点System.out.println("---------------------------------");System.out.println("Begin delete.");for (int i = 0; i < f.length;) {Point p1 = new Point(new float[] { f[i++], f[i++] });Point p2 = new Point(new float[] { f[i++], f[i++] });final Rectangle rectangle = new Rectangle(p1, p2);tree.delete(rectangle);Rectangle[] rectangles = tree.root.datas;System.out.println(tree.root.level);for (int j = 0; j < rectangles.length; j++)System.out.println(rectangles[j]);}System.out.println("---------------------------------");System.out.println("Delete finished.");Rectangle[] rectangles = tree.root.datas;for (int i = 0; i < rectangles.length; i++)System.out.println(rectangles[i]);}}

Constants

package rtree;import rtree.RTNode;public class Constants {public static final int MAX_NUMBER_OF_ENTRIES_IN_NODE = 20;// 结点中的最大条目数public static final int MIN_NUMBER_OF_ENTRIES_IN_NODE = 8;// 结点中的最小条目数public static final int RTDataNode_Dimension = 2;/** Available RTree variants. */ // 树的类型常量public static final int RTREE_LINEAR = 0; // 线性public static final int RTREE_QUADRATIC = 1; // 二维public static final int RTREE_EXPONENTIAL = 2; // 多维public static final int RSTAR = 3; // 星型public static final int NIL = -1;public static final RTNode NULL = null;
} 

参考文章：

1.从 B 树、B+ 树、B*树谈到 R 树 http://blog.csdn.net/v_JULY_v/article/details/6530142/

2.R 树的 Java 实现 http://blog.csdn.net/renyisheng/article/details/40347223

3.R 树 wiki https://en.wikipedia.org/wiki/R-tree

这篇关于空间数据索引 RTree 完全解析及 Java 实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---