2 // Java Spatial Index Library
3 // Copyright (C) 2002-2005 Infomatiq Limited
4 // Copyright (C) 2008-2010 aled@sourceforge.net
6 // This library is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU Lesser General Public
8 // License as published by the Free Software Foundation; either
9 // version 2.1 of the License, or (at your option) any later version.
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // Lesser General Public License for more details.
16 // You should have received a copy of the GNU Lesser General Public
17 // License along with this library; if not, write to the Free Software
18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 package com.infomatiq.jsi.rtree;
22 import gnu.trove.TIntArrayList;
23 import gnu.trove.TIntObjectHashMap;
24 import gnu.trove.TIntProcedure;
25 import gnu.trove.TIntStack;
27 import java.util.Properties;
29 import com.infomatiq.jsi.Point;
30 import com.infomatiq.jsi.Rectangle;
31 import com.infomatiq.jsi.PriorityQueue;
32 import com.infomatiq.jsi.SpatialIndex;
35 * Stub replacement for org.apache.log4j.Logger to prevent dependency on log4j.
37 * @author Tuukka Lehtonen
42 public Logger(String name) {
46 public static Logger getLogger(String name) {
47 return new Logger(name);
50 public void warn(String string) {
51 //System.out.println(name + ": WARN " + string);
54 public boolean isDebugEnabled() {
58 public void debug(String string) {
59 //System.out.println(name + ": DEBUG " + string);
62 public void error(String string) {
63 System.out.println(name + ": ERROR " + string);
68 * <p>This is a lightweight RTree implementation, specifically designed
69 * for the following features (in order of importance):
71 * <li>Fast intersection query performance. To achieve this, the RTree
72 * uses only main memory to store entries. Obviously this will only improve
73 * performance if there is enough physical memory to avoid paging.</li>
74 * <li>Low memory requirements.</li>
75 * <li>Fast add performance.</li>
78 * <p>The main reason for the high speed of this RTree implementation is the
79 * avoidance of the creation of unnecessary objects, mainly achieved by using
80 * primitive collections from the trove4j library.</p>
82 * @author aled@sourceforge.net
85 public class RTree implements SpatialIndex {
86 private static final Logger log = Logger.getLogger(RTree.class.getName());
87 private static final Logger deleteLog = Logger.getLogger(RTree.class.getName() + "-delete");
89 private static final String version = "1.0b8";
91 // parameters of the tree
92 private final static int DEFAULT_MAX_NODE_ENTRIES = 10;
96 // map of nodeId -> node object
97 // TODO eliminate this map - it should not be needed. Nodes
98 // can be found by traversing the tree.
99 private TIntObjectHashMap<Node> nodeMap = new TIntObjectHashMap<Node>();
101 // internal consistency checking - set to true if debugging tree corruption
102 private final static boolean INTERNAL_CONSISTENCY_CHECKING = false;
104 // used to mark the status of entries during a node split
105 private final static int ENTRY_STATUS_ASSIGNED = 0;
106 private final static int ENTRY_STATUS_UNASSIGNED = 1;
107 private byte[] entryStatus = null;
108 private byte[] initialEntryStatus = null;
110 // stacks used to store nodeId and entry index of each node
111 // from the root down to the leaf. Enables fast lookup
112 // of nodes when a split is propagated up the tree.
113 private TIntStack parents = new TIntStack();
114 private TIntStack parentsEntry = new TIntStack();
117 private int treeHeight = 1; // leaves are always level 1
118 private int rootNodeId = 0;
119 private int size = 0;
121 // Enables creation of new nodes
122 private int highestUsedNodeId = rootNodeId;
124 // Deleted node objects are retained in the nodeMap,
125 // so that they can be reused. Store the IDs of nodes
126 // which can be reused.
127 private TIntStack deletedNodeIds = new TIntStack();
129 // List of nearest rectangles. Use a member variable to
130 // avoid recreating the object each time nearest() is called.
131 private TIntArrayList nearestIds = new TIntArrayList();
132 private TIntArrayList savedValues = new TIntArrayList();
133 private float savedPriority = 0;
135 // List of nearestN rectangles
136 private SortedList nearestNIds = new SortedList();
138 // List of nearestN rectanges, used in the alternative nearestN implementation.
139 private PriorityQueue distanceQueue =
140 new PriorityQueue(PriorityQueue.SORT_ORDER_ASCENDING);
143 * Constructor. Use init() method to initialize parameters of the RTree.
149 //-------------------------------------------------------------------------
150 // public implementation of SpatialIndex interface:
152 // add(Rectangle, int)
153 // delete(Rectangle, int)
154 // nearest(Point, TIntProcedure, float)
155 // intersects(Rectangle, TIntProcedure)
156 // contains(Rectangle, TIntProcedure)
158 //-------------------------------------------------------------------------
160 * <p>Initialize implementation dependent properties of the RTree.
161 * Currently implemented properties are:
163 * <li>MaxNodeEntries</li> This specifies the maximum number of entries
164 * in a node. The default value is 10, which is used if the property is
165 * not specified, or is less than 2.
166 * <li>MinNodeEntries</li> This specifies the minimum number of entries
167 * in a node. The default value is half of the MaxNodeEntries value (rounded
168 * down), which is used if the property is not specified or is less than 1.
171 * @see com.infomatiq.jsi.SpatialIndex#init(Properties)
173 public void init(Properties props) {
175 // use sensible defaults if null is passed in.
179 maxNodeEntries = Integer.parseInt(props.getProperty("MaxNodeEntries", "0"));
180 minNodeEntries = Integer.parseInt(props.getProperty("MinNodeEntries", "0"));
182 // Obviously a node with less than 2 entries cannot be split.
183 // The node splitting algorithm will work with only 2 entries
184 // per node, but will be inefficient.
185 if (maxNodeEntries < 2) {
186 log.warn("Invalid MaxNodeEntries = " + maxNodeEntries + " Resetting to default value of " + DEFAULT_MAX_NODE_ENTRIES);
187 maxNodeEntries = DEFAULT_MAX_NODE_ENTRIES;
190 // The MinNodeEntries must be less than or equal to (int) (MaxNodeEntries / 2)
191 if (minNodeEntries < 1 || minNodeEntries > maxNodeEntries / 2) {
192 log.warn("MinNodeEntries must be between 1 and MaxNodeEntries / 2");
193 minNodeEntries = maxNodeEntries / 2;
197 entryStatus = new byte[maxNodeEntries];
198 initialEntryStatus = new byte[maxNodeEntries];
200 for (int i = 0; i < maxNodeEntries; i++) {
201 initialEntryStatus[i] = ENTRY_STATUS_UNASSIGNED;
204 Node root = new Node(rootNodeId, 1, maxNodeEntries);
205 nodeMap.put(rootNodeId, root);
207 log.debug("init() " + " MaxNodeEntries = " + maxNodeEntries + ", MinNodeEntries = " + minNodeEntries);
211 * @see com.infomatiq.jsi.SpatialIndex#add(Rectangle, int)
213 public void add(Rectangle r, int id) {
214 if (log.isDebugEnabled()) {
215 log.debug("Adding rectangle " + r + ", id " + id);
218 add(r.minX, r.minY, r.maxX, r.maxY, id, 1);
222 if (INTERNAL_CONSISTENCY_CHECKING) {
228 * Adds a new entry at a specified level in the tree
230 private void add(float minX, float minY, float maxX, float maxY, int id, int level) {
231 // I1 [Find position for new record] Invoke ChooseLeaf to select a
232 // leaf node L in which to place r
233 Node n = chooseNode(minX, minY, maxX, maxY, level);
236 // I2 [Add record to leaf node] If L has room for another entry,
237 // install E. Otherwise invoke SplitNode to obtain L and LL containing
238 // E and all the old entries of L
239 if (n.entryCount < maxNodeEntries) {
240 n.addEntry(minX, minY, maxX, maxY, id);
242 newLeaf = splitNode(n, minX, minY, maxX, maxY, id);
245 // I3 [Propagate changes upwards] Invoke AdjustTree on L, also passing LL
246 // if a split was performed
247 Node newNode = adjustTree(n, newLeaf);
249 // I4 [Grow tree taller] If node split propagation caused the root to
250 // split, create a new root whose children are the two resulting nodes.
251 if (newNode != null) {
252 int oldRootNodeId = rootNodeId;
253 Node oldRoot = getNode(oldRootNodeId);
255 rootNodeId = getNextNodeId();
257 Node root = new Node(rootNodeId, treeHeight, maxNodeEntries);
258 root.addEntry(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY, newNode.nodeId);
259 root.addEntry(oldRoot.mbrMinX, oldRoot.mbrMinY, oldRoot.mbrMaxX, oldRoot.mbrMaxY, oldRoot.nodeId);
260 nodeMap.put(rootNodeId, root);
265 * @see com.infomatiq.jsi.SpatialIndex#delete(Rectangle, int)
267 public boolean delete(Rectangle r, int id) {
268 // FindLeaf algorithm inlined here. Note the "official" algorithm
269 // searches all overlapping entries. This seems inefficient to me,
270 // as an entry is only worth searching if it contains (NOT overlaps)
271 // the rectangle we are searching for.
273 // Also the algorithm has been changed so that it is not recursive.
275 // FL1 [Search subtrees] If root is not a leaf, check each entry
276 // to determine if it contains r. For each entry found, invoke
277 // findLeaf on the node pointed to by the entry, until r is found or
278 // all entries have been checked.
280 parents.push(rootNodeId);
282 parentsEntry.reset();
283 parentsEntry.push(-1);
285 int foundIndex = -1; // index of entry to be deleted in leaf
287 while (foundIndex == -1 && parents.size() > 0) {
288 n = getNode(parents.peek());
289 int startIndex = parentsEntry.peek() + 1;
292 deleteLog.debug("searching node " + n.nodeId + ", from index " + startIndex);
293 boolean contains = false;
294 for (int i = startIndex; i < n.entryCount; i++) {
295 if (Rectangle.contains(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i],
296 r.minX, r.minY, r.maxX, r.maxY)) {
297 parents.push(n.ids[i]);
299 parentsEntry.push(i); // this becomes the start index when the child has been searched
300 parentsEntry.push(-1);
302 break; // ie go to next iteration of while()
309 foundIndex = n.findEntry(r.minX, r.minY, r.maxX, r.maxY, id);
316 if (foundIndex != -1) {
317 n.deleteEntry(foundIndex);
322 // shrink the tree if possible (i.e. if root node has exactly one entry,and that
323 // entry is not a leaf node, delete the root (it's entry becomes the new root)
324 Node root = getNode(rootNodeId);
325 while (root.entryCount == 1 && treeHeight > 1)
327 deletedNodeIds.push(rootNodeId);
329 rootNodeId = root.ids[0];
331 root = getNode(rootNodeId);
334 // if the tree is now empty, then set the MBR of the root node back to it's original state
335 // (this is only needed when the tree is empty, as this is the only state where an empty node
336 // is not eliminated)
338 root.mbrMinX = Float.MAX_VALUE;
339 root.mbrMinY = Float.MAX_VALUE;
340 root.mbrMaxX = -Float.MAX_VALUE;
341 root.mbrMaxY = -Float.MAX_VALUE;
344 if (INTERNAL_CONSISTENCY_CHECKING) {
348 return (foundIndex != -1);
352 * @see com.infomatiq.jsi.SpatialIndex#nearest(Point, TIntProcedure, float)
354 public void nearest(Point p, TIntProcedure v, float furthestDistance) {
355 Node rootNode = getNode(rootNodeId);
357 float furthestDistanceSq = furthestDistance * furthestDistance;
358 nearest(p, rootNode, furthestDistanceSq);
360 nearestIds.forEach(v);
364 private void createNearestNDistanceQueue(Point p, int count, float furthestDistance) {
365 distanceQueue.reset();
366 distanceQueue.setSortOrder(PriorityQueue.SORT_ORDER_DESCENDING);
368 // return immediately if given an invalid "count" parameter
374 parents.push(rootNodeId);
376 parentsEntry.reset();
377 parentsEntry.push(-1);
379 // TODO: possible shortcut here - could test for intersection with the
380 // MBR of the root node. If no intersection, return immediately.
382 float furthestDistanceSq = furthestDistance * furthestDistance;
384 while (parents.size() > 0) {
385 Node n = getNode(parents.peek());
386 int startIndex = parentsEntry.peek() + 1;
389 // go through every entry in the index node to check
390 // if it could contain an entry closer than the farthest entry
392 boolean near = false;
393 for (int i = startIndex; i < n.entryCount; i++) {
394 if (Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i],
395 n.entriesMaxX[i], n.entriesMaxY[i],
396 p.x, p.y) <= furthestDistanceSq) {
397 parents.push(n.ids[i]);
399 parentsEntry.push(i); // this becomes the start index when the child has been searched
400 parentsEntry.push(-1);
402 break; // ie go to next iteration of while()
409 // go through every entry in the leaf to check if
410 // it is currently one of the nearest N entries.
411 for (int i = 0; i < n.entryCount; i++) {
412 float entryDistanceSq = Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i],
413 n.entriesMaxX[i], n.entriesMaxY[i],
415 int entryId = n.ids[i];
417 if (entryDistanceSq <= furthestDistanceSq) {
418 distanceQueue.insert(entryId, entryDistanceSq);
420 while (distanceQueue.size() > count) {
421 // normal case - we can simply remove the lowest priority (highest distance) entry
422 int value = distanceQueue.getValue();
423 float distanceSq = distanceQueue.getPriority();
426 // rare case - multiple items of the same priority (distance)
427 if (distanceSq == distanceQueue.getPriority()) {
428 savedValues.add(value);
429 savedPriority = distanceSq;
435 // if the saved values have the same distance as the
436 // next one in the tree, add them back in.
437 if (savedValues.size() > 0 && savedPriority == distanceQueue.getPriority()) {
438 for (int svi = 0; svi < savedValues.size(); svi++) {
439 distanceQueue.insert(savedValues.get(svi), savedPriority);
444 // narrow the search, if we have already found N items
445 if (distanceQueue.getPriority() < furthestDistanceSq && distanceQueue.size() >= count) {
446 furthestDistanceSq = distanceQueue.getPriority();
457 * @see com.infomatiq.jsi.SpatialIndex#nearestNUnsorted(Point, TIntProcedure, int, float)
459 public void nearestNUnsorted(Point p, TIntProcedure v, int count, float furthestDistance) {
460 // This implementation is designed to give good performance
462 // o N is high (100+)
463 // o The results do not need to be sorted by distance.
465 // Uses a priority queue as the underlying data structure.
467 // The behaviour of this algorithm has been carefully designed to
468 // return exactly the same items as the the original version (nearestN_orig), in particular,
469 // more than N items will be returned if items N and N+x have the
471 createNearestNDistanceQueue(p, count, furthestDistance);
473 while (distanceQueue.size() > 0) {
474 v.execute(distanceQueue.getValue());
480 * @see com.infomatiq.jsi.SpatialIndex#nearestN(Point, TIntProcedure, int, float)
482 public void nearestN(Point p, TIntProcedure v, int count, float furthestDistance) {
483 createNearestNDistanceQueue(p, count, furthestDistance);
485 distanceQueue.setSortOrder(PriorityQueue.SORT_ORDER_ASCENDING);
487 while (distanceQueue.size() > 0) {
488 v.execute(distanceQueue.getValue());
494 * @see com.infomatiq.jsi.SpatialIndex#nearestN(Point, TIntProcedure, int, float)
495 * @deprecated Use new NearestN or NearestNUnsorted instead.
497 * This implementation of nearestN is only suitable for small values of N (ie less than 10).
499 public void nearestN_orig(Point p, TIntProcedure v, int count, float furthestDistance) {
500 // return immediately if given an invalid "count" parameter
506 parents.push(rootNodeId);
508 parentsEntry.reset();
509 parentsEntry.push(-1);
511 nearestNIds.init(count);
513 // TODO: possible shortcut here - could test for intersection with the
514 // MBR of the root node. If no intersection, return immediately.
516 float furthestDistanceSq = furthestDistance * furthestDistance;
518 while (parents.size() > 0) {
519 Node n = getNode(parents.peek());
520 int startIndex = parentsEntry.peek() + 1;
523 // go through every entry in the index node to check
524 // if it could contain an entry closer than the farthest entry
526 boolean near = false;
527 for (int i = startIndex; i < n.entryCount; i++) {
528 if (Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i],
529 n.entriesMaxX[i], n.entriesMaxY[i],
530 p.x, p.y) <= furthestDistanceSq) {
531 parents.push(n.ids[i]);
533 parentsEntry.push(i); // this becomes the start index when the child has been searched
534 parentsEntry.push(-1);
536 break; // ie go to next iteration of while()
543 // go through every entry in the leaf to check if
544 // it is currently one of the nearest N entries.
545 for (int i = 0; i < n.entryCount; i++) {
546 float entryDistanceSq = Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i],
547 n.entriesMaxX[i], n.entriesMaxY[i],
549 int entryId = n.ids[i];
551 if (entryDistanceSq <= furthestDistanceSq) {
552 // add the new entry to the tree. Note that the higher the distance, the lower the priority
553 nearestNIds.add(entryId, -entryDistanceSq);
555 float tempFurthestDistanceSq = -nearestNIds.getLowestPriority();
556 if (tempFurthestDistanceSq < furthestDistanceSq) {
557 furthestDistanceSq = tempFurthestDistanceSq;
566 nearestNIds.forEachId(v);
570 * @see com.infomatiq.jsi.SpatialIndex#intersects(Rectangle, TIntProcedure)
572 public void intersects(Rectangle r, TIntProcedure v) {
573 Node rootNode = getNode(rootNodeId);
574 intersects(r, v, rootNode);
578 * @see com.infomatiq.jsi.SpatialIndex#contains(Rectangle, TIntProcedure)
580 public void contains(Rectangle r, TIntProcedure v) {
581 // find all rectangles in the tree that are contained by the passed rectangle
582 // written to be non-recursive (should model other searches on this?)
585 parents.push(rootNodeId);
587 parentsEntry.reset();
588 parentsEntry.push(-1);
590 // TODO: possible shortcut here - could test for intersection with the
591 // MBR of the root node. If no intersection, return immediately.
593 while (parents.size() > 0) {
594 Node n = getNode(parents.peek());
595 int startIndex = parentsEntry.peek() + 1;
598 // go through every entry in the index node to check
599 // if it intersects the passed rectangle. If so, it
600 // could contain entries that are contained.
601 boolean intersects = false;
602 for (int i = startIndex; i < n.entryCount; i++) {
603 if (Rectangle.intersects(r.minX, r.minY, r.maxX, r.maxY,
604 n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i])) {
605 parents.push(n.ids[i]);
607 parentsEntry.push(i); // this becomes the start index when the child has been searched
608 parentsEntry.push(-1);
610 break; // ie go to next iteration of while()
617 // go through every entry in the leaf to check if
618 // it is contained by the passed rectangle
619 for (int i = 0; i < n.entryCount; i++) {
620 if (Rectangle.contains(r.minX, r.minY, r.maxX, r.maxY,
621 n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i])) {
622 if (!v.execute(n.ids[i])) {
634 * @see com.infomatiq.jsi.SpatialIndex#size()
641 * @see com.infomatiq.jsi.SpatialIndex#getBounds()
643 public Rectangle getBounds() {
644 Rectangle bounds = null;
646 Node n = getNode(getRootNodeId());
647 if (n != null && n.entryCount > 0) {
648 bounds = new Rectangle();
649 bounds.minX = n.mbrMinX;
650 bounds.minY = n.mbrMinY;
651 bounds.maxX = n.mbrMaxX;
652 bounds.maxY = n.mbrMaxY;
658 * @see com.infomatiq.jsi.SpatialIndex#getVersion()
660 public String getVersion() {
661 return "RTree-" + version;
663 //-------------------------------------------------------------------------
664 // end of SpatialIndex methods
665 //-------------------------------------------------------------------------
668 * Get the next available node ID. Reuse deleted node IDs if
671 private int getNextNodeId() {
673 if (deletedNodeIds.size() > 0) {
674 nextNodeId = deletedNodeIds.pop();
676 nextNodeId = 1 + highestUsedNodeId++;
682 * Get a node object, given the ID of the node.
684 public Node getNode(int id) {
685 return nodeMap.get(id);
689 * Get the highest used node ID
691 public int getHighestUsedNodeId() {
692 return highestUsedNodeId;
696 * Get the root node ID
698 public int getRootNodeId() {
703 * Split a node. Algorithm is taken pretty much verbatim from
704 * Guttman's original paper.
706 * @return new node object.
708 private Node splitNode(Node n, float newRectMinX, float newRectMinY, float newRectMaxX, float newRectMaxY, int newId) {
709 // [Pick first entry for each group] Apply algorithm pickSeeds to
710 // choose two entries to be the first elements of the groups. Assign
714 float initialArea = 0;
715 if (log.isDebugEnabled()) {
716 float unionMinX = Math.min(n.mbrMinX, newRectMinX);
717 float unionMinY = Math.min(n.mbrMinY, newRectMinY);
718 float unionMaxX = Math.max(n.mbrMaxX, newRectMaxX);
719 float unionMaxY = Math.max(n.mbrMaxY, newRectMaxY);
721 initialArea = (unionMaxX - unionMinX) * (unionMaxY - unionMinY);
724 System.arraycopy(initialEntryStatus, 0, entryStatus, 0, maxNodeEntries);
727 newNode = new Node(getNextNodeId(), n.level, maxNodeEntries);
728 nodeMap.put(newNode.nodeId, newNode);
730 pickSeeds(n, newRectMinX, newRectMinY, newRectMaxX, newRectMaxY, newId, newNode); // this also sets the entryCount to 1
732 // [Check if done] If all entries have been assigned, stop. If one
733 // group has so few entries that all the rest must be assigned to it in
734 // order for it to have the minimum number m, assign them and stop.
735 while (n.entryCount + newNode.entryCount < maxNodeEntries + 1) {
736 if (maxNodeEntries + 1 - newNode.entryCount == minNodeEntries) {
737 // assign all remaining entries to original node
738 for (int i = 0; i < maxNodeEntries; i++) {
739 if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED) {
740 entryStatus[i] = ENTRY_STATUS_ASSIGNED;
742 if (n.entriesMinX[i] < n.mbrMinX) n.mbrMinX = n.entriesMinX[i];
743 if (n.entriesMinY[i] < n.mbrMinY) n.mbrMinY = n.entriesMinY[i];
744 if (n.entriesMaxX[i] > n.mbrMaxX) n.mbrMaxX = n.entriesMaxX[i];
745 if (n.entriesMaxY[i] > n.mbrMaxY) n.mbrMaxY = n.entriesMaxY[i];
752 if (maxNodeEntries + 1 - n.entryCount == minNodeEntries) {
753 // assign all remaining entries to new node
754 for (int i = 0; i < maxNodeEntries; i++) {
755 if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED) {
756 entryStatus[i] = ENTRY_STATUS_ASSIGNED;
757 newNode.addEntry(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i], n.ids[i]);
758 n.ids[i] = -1; // an id of -1 indicates the entry is not in use
764 // [Select entry to assign] Invoke algorithm pickNext to choose the
765 // next entry to assign. Add it to the group whose covering rectangle
766 // will have to be enlarged least to accommodate it. Resolve ties
767 // by adding the entry to the group with smaller area, then to the
768 // the one with fewer entries, then to either. Repeat from S2
769 pickNext(n, newNode);
774 // check that the MBR stored for each node is correct.
775 if (INTERNAL_CONSISTENCY_CHECKING) {
776 Rectangle nMBR = new Rectangle(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY);
777 if (!nMBR.equals(calculateMBR(n))) {
778 log.error("Error: splitNode old node MBR wrong");
780 Rectangle newNodeMBR = new Rectangle(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY);
781 if (!newNodeMBR.equals(calculateMBR(newNode))) {
782 log.error("Error: splitNode new node MBR wrong");
787 if (log.isDebugEnabled()) {
788 float newArea = Rectangle.area(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY) +
789 Rectangle.area(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY);
790 float percentageIncrease = (100 * (newArea - initialArea)) / initialArea;
791 log.debug("Node " + n.nodeId + " split. New area increased by " + percentageIncrease + "%");
798 * Pick the seeds used to split a node.
799 * Select two entries to be the first elements of the groups
801 private void pickSeeds(Node n, float newRectMinX, float newRectMinY, float newRectMaxX, float newRectMaxY, int newId, Node newNode) {
802 // Find extreme rectangles along all dimension. Along each dimension,
803 // find the entry whose rectangle has the highest low side, and the one
804 // with the lowest high side. Record the separation.
805 float maxNormalizedSeparation = -1; // initialize to -1 so that even overlapping rectangles will be considered for the seeds
806 int highestLowIndex = -1;
807 int lowestHighIndex = -1;
809 // for the purposes of picking seeds, take the MBR of the node to include
810 // the new rectangle aswell.
811 if (newRectMinX < n.mbrMinX) n.mbrMinX = newRectMinX;
812 if (newRectMinY < n.mbrMinY) n.mbrMinY = newRectMinY;
813 if (newRectMaxX > n.mbrMaxX) n.mbrMaxX = newRectMaxX;
814 if (newRectMaxY > n.mbrMaxY) n.mbrMaxY = newRectMaxY;
816 float mbrLenX = n.mbrMaxX - n.mbrMinX;
817 float mbrLenY = n.mbrMaxY - n.mbrMinY;
819 if (log.isDebugEnabled()) {
820 log.debug("pickSeeds(): NodeId = " + n.nodeId);
823 float tempHighestLow = newRectMinX;
824 int tempHighestLowIndex = -1; // -1 indicates the new rectangle is the seed
826 float tempLowestHigh = newRectMaxX;
827 int tempLowestHighIndex = -1; // -1 indicates the new rectangle is the seed
829 for (int i = 0; i < n.entryCount; i++) {
830 float tempLow = n.entriesMinX[i];
831 if (tempLow >= tempHighestLow) {
832 tempHighestLow = tempLow;
833 tempHighestLowIndex = i;
834 } else { // ensure that the same index cannot be both lowestHigh and highestLow
835 float tempHigh = n.entriesMaxX[i];
836 if (tempHigh <= tempLowestHigh) {
837 tempLowestHigh = tempHigh;
838 tempLowestHighIndex = i;
842 // PS2 [Adjust for shape of the rectangle cluster] Normalize the separations
843 // by dividing by the widths of the entire set along the corresponding
845 float normalizedSeparation = mbrLenX == 0 ? 1 : (tempHighestLow - tempLowestHigh) / mbrLenX;
846 if (normalizedSeparation > 1 || normalizedSeparation < -1) {
847 log.error("Invalid normalized separation X");
850 if (log.isDebugEnabled()) {
851 log.debug("Entry " + i + ", dimension X: HighestLow = " + tempHighestLow +
852 " (index " + tempHighestLowIndex + ")" + ", LowestHigh = " +
853 tempLowestHigh + " (index " + tempLowestHighIndex + ", NormalizedSeparation = " + normalizedSeparation);
856 // PS3 [Select the most extreme pair] Choose the pair with the greatest
857 // normalized separation along any dimension.
858 // Note that if negative it means the rectangles overlapped. However still include
859 // overlapping rectangles if that is the only choice available.
860 if (normalizedSeparation >= maxNormalizedSeparation) {
861 highestLowIndex = tempHighestLowIndex;
862 lowestHighIndex = tempLowestHighIndex;
863 maxNormalizedSeparation = normalizedSeparation;
867 // Repeat for the Y dimension
868 tempHighestLow = newRectMinY;
869 tempHighestLowIndex = -1; // -1 indicates the new rectangle is the seed
871 tempLowestHigh = newRectMaxY;
872 tempLowestHighIndex = -1; // -1 indicates the new rectangle is the seed
874 for (int i = 0; i < n.entryCount; i++) {
875 float tempLow = n.entriesMinY[i];
876 if (tempLow >= tempHighestLow) {
877 tempHighestLow = tempLow;
878 tempHighestLowIndex = i;
879 } else { // ensure that the same index cannot be both lowestHigh and highestLow
880 float tempHigh = n.entriesMaxY[i];
881 if (tempHigh <= tempLowestHigh) {
882 tempLowestHigh = tempHigh;
883 tempLowestHighIndex = i;
887 // PS2 [Adjust for shape of the rectangle cluster] Normalize the separations
888 // by dividing by the widths of the entire set along the corresponding
890 float normalizedSeparation = mbrLenY == 0 ? 1 : (tempHighestLow - tempLowestHigh) / mbrLenY;
891 if (normalizedSeparation > 1 || normalizedSeparation < -1) {
892 log.error("Invalid normalized separation Y");
895 if (log.isDebugEnabled()) {
896 log.debug("Entry " + i + ", dimension Y: HighestLow = " + tempHighestLow +
897 " (index " + tempHighestLowIndex + ")" + ", LowestHigh = " +
898 tempLowestHigh + " (index " + tempLowestHighIndex + ", NormalizedSeparation = " + normalizedSeparation);
901 // PS3 [Select the most extreme pair] Choose the pair with the greatest
902 // normalized separation along any dimension.
903 // Note that if negative it means the rectangles overlapped. However still include
904 // overlapping rectangles if that is the only choice available.
905 if (normalizedSeparation >= maxNormalizedSeparation) {
906 highestLowIndex = tempHighestLowIndex;
907 lowestHighIndex = tempLowestHighIndex;
908 maxNormalizedSeparation = normalizedSeparation;
912 // At this point it is possible that the new rectangle is both highestLow and lowestHigh.
913 // This can happen if all rectangles in the node overlap the new rectangle.
914 // Resolve this by declaring that the highestLowIndex is the lowest Y and,
915 // the lowestHighIndex is the largest X (but always a different rectangle)
916 if (highestLowIndex == lowestHighIndex) {
917 highestLowIndex = -1;
918 float tempMinY = newRectMinY;
920 float tempMaxX = n.entriesMaxX[0];
922 for (int i = 1; i < n.entryCount; i++) {
923 if (n.entriesMinY[i] < tempMinY) {
924 tempMinY = n.entriesMinY[i];
927 else if (n.entriesMaxX[i] > tempMaxX) {
928 tempMaxX = n.entriesMaxX[i];
934 // highestLowIndex is the seed for the new node.
935 if (highestLowIndex == -1) {
936 newNode.addEntry(newRectMinX, newRectMinY, newRectMaxX, newRectMaxY, newId);
938 newNode.addEntry(n.entriesMinX[highestLowIndex], n.entriesMinY[highestLowIndex],
939 n.entriesMaxX[highestLowIndex], n.entriesMaxY[highestLowIndex],
940 n.ids[highestLowIndex]);
941 n.ids[highestLowIndex] = -1;
943 // move the new rectangle into the space vacated by the seed for the new node
944 n.entriesMinX[highestLowIndex] = newRectMinX;
945 n.entriesMinY[highestLowIndex] = newRectMinY;
946 n.entriesMaxX[highestLowIndex] = newRectMaxX;
947 n.entriesMaxY[highestLowIndex] = newRectMaxY;
949 n.ids[highestLowIndex] = newId;
952 // lowestHighIndex is the seed for the original node.
953 if (lowestHighIndex == -1) {
954 lowestHighIndex = highestLowIndex;
957 entryStatus[lowestHighIndex] = ENTRY_STATUS_ASSIGNED;
959 n.mbrMinX = n.entriesMinX[lowestHighIndex];
960 n.mbrMinY = n.entriesMinY[lowestHighIndex];
961 n.mbrMaxX = n.entriesMaxX[lowestHighIndex];
962 n.mbrMaxY = n.entriesMaxY[lowestHighIndex];
966 * Pick the next entry to be assigned to a group during a node split.
968 * [Determine cost of putting each entry in each group] For each
969 * entry not yet in a group, calculate the area increase required
970 * in the covering rectangles of each group
972 private int pickNext(Node n, Node newNode) {
973 float maxDifference = Float.NEGATIVE_INFINITY;
977 maxDifference = Float.NEGATIVE_INFINITY;
979 if (log.isDebugEnabled()) {
980 log.debug("pickNext()");
983 for (int i = 0; i < maxNodeEntries; i++) {
984 if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED) {
986 if (n.ids[i] == -1) {
987 log.error("Error: Node " + n.nodeId + ", entry " + i + " is null");
990 float nIncrease = Rectangle.enlargement(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY,
991 n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i]);
992 float newNodeIncrease = Rectangle.enlargement(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY,
993 n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i]);
995 float difference = Math.abs(nIncrease - newNodeIncrease);
997 if (difference > maxDifference) {
1000 if (nIncrease < newNodeIncrease) {
1002 } else if (newNodeIncrease < nIncrease) {
1004 } else if (Rectangle.area(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY) < Rectangle.area(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY)) {
1006 } else if (Rectangle.area(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY) < Rectangle.area(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY)) {
1008 } else if (newNode.entryCount < maxNodeEntries / 2) {
1013 maxDifference = difference;
1015 if (log.isDebugEnabled()) {
1016 log.debug("Entry " + i + " group0 increase = " + nIncrease + ", group1 increase = " + newNodeIncrease +
1017 ", diff = " + difference + ", MaxDiff = " + maxDifference + " (entry " + next + ")");
1022 entryStatus[next] = ENTRY_STATUS_ASSIGNED;
1024 if (nextGroup == 0) {
1025 if (n.entriesMinX[next] < n.mbrMinX) n.mbrMinX = n.entriesMinX[next];
1026 if (n.entriesMinY[next] < n.mbrMinY) n.mbrMinY = n.entriesMinY[next];
1027 if (n.entriesMaxX[next] > n.mbrMaxX) n.mbrMaxX = n.entriesMaxX[next];
1028 if (n.entriesMaxY[next] > n.mbrMaxY) n.mbrMaxY = n.entriesMaxY[next];
1031 // move to new node.
1032 newNode.addEntry(n.entriesMinX[next], n.entriesMinY[next], n.entriesMaxX[next], n.entriesMaxY[next], n.ids[next]);
1040 * Recursively searches the tree for the nearest entry. Other queries
1041 * call execute() on an IntProcedure when a matching entry is found;
1042 * however nearest() must store the entry Ids as it searches the tree,
1043 * in case a nearer entry is found.
1044 * Uses the member variable nearestIds to store the nearest
1047 * TODO rewrite this to be non-recursive?
1049 private float nearest(Point p, Node n, float furthestDistanceSq) {
1050 for (int i = 0; i < n.entryCount; i++) {
1051 float tempDistanceSq = Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i], p.x, p.y);
1052 if (n.isLeaf()) { // for leaves, the distance is an actual nearest distance
1053 if (tempDistanceSq < furthestDistanceSq) {
1054 furthestDistanceSq = tempDistanceSq;
1057 if (tempDistanceSq <= furthestDistanceSq) {
1058 nearestIds.add(n.ids[i]);
1060 } else { // for index nodes, only go into them if they potentially could have
1061 // a rectangle nearer than actualNearest
1062 if (tempDistanceSq <= furthestDistanceSq) {
1063 // search the child node
1064 furthestDistanceSq = nearest(p, getNode(n.ids[i]), furthestDistanceSq);
1068 return furthestDistanceSq;
1072 * Recursively searches the tree for all intersecting entries.
1073 * Immediately calls execute() on the passed IntProcedure when
1074 * a matching entry is found.
1076 * TODO rewrite this to be non-recursive? Make sure it
1077 * doesn't slow it down.
1079 private boolean intersects(Rectangle r, TIntProcedure v, Node n) {
1080 for (int i = 0; i < n.entryCount; i++) {
1081 if (Rectangle.intersects(r.minX, r.minY, r.maxX, r.maxY, n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i])) {
1083 if (!v.execute(n.ids[i])) {
1087 Node childNode = getNode(n.ids[i]);
1088 if (!intersects(r, v, childNode)) {
1098 * Used by delete(). Ensures that all nodes from the passed node
1099 * up to the root have the minimum number of entries.
1101 * Note that the parent and parentEntry stacks are expected to
1102 * contain the nodeIds of all parents up to the root.
1104 private void condenseTree(Node l) {
1105 // CT1 [Initialize] Set n=l. Set the list of eliminated
1106 // nodes to be empty.
1109 int parentEntry = 0;
1111 TIntStack eliminatedNodeIds = new TIntStack();
1113 // CT2 [Find parent entry] If N is the root, go to CT6. Otherwise
1114 // let P be the parent of N, and let En be N's entry in P
1115 while (n.level != treeHeight) {
1116 parent = getNode(parents.pop());
1117 parentEntry = parentsEntry.pop();
1119 // CT3 [Eliminiate under-full node] If N has too few entries,
1120 // delete En from P and add N to the list of eliminated nodes
1121 if (n.entryCount < minNodeEntries) {
1122 parent.deleteEntry(parentEntry);
1123 eliminatedNodeIds.push(n.nodeId);
1125 // CT4 [Adjust covering rectangle] If N has not been eliminated,
1126 // adjust EnI to tightly contain all entries in N
1127 if (n.mbrMinX != parent.entriesMinX[parentEntry] ||
1128 n.mbrMinY != parent.entriesMinY[parentEntry] ||
1129 n.mbrMaxX != parent.entriesMaxX[parentEntry] ||
1130 n.mbrMaxY != parent.entriesMaxY[parentEntry]) {
1131 float deletedMinX = parent.entriesMinX[parentEntry];
1132 float deletedMinY = parent.entriesMinY[parentEntry];
1133 float deletedMaxX = parent.entriesMaxX[parentEntry];
1134 float deletedMaxY = parent.entriesMaxY[parentEntry];
1135 parent.entriesMinX[parentEntry] = n.mbrMinX;
1136 parent.entriesMinY[parentEntry] = n.mbrMinY;
1137 parent.entriesMaxX[parentEntry] = n.mbrMaxX;
1138 parent.entriesMaxY[parentEntry] = n.mbrMaxY;
1139 parent.recalculateMBRIfInfluencedBy(deletedMinX, deletedMinY, deletedMaxX, deletedMaxY);
1142 // CT5 [Move up one level in tree] Set N=P and repeat from CT2
1146 // CT6 [Reinsert orphaned entries] Reinsert all entries of nodes in set Q.
1147 // Entries from eliminated leaf nodes are reinserted in tree leaves as in
1148 // Insert(), but entries from higher level nodes must be placed higher in
1149 // the tree, so that leaves of their dependent subtrees will be on the same
1150 // level as leaves of the main tree
1151 while (eliminatedNodeIds.size() > 0) {
1152 Node e = getNode(eliminatedNodeIds.pop());
1153 for (int j = 0; j < e.entryCount; j++) {
1154 add(e.entriesMinX[j], e.entriesMinY[j], e.entriesMaxX[j], e.entriesMaxY[j], e.ids[j], e.level);
1158 deletedNodeIds.push(e.nodeId);
1163 * Used by add(). Chooses a leaf to add the rectangle to.
1165 private Node chooseNode(float minX, float minY, float maxX, float maxY, int level) {
1166 // CL1 [Initialize] Set N to be the root node
1167 Node n = getNode(rootNodeId);
1169 parentsEntry.reset();
1171 // CL2 [Leaf check] If N is a leaf, return N
1174 log.error("Could not get root node (" + rootNodeId + ")");
1177 if (n.level == level) {
1181 // CL3 [Choose subtree] If N is not at the desired level, let F be the entry in N
1182 // whose rectangle FI needs least enlargement to include EI. Resolve
1183 // ties by choosing the entry with the rectangle of smaller area.
1184 float leastEnlargement = Rectangle.enlargement(n.entriesMinX[0], n.entriesMinY[0], n.entriesMaxX[0], n.entriesMaxY[0],
1185 minX, minY, maxX, maxY);
1186 int index = 0; // index of rectangle in subtree
1187 for (int i = 1; i < n.entryCount; i++) {
1188 float tempMinX = n.entriesMinX[i];
1189 float tempMinY = n.entriesMinY[i];
1190 float tempMaxX = n.entriesMaxX[i];
1191 float tempMaxY = n.entriesMaxY[i];
1192 float tempEnlargement = Rectangle.enlargement(tempMinX, tempMinY, tempMaxX, tempMaxY,
1193 minX, minY, maxX, maxY);
1194 if ((tempEnlargement < leastEnlargement) ||
1195 ((tempEnlargement == leastEnlargement) &&
1196 (Rectangle.area(tempMinX, tempMinY, tempMaxX, tempMaxY) <
1197 Rectangle.area(n.entriesMinX[index], n.entriesMinY[index], n.entriesMaxX[index], n.entriesMaxY[index])))) {
1199 leastEnlargement = tempEnlargement;
1203 parents.push(n.nodeId);
1204 parentsEntry.push(index);
1206 // CL4 [Descend until a leaf is reached] Set N to be the child node
1207 // pointed to by Fp and repeat from CL2
1208 n = getNode(n.ids[index]);
1213 * Ascend from a leaf node L to the root, adjusting covering rectangles and
1214 * propagating node splits as necessary.
1216 private Node adjustTree(Node n, Node nn) {
1217 // AT1 [Initialize] Set N=L. If L was split previously, set NN to be
1218 // the resulting second node.
1220 // AT2 [Check if done] If N is the root, stop
1221 while (n.level != treeHeight) {
1223 // AT3 [Adjust covering rectangle in parent entry] Let P be the parent
1224 // node of N, and let En be N's entry in P. Adjust EnI so that it tightly
1225 // encloses all entry rectangles in N.
1226 Node parent = getNode(parents.pop());
1227 int entry = parentsEntry.pop();
1229 if (parent.ids[entry] != n.nodeId) {
1230 log.error("Error: entry " + entry + " in node " +
1231 parent.nodeId + " should point to node " +
1232 n.nodeId + "; actually points to node " + parent.ids[entry]);
1235 if (parent.entriesMinX[entry] != n.mbrMinX ||
1236 parent.entriesMinY[entry] != n.mbrMinY ||
1237 parent.entriesMaxX[entry] != n.mbrMaxX ||
1238 parent.entriesMaxY[entry] != n.mbrMaxY) {
1240 parent.entriesMinX[entry] = n.mbrMinX;
1241 parent.entriesMinY[entry] = n.mbrMinY;
1242 parent.entriesMaxX[entry] = n.mbrMaxX;
1243 parent.entriesMaxY[entry] = n.mbrMaxY;
1245 parent.recalculateMBR();
1248 // AT4 [Propagate node split upward] If N has a partner NN resulting from
1249 // an earlier split, create a new entry Enn with Ennp pointing to NN and
1250 // Enni enclosing all rectangles in NN. Add Enn to P if there is room.
1251 // Otherwise, invoke splitNode to produce P and PP containing Enn and
1252 // all P's old entries.
1253 Node newNode = null;
1255 if (parent.entryCount < maxNodeEntries) {
1256 parent.addEntry(nn.mbrMinX, nn.mbrMinY, nn.mbrMaxX, nn.mbrMaxY, nn.nodeId);
1258 newNode = splitNode(parent, nn.mbrMinX, nn.mbrMinY, nn.mbrMaxX, nn.mbrMaxY, nn.nodeId);
1262 // AT5 [Move up to next level] Set N = P and set NN = PP if a split
1263 // occurred. Repeat from AT2
1276 * Check the consistency of the tree.
1278 * @return false if an inconsistency is detected, true otherwise.
1280 public boolean checkConsistency() {
1281 return checkConsistency(rootNodeId, treeHeight, null);
1284 private boolean checkConsistency(int nodeId, int expectedLevel, Rectangle expectedMBR) {
1285 // go through the tree, and check that the internal data structures of
1286 // the tree are not corrupted.
1287 Node n = getNode(nodeId);
1290 log.error("Error: Could not read node " + nodeId);
1294 // if tree is empty, then there should be exactly one node, at level 1
1295 // TODO: also check the MBR is as for a new node
1296 if (nodeId == rootNodeId && size() == 0) {
1298 log.error("Error: tree is empty but root node is not at level 1");
1303 if (n.level != expectedLevel) {
1304 log.error("Error: Node " + nodeId + ", expected level " + expectedLevel + ", actual level " + n.level);
1308 Rectangle calculatedMBR = calculateMBR(n);
1309 Rectangle actualMBR = new Rectangle();
1310 actualMBR.minX = n.mbrMinX;
1311 actualMBR.minY = n.mbrMinY;
1312 actualMBR.maxX = n.mbrMaxX;
1313 actualMBR.maxY = n.mbrMaxY;
1314 if (!actualMBR.equals(calculatedMBR)) {
1315 log.error("Error: Node " + nodeId + ", calculated MBR does not equal stored MBR");
1316 if (actualMBR.minX != n.mbrMinX) log.error(" actualMinX=" + actualMBR.minX + ", calc=" + calculatedMBR.minX);
1317 if (actualMBR.minY != n.mbrMinY) log.error(" actualMinY=" + actualMBR.minY + ", calc=" + calculatedMBR.minY);
1318 if (actualMBR.maxX != n.mbrMaxX) log.error(" actualMaxX=" + actualMBR.maxX + ", calc=" + calculatedMBR.maxX);
1319 if (actualMBR.maxY != n.mbrMaxY) log.error(" actualMaxY=" + actualMBR.maxY + ", calc=" + calculatedMBR.maxY);
1323 if (expectedMBR != null && !actualMBR.equals(expectedMBR)) {
1324 log.error("Error: Node " + nodeId + ", expected MBR (from parent) does not equal stored MBR");
1328 // Check for corruption where a parent entry is the same object as the child MBR
1329 if (expectedMBR != null && actualMBR.sameObject(expectedMBR)) {
1330 log.error("Error: Node " + nodeId + " MBR using same rectangle object as parent's entry");
1334 for (int i = 0; i < n.entryCount; i++) {
1335 if (n.ids[i] == -1) {
1336 log.error("Error: Node " + nodeId + ", Entry " + i + " is null");
1340 if (n.level > 1) { // if not a leaf
1341 if (!checkConsistency(n.ids[i], n.level - 1, new Rectangle(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i]))) {
1350 * Given a node object, calculate the node MBR from it's entries.
1351 * Used in consistency checking
1353 private Rectangle calculateMBR(Node n) {
1354 Rectangle mbr = new Rectangle();
1356 for (int i = 0; i < n.entryCount; i++) {
1357 if (n.entriesMinX[i] < mbr.minX) mbr.minX = n.entriesMinX[i];
1358 if (n.entriesMinY[i] < mbr.minY) mbr.minY = n.entriesMinY[i];
1359 if (n.entriesMaxX[i] > mbr.maxX) mbr.maxX = n.entriesMaxX[i];
1360 if (n.entriesMaxY[i] > mbr.maxY) mbr.maxY = n.entriesMaxY[i];