空间数据索引RTree完全解析及Java实现
生活随笔
收集整理的這篇文章主要介紹了
空间数据索引RTree完全解析及Java实现
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
版權聲明：本文為博主原創文章，未經博主允許不得轉載。 https://blog.csdn.net/MongChia1993/article/details/69941783 public class Point{ //用一個類來表示一個點 public Float x; public Float y } public class MBR{ public Point BottomLeft; public Point TopRight; }
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]; // 復制數組 } } protected Object clone() { float[] copy = new float[data.length]; System.arraycopy(data, 0, copy, 0, data.length); return new Point(copy); } 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]; } public 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; } } 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 } // 重寫clone()函數 protected Object clone() { Point p1 = (Point) low.clone(); Point p2 = (Point) high.clone(); return new Rectangle(p1, p2); } // 重寫tostring()方法 public String toString() { return "Rectangle Low:" + low + " High:" + high; } /* * ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ ★ 測試 ★ * ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ */ public static void main(String[] args) { // 新建兩point再根據兩個point構建一個Rectangle float[] 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包含rectangle2 else 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; } // 重寫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; } } 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 while int[][] 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); } 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()返回包含結點中所有條目的最小Rectangle rDirNode.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 }; } public 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); // 用于存儲被刪除的結點包含的條目的鏈表Q List<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 for return -1; } protected RTDataNode findLeaf(Rectangle rectangle) { for (int i = 0; i < usedSpace; i++) { if (datas[i].enclosure(rectangle)) { deleteIndex = i;// 記錄搜索路徑 return this; } } return null; } } 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); } /*-->選擇葉子結點*/ 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()) { // 新建根節點，層數加1 RTDirNode 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 }; } // 尋找葉子 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; } } 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]); } } 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; }
- 第一部分 空間數據的背景介紹
- 空間數據的建模
- 基于實體的模型（基于對象）Entity-based models (or object based)
- 常用的空間數據查詢方式
- 空間數據獲取的方法
- R樹
- 簡介
- R樹的數據結構
- 一個更具體的使用場景
- 一棵R樹滿足如下的性質：
- 結點的結構
- R樹的操作
- 搜索
- 插入
- 插入操作存在的情況
-
-
- 如何合理地分裂到兩個組
- 刪除
- 另一個例子再次理解刪除
-
- 空間數據的建模
- 第二部分 R樹的Java實現
- UML
第一部分 空間數據的背景介紹
空間數據的建模
基于實體的模型（基于對象）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
通常，我們只需要兩個點就可限定一個矩形，也就是矩形某個對角線的兩個點就可以決定一個唯一的矩形。通常我們使用（左下，右上兩個點表示）或者使用右上左下，都是可以的。
-

表示一個點的數據：
表示一個MBR的數據
- 如何判斷兩個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樹中。
- 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

Point
Rectangle
RTNode
RTDataNode
RTDirNode
Rtree
Constants
參考文章：
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
轉載于:https://www.cnblogs.com/ExMan/p/9674308.html
總結
以上是生活随笔為你收集整理的空间数据索引RTree完全解析及Java实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： aspnet_UsersInRoles_
- 下一篇： 基本 SQL 之增删改查