-// RTree.java\r
-// Java Spatial Index Library\r
-// Copyright (C) 2002-2005 Infomatiq Limited\r
-// Copyright (C) 2008-2010 aled@sourceforge.net\r
-// \r
-// This library is free software; you can redistribute it and/or\r
-// modify it under the terms of the GNU Lesser General Public\r
-// License as published by the Free Software Foundation; either\r
-// version 2.1 of the License, or (at your option) any later version.\r
-// \r
-// This library is distributed in the hope that it will be useful,\r
-// but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\r
-// Lesser General Public License for more details.\r
-// \r
-// You should have received a copy of the GNU Lesser General Public\r
-// License along with this library; if not, write to the Free Software\r
-// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\r
-\r
-package com.infomatiq.jsi.rtree;\r
-\r
-import gnu.trove.TIntArrayList;\r
-import gnu.trove.TIntObjectHashMap;\r
-import gnu.trove.TIntProcedure;\r
-import gnu.trove.TIntStack;\r
-\r
-import java.util.Properties;\r
-\r
-import com.infomatiq.jsi.Point;\r
-import com.infomatiq.jsi.Rectangle;\r
-import com.infomatiq.jsi.PriorityQueue;\r
-import com.infomatiq.jsi.SpatialIndex;\r
-\r
-/**\r
- * Stub replacement for org.apache.log4j.Logger to prevent dependency on log4j.\r
- * \r
- * @author Tuukka Lehtonen\r
- */\r
-class Logger {\r
- String name;\r
-\r
- public Logger(String name) {\r
- this.name = name;\r
- }\r
-\r
- public static Logger getLogger(String name) {\r
- return new Logger(name);\r
- }\r
-\r
- public void warn(String string) {\r
- //System.out.println(name + ": WARN " + string);\r
- }\r
-\r
- public boolean isDebugEnabled() {\r
- return false;\r
- }\r
-\r
- public void debug(String string) {\r
- //System.out.println(name + ": DEBUG " + string);\r
- }\r
-\r
- public void error(String string) {\r
- System.out.println(name + ": ERROR " + string);\r
- }\r
-}\r
-\r
-/**\r
- * <p>This is a lightweight RTree implementation, specifically designed \r
- * for the following features (in order of importance): \r
- * <ul>\r
- * <li>Fast intersection query performance. To achieve this, the RTree \r
- * uses only main memory to store entries. Obviously this will only improve\r
- * performance if there is enough physical memory to avoid paging.</li>\r
- * <li>Low memory requirements.</li>\r
- * <li>Fast add performance.</li>\r
- * </ul></p> \r
- * \r
- * <p>The main reason for the high speed of this RTree implementation is the \r
- * avoidance of the creation of unnecessary objects, mainly achieved by using\r
- * primitive collections from the trove4j library.</p>\r
- * \r
- * @author aled@sourceforge.net\r
- * @version 1.0b8\r
- */\r
-public class RTree implements SpatialIndex {\r
- private static final Logger log = Logger.getLogger(RTree.class.getName());\r
- private static final Logger deleteLog = Logger.getLogger(RTree.class.getName() + "-delete");\r
- \r
- private static final String version = "1.0b8";\r
- \r
- // parameters of the tree\r
- private final static int DEFAULT_MAX_NODE_ENTRIES = 10;\r
- int maxNodeEntries;\r
- int minNodeEntries;\r
- \r
- // map of nodeId -> node object\r
- // TODO eliminate this map - it should not be needed. Nodes\r
- // can be found by traversing the tree.\r
- private TIntObjectHashMap<Node> nodeMap = new TIntObjectHashMap<Node>();\r
- \r
- // internal consistency checking - set to true if debugging tree corruption\r
- private final static boolean INTERNAL_CONSISTENCY_CHECKING = false;\r
- \r
- // used to mark the status of entries during a node split\r
- private final static int ENTRY_STATUS_ASSIGNED = 0;\r
- private final static int ENTRY_STATUS_UNASSIGNED = 1; \r
- private byte[] entryStatus = null;\r
- private byte[] initialEntryStatus = null;\r
- \r
- // stacks used to store nodeId and entry index of each node \r
- // from the root down to the leaf. Enables fast lookup\r
- // of nodes when a split is propagated up the tree.\r
- private TIntStack parents = new TIntStack();\r
- private TIntStack parentsEntry = new TIntStack();\r
- \r
- // initialisation\r
- private int treeHeight = 1; // leaves are always level 1\r
- private int rootNodeId = 0;\r
- private int size = 0;\r
- \r
- // Enables creation of new nodes\r
- private int highestUsedNodeId = rootNodeId; \r
- \r
- // Deleted node objects are retained in the nodeMap, \r
- // so that they can be reused. Store the IDs of nodes\r
- // which can be reused.\r
- private TIntStack deletedNodeIds = new TIntStack();\r
- \r
- // List of nearest rectangles. Use a member variable to\r
- // avoid recreating the object each time nearest() is called.\r
- private TIntArrayList nearestIds = new TIntArrayList();\r
- private TIntArrayList savedValues = new TIntArrayList();\r
- private float savedPriority = 0;\r
-\r
- // List of nearestN rectangles\r
- private SortedList nearestNIds = new SortedList();\r
- \r
- // List of nearestN rectanges, used in the alternative nearestN implementation.\r
- private PriorityQueue distanceQueue = \r
- new PriorityQueue(PriorityQueue.SORT_ORDER_ASCENDING);\r
- \r
- /**\r
- * Constructor. Use init() method to initialize parameters of the RTree.\r
- */\r
- public RTree() { \r
- return; // NOP \r
- }\r
- \r
- //-------------------------------------------------------------------------\r
- // public implementation of SpatialIndex interface:\r
- // init(Properties)\r
- // add(Rectangle, int)\r
- // delete(Rectangle, int)\r
- // nearest(Point, TIntProcedure, float)\r
- // intersects(Rectangle, TIntProcedure)\r
- // contains(Rectangle, TIntProcedure)\r
- // size()\r
- //-------------------------------------------------------------------------\r
- /**\r
- * <p>Initialize implementation dependent properties of the RTree.\r
- * Currently implemented properties are:\r
- * <ul>\r
- * <li>MaxNodeEntries</li> This specifies the maximum number of entries\r
- * in a node. The default value is 10, which is used if the property is\r
- * not specified, or is less than 2.\r
- * <li>MinNodeEntries</li> This specifies the minimum number of entries\r
- * in a node. The default value is half of the MaxNodeEntries value (rounded\r
- * down), which is used if the property is not specified or is less than 1.\r
- * </ul></p>\r
- * \r
- * @see com.infomatiq.jsi.SpatialIndex#init(Properties)\r
- */\r
- public void init(Properties props) {\r
- if (props == null) {\r
- // use sensible defaults if null is passed in.\r
- maxNodeEntries = 50;\r
- minNodeEntries = 20;\r
- } else {\r
- maxNodeEntries = Integer.parseInt(props.getProperty("MaxNodeEntries", "0"));\r
- minNodeEntries = Integer.parseInt(props.getProperty("MinNodeEntries", "0"));\r
- \r
- // Obviously a node with less than 2 entries cannot be split.\r
- // The node splitting algorithm will work with only 2 entries\r
- // per node, but will be inefficient.\r
- if (maxNodeEntries < 2) { \r
- log.warn("Invalid MaxNodeEntries = " + maxNodeEntries + " Resetting to default value of " + DEFAULT_MAX_NODE_ENTRIES);\r
- maxNodeEntries = DEFAULT_MAX_NODE_ENTRIES;\r
- }\r
- \r
- // The MinNodeEntries must be less than or equal to (int) (MaxNodeEntries / 2)\r
- if (minNodeEntries < 1 || minNodeEntries > maxNodeEntries / 2) {\r
- log.warn("MinNodeEntries must be between 1 and MaxNodeEntries / 2");\r
- minNodeEntries = maxNodeEntries / 2;\r
- }\r
- }\r
- \r
- entryStatus = new byte[maxNodeEntries]; \r
- initialEntryStatus = new byte[maxNodeEntries];\r
- \r
- for (int i = 0; i < maxNodeEntries; i++) {\r
- initialEntryStatus[i] = ENTRY_STATUS_UNASSIGNED;\r
- }\r
- \r
- Node root = new Node(rootNodeId, 1, maxNodeEntries);\r
- nodeMap.put(rootNodeId, root);\r
- \r
- log.debug("init() " + " MaxNodeEntries = " + maxNodeEntries + ", MinNodeEntries = " + minNodeEntries);\r
- }\r
- \r
- /**\r
- * @see com.infomatiq.jsi.SpatialIndex#add(Rectangle, int)\r
- */\r
- public void add(Rectangle r, int id) {\r
- if (log.isDebugEnabled()) {\r
- log.debug("Adding rectangle " + r + ", id " + id);\r
- }\r
- \r
- add(r.minX, r.minY, r.maxX, r.maxY, id, 1); \r
- \r
- size++;\r
- \r
- if (INTERNAL_CONSISTENCY_CHECKING) {\r
- checkConsistency();\r
- }\r
- }\r
- \r
- /**\r
- * Adds a new entry at a specified level in the tree\r
- */\r
- private void add(float minX, float minY, float maxX, float maxY, int id, int level) {\r
- // I1 [Find position for new record] Invoke ChooseLeaf to select a \r
- // leaf node L in which to place r\r
- Node n = chooseNode(minX, minY, maxX, maxY, level);\r
- Node newLeaf = null;\r
- \r
- // I2 [Add record to leaf node] If L has room for another entry, \r
- // install E. Otherwise invoke SplitNode to obtain L and LL containing\r
- // E and all the old entries of L\r
- if (n.entryCount < maxNodeEntries) {\r
- n.addEntry(minX, minY, maxX, maxY, id);\r
- } else {\r
- newLeaf = splitNode(n, minX, minY, maxX, maxY, id); \r
- }\r
- \r
- // I3 [Propagate changes upwards] Invoke AdjustTree on L, also passing LL\r
- // if a split was performed\r
- Node newNode = adjustTree(n, newLeaf); \r
-\r
- // I4 [Grow tree taller] If node split propagation caused the root to \r
- // split, create a new root whose children are the two resulting nodes.\r
- if (newNode != null) {\r
- int oldRootNodeId = rootNodeId;\r
- Node oldRoot = getNode(oldRootNodeId);\r
- \r
- rootNodeId = getNextNodeId();\r
- treeHeight++;\r
- Node root = new Node(rootNodeId, treeHeight, maxNodeEntries);\r
- root.addEntry(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY, newNode.nodeId);\r
- root.addEntry(oldRoot.mbrMinX, oldRoot.mbrMinY, oldRoot.mbrMaxX, oldRoot.mbrMaxY, oldRoot.nodeId);\r
- nodeMap.put(rootNodeId, root);\r
- } \r
- } \r
- \r
- /**\r
- * @see com.infomatiq.jsi.SpatialIndex#delete(Rectangle, int)\r
- */\r
- public boolean delete(Rectangle r, int id) {\r
- // FindLeaf algorithm inlined here. Note the "official" algorithm \r
- // searches all overlapping entries. This seems inefficient to me, \r
- // as an entry is only worth searching if it contains (NOT overlaps)\r
- // the rectangle we are searching for.\r
- //\r
- // Also the algorithm has been changed so that it is not recursive.\r
- \r
- // FL1 [Search subtrees] If root is not a leaf, check each entry \r
- // to determine if it contains r. For each entry found, invoke\r
- // findLeaf on the node pointed to by the entry, until r is found or\r
- // all entries have been checked.\r
- parents.reset();\r
- parents.push(rootNodeId);\r
- \r
- parentsEntry.reset();\r
- parentsEntry.push(-1);\r
- Node n = null;\r
- int foundIndex = -1; // index of entry to be deleted in leaf\r
- \r
- while (foundIndex == -1 && parents.size() > 0) {\r
- n = getNode(parents.peek());\r
- int startIndex = parentsEntry.peek() + 1;\r
- \r
- if (!n.isLeaf()) {\r
- deleteLog.debug("searching node " + n.nodeId + ", from index " + startIndex);\r
- boolean contains = false;\r
- for (int i = startIndex; i < n.entryCount; i++) {\r
- if (Rectangle.contains(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i],\r
- r.minX, r.minY, r.maxX, r.maxY)) { \r
- parents.push(n.ids[i]);\r
- parentsEntry.pop();\r
- parentsEntry.push(i); // this becomes the start index when the child has been searched\r
- parentsEntry.push(-1);\r
- contains = true;\r
- break; // ie go to next iteration of while()\r
- }\r
- }\r
- if (contains) {\r
- continue;\r
- }\r
- } else {\r
- foundIndex = n.findEntry(r.minX, r.minY, r.maxX, r.maxY, id); \r
- }\r
- \r
- parents.pop();\r
- parentsEntry.pop();\r
- } // while not found\r
- \r
- if (foundIndex != -1) {\r
- n.deleteEntry(foundIndex);\r
- condenseTree(n);\r
- size--;\r
- }\r
- \r
- // shrink the tree if possible (i.e. if root node has exactly one entry,and that \r
- // entry is not a leaf node, delete the root (it's entry becomes the new root)\r
- Node root = getNode(rootNodeId);\r
- while (root.entryCount == 1 && treeHeight > 1)\r
- {\r
- deletedNodeIds.push(rootNodeId);\r
- root.entryCount = 0;\r
- rootNodeId = root.ids[0];\r
- treeHeight--;\r
- root = getNode(rootNodeId);\r
- }\r
- \r
- // if the tree is now empty, then set the MBR of the root node back to it's original state\r
- // (this is only needed when the tree is empty, as this is the only state where an empty node\r
- // is not eliminated)\r
- if (size == 0) {\r
- root.mbrMinX = Float.MAX_VALUE;\r
- root.mbrMinY = Float.MAX_VALUE;\r
- root.mbrMaxX = -Float.MAX_VALUE;\r
- root.mbrMaxY = -Float.MAX_VALUE;\r
- }\r
-\r
- if (INTERNAL_CONSISTENCY_CHECKING) {\r
- checkConsistency();\r
- }\r
- \r
- return (foundIndex != -1);\r
- }\r
- \r
- /**\r
- * @see com.infomatiq.jsi.SpatialIndex#nearest(Point, TIntProcedure, float)\r
- */\r
- public void nearest(Point p, TIntProcedure v, float furthestDistance) {\r
- Node rootNode = getNode(rootNodeId);\r
- \r
- float furthestDistanceSq = furthestDistance * furthestDistance;\r
- nearest(p, rootNode, furthestDistanceSq);\r
- \r
- nearestIds.forEach(v);\r
- nearestIds.reset();\r
- }\r
- \r
- private void createNearestNDistanceQueue(Point p, int count, float furthestDistance) {\r
- distanceQueue.reset();\r
- distanceQueue.setSortOrder(PriorityQueue.SORT_ORDER_DESCENDING);\r
- \r
- // return immediately if given an invalid "count" parameter\r
- if (count <= 0) {\r
- return;\r
- } \r
- \r
- parents.reset();\r
- parents.push(rootNodeId);\r
- \r
- parentsEntry.reset();\r
- parentsEntry.push(-1);\r
- \r
- // TODO: possible shortcut here - could test for intersection with the \r
- // MBR of the root node. If no intersection, return immediately.\r
- \r
- float furthestDistanceSq = furthestDistance * furthestDistance;\r
- \r
- while (parents.size() > 0) {\r
- Node n = getNode(parents.peek());\r
- int startIndex = parentsEntry.peek() + 1;\r
- \r
- if (!n.isLeaf()) {\r
- // go through every entry in the index node to check\r
- // if it could contain an entry closer than the farthest entry\r
- // currently stored.\r
- boolean near = false;\r
- for (int i = startIndex; i < n.entryCount; i++) {\r
- if (Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i], \r
- n.entriesMaxX[i], n.entriesMaxY[i], \r
- p.x, p.y) <= furthestDistanceSq) {\r
- parents.push(n.ids[i]);\r
- parentsEntry.pop();\r
- parentsEntry.push(i); // this becomes the start index when the child has been searched\r
- parentsEntry.push(-1);\r
- near = true;\r
- break; // ie go to next iteration of while()\r
- }\r
- }\r
- if (near) {\r
- continue;\r
- }\r
- } else {\r
- // go through every entry in the leaf to check if \r
- // it is currently one of the nearest N entries.\r
- for (int i = 0; i < n.entryCount; i++) {\r
- float entryDistanceSq = Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i],\r
- n.entriesMaxX[i], n.entriesMaxY[i],\r
- p.x, p.y);\r
- int entryId = n.ids[i];\r
- \r
- if (entryDistanceSq <= furthestDistanceSq) {\r
- distanceQueue.insert(entryId, entryDistanceSq);\r
- \r
- while (distanceQueue.size() > count) {\r
- // normal case - we can simply remove the lowest priority (highest distance) entry\r
- int value = distanceQueue.getValue();\r
- float distanceSq = distanceQueue.getPriority();\r
- distanceQueue.pop();\r
- \r
- // rare case - multiple items of the same priority (distance)\r
- if (distanceSq == distanceQueue.getPriority()) {\r
- savedValues.add(value);\r
- savedPriority = distanceSq;\r
- } else {\r
- savedValues.reset();\r
- }\r
- }\r
- \r
- // if the saved values have the same distance as the\r
- // next one in the tree, add them back in.\r
- if (savedValues.size() > 0 && savedPriority == distanceQueue.getPriority()) {\r
- for (int svi = 0; svi < savedValues.size(); svi++) {\r
- distanceQueue.insert(savedValues.get(svi), savedPriority);\r
- }\r
- savedValues.reset();\r
- }\r
- \r
- // narrow the search, if we have already found N items\r
- if (distanceQueue.getPriority() < furthestDistanceSq && distanceQueue.size() >= count) {\r
- furthestDistanceSq = distanceQueue.getPriority(); \r
- }\r
- } \r
- } \r
- }\r
- parents.pop();\r
- parentsEntry.pop(); \r
- }\r
- }\r
- \r
- /**\r
- * @see com.infomatiq.jsi.SpatialIndex#nearestNUnsorted(Point, TIntProcedure, int, float)\r
- */\r
- public void nearestNUnsorted(Point p, TIntProcedure v, int count, float furthestDistance) {\r
- // This implementation is designed to give good performance\r
- // where\r
- // o N is high (100+)\r
- // o The results do not need to be sorted by distance.\r
- // \r
- // Uses a priority queue as the underlying data structure. \r
- // \r
- // The behaviour of this algorithm has been carefully designed to\r
- // return exactly the same items as the the original version (nearestN_orig), in particular,\r
- // more than N items will be returned if items N and N+x have the\r
- // same priority. \r
- createNearestNDistanceQueue(p, count, furthestDistance);\r
- \r
- while (distanceQueue.size() > 0) {\r
- v.execute(distanceQueue.getValue());\r
- distanceQueue.pop();\r
- }\r
- }\r
- \r
- /**\r
- * @see com.infomatiq.jsi.SpatialIndex#nearestN(Point, TIntProcedure, int, float)\r
- */\r
- public void nearestN(Point p, TIntProcedure v, int count, float furthestDistance) {\r
- createNearestNDistanceQueue(p, count, furthestDistance);\r
- \r
- distanceQueue.setSortOrder(PriorityQueue.SORT_ORDER_ASCENDING);\r
- \r
- while (distanceQueue.size() > 0) {\r
- v.execute(distanceQueue.getValue());\r
- distanceQueue.pop();\r
- } \r
- }\r
- \r
- /**\r
- * @see com.infomatiq.jsi.SpatialIndex#nearestN(Point, TIntProcedure, int, float)\r
- * @deprecated Use new NearestN or NearestNUnsorted instead.\r
- * \r
- * This implementation of nearestN is only suitable for small values of N (ie less than 10).\r
- */ \r
- public void nearestN_orig(Point p, TIntProcedure v, int count, float furthestDistance) {\r
- // return immediately if given an invalid "count" parameter\r
- if (count <= 0) {\r
- return;\r
- }\r
- \r
- parents.reset();\r
- parents.push(rootNodeId);\r
- \r
- parentsEntry.reset();\r
- parentsEntry.push(-1);\r
- \r
- nearestNIds.init(count);\r
- \r
- // TODO: possible shortcut here - could test for intersection with the \r
- // MBR of the root node. If no intersection, return immediately.\r
- \r
- float furthestDistanceSq = furthestDistance * furthestDistance;\r
- \r
- while (parents.size() > 0) {\r
- Node n = getNode(parents.peek());\r
- int startIndex = parentsEntry.peek() + 1;\r
- \r
- if (!n.isLeaf()) {\r
- // go through every entry in the index node to check\r
- // if it could contain an entry closer than the farthest entry\r
- // currently stored.\r
- boolean near = false;\r
- for (int i = startIndex; i < n.entryCount; i++) {\r
- if (Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i], \r
- n.entriesMaxX[i], n.entriesMaxY[i], \r
- p.x, p.y) <= furthestDistanceSq) {\r
- parents.push(n.ids[i]);\r
- parentsEntry.pop();\r
- parentsEntry.push(i); // this becomes the start index when the child has been searched\r
- parentsEntry.push(-1);\r
- near = true;\r
- break; // ie go to next iteration of while()\r
- }\r
- }\r
- if (near) {\r
- continue;\r
- }\r
- } else {\r
- // go through every entry in the leaf to check if \r
- // it is currently one of the nearest N entries.\r
- for (int i = 0; i < n.entryCount; i++) {\r
- float entryDistanceSq = Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i],\r
- n.entriesMaxX[i], n.entriesMaxY[i],\r
- p.x, p.y);\r
- int entryId = n.ids[i];\r
- \r
- if (entryDistanceSq <= furthestDistanceSq) {\r
- // add the new entry to the tree. Note that the higher the distance, the lower the priority\r
- nearestNIds.add(entryId, -entryDistanceSq);\r
- \r
- float tempFurthestDistanceSq = -nearestNIds.getLowestPriority();\r
- if (tempFurthestDistanceSq < furthestDistanceSq) {\r
- furthestDistanceSq = tempFurthestDistanceSq; \r
- }\r
- } \r
- } \r
- }\r
- parents.pop();\r
- parentsEntry.pop(); \r
- }\r
- \r
- nearestNIds.forEachId(v);\r
- }\r
- \r
- /**\r
- * @see com.infomatiq.jsi.SpatialIndex#intersects(Rectangle, TIntProcedure)\r
- */\r
- public void intersects(Rectangle r, TIntProcedure v) {\r
- Node rootNode = getNode(rootNodeId);\r
- intersects(r, v, rootNode);\r
- }\r
-\r
- /**\r
- * @see com.infomatiq.jsi.SpatialIndex#contains(Rectangle, TIntProcedure)\r
- */\r
- public void contains(Rectangle r, TIntProcedure v) {\r
- // find all rectangles in the tree that are contained by the passed rectangle\r
- // written to be non-recursive (should model other searches on this?)\r
- \r
- parents.reset();\r
- parents.push(rootNodeId);\r
- \r
- parentsEntry.reset();\r
- parentsEntry.push(-1);\r
- \r
- // TODO: possible shortcut here - could test for intersection with the \r
- // MBR of the root node. If no intersection, return immediately.\r
- \r
- while (parents.size() > 0) {\r
- Node n = getNode(parents.peek());\r
- int startIndex = parentsEntry.peek() + 1;\r
- \r
- if (!n.isLeaf()) {\r
- // go through every entry in the index node to check\r
- // if it intersects the passed rectangle. If so, it \r
- // could contain entries that are contained.\r
- boolean intersects = false;\r
- for (int i = startIndex; i < n.entryCount; i++) {\r
- if (Rectangle.intersects(r.minX, r.minY, r.maxX, r.maxY, \r
- n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i])) {\r
- parents.push(n.ids[i]);\r
- parentsEntry.pop();\r
- parentsEntry.push(i); // this becomes the start index when the child has been searched\r
- parentsEntry.push(-1);\r
- intersects = true;\r
- break; // ie go to next iteration of while()\r
- }\r
- }\r
- if (intersects) {\r
- continue;\r
- }\r
- } else {\r
- // go through every entry in the leaf to check if \r
- // it is contained by the passed rectangle\r
- for (int i = 0; i < n.entryCount; i++) {\r
- if (Rectangle.contains(r.minX, r.minY, r.maxX, r.maxY, \r
- n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i])) {\r
- if (!v.execute(n.ids[i])) {\r
- return;\r
- }\r
- } \r
- } \r
- }\r
- parents.pop();\r
- parentsEntry.pop(); \r
- }\r
- }\r
-\r
- /**\r
- * @see com.infomatiq.jsi.SpatialIndex#size()\r
- */\r
- public int size() {\r
- return size;\r
- }\r
-\r
- /**\r
- * @see com.infomatiq.jsi.SpatialIndex#getBounds()\r
- */\r
- public Rectangle getBounds() {\r
- Rectangle bounds = null;\r
- \r
- Node n = getNode(getRootNodeId());\r
- if (n != null && n.entryCount > 0) {\r
- bounds = new Rectangle();\r
- bounds.minX = n.mbrMinX;\r
- bounds.minY = n.mbrMinY;\r
- bounds.maxX = n.mbrMaxX;\r
- bounds.maxY = n.mbrMaxY;\r
- }\r
- return bounds;\r
- }\r
- \r
- /**\r
- * @see com.infomatiq.jsi.SpatialIndex#getVersion()\r
- */\r
- public String getVersion() {\r
- return "RTree-" + version;\r
- }\r
- //-------------------------------------------------------------------------\r
- // end of SpatialIndex methods\r
- //-------------------------------------------------------------------------\r
- \r
- /**\r
- * Get the next available node ID. Reuse deleted node IDs if\r
- * possible\r
- */\r
- private int getNextNodeId() {\r
- int nextNodeId = 0;\r
- if (deletedNodeIds.size() > 0) {\r
- nextNodeId = deletedNodeIds.pop();\r
- } else {\r
- nextNodeId = 1 + highestUsedNodeId++;\r
- }\r
- return nextNodeId;\r
- }\r
-\r
- /**\r
- * Get a node object, given the ID of the node.\r
- */\r
- public Node getNode(int id) {\r
- return nodeMap.get(id);\r
- }\r
-\r
- /**\r
- * Get the highest used node ID\r
- */ \r
- public int getHighestUsedNodeId() {\r
- return highestUsedNodeId;\r
- }\r
-\r
- /**\r
- * Get the root node ID\r
- */\r
- public int getRootNodeId() {\r
- return rootNodeId; \r
- }\r
- \r
- /**\r
- * Split a node. Algorithm is taken pretty much verbatim from\r
- * Guttman's original paper.\r
- * \r
- * @return new node object.\r
- */\r
- private Node splitNode(Node n, float newRectMinX, float newRectMinY, float newRectMaxX, float newRectMaxY, int newId) {\r
- // [Pick first entry for each group] Apply algorithm pickSeeds to \r
- // choose two entries to be the first elements of the groups. Assign\r
- // each to a group.\r
- \r
- // debug code\r
- float initialArea = 0;\r
- if (log.isDebugEnabled()) {\r
- float unionMinX = Math.min(n.mbrMinX, newRectMinX);\r
- float unionMinY = Math.min(n.mbrMinY, newRectMinY);\r
- float unionMaxX = Math.max(n.mbrMaxX, newRectMaxX);\r
- float unionMaxY = Math.max(n.mbrMaxY, newRectMaxY);\r
- \r
- initialArea = (unionMaxX - unionMinX) * (unionMaxY - unionMinY);\r
- }\r
- \r
- System.arraycopy(initialEntryStatus, 0, entryStatus, 0, maxNodeEntries);\r
- \r
- Node newNode = null;\r
- newNode = new Node(getNextNodeId(), n.level, maxNodeEntries);\r
- nodeMap.put(newNode.nodeId, newNode);\r
- \r
- pickSeeds(n, newRectMinX, newRectMinY, newRectMaxX, newRectMaxY, newId, newNode); // this also sets the entryCount to 1\r
- \r
- // [Check if done] If all entries have been assigned, stop. If one\r
- // group has so few entries that all the rest must be assigned to it in \r
- // order for it to have the minimum number m, assign them and stop. \r
- while (n.entryCount + newNode.entryCount < maxNodeEntries + 1) {\r
- if (maxNodeEntries + 1 - newNode.entryCount == minNodeEntries) {\r
- // assign all remaining entries to original node\r
- for (int i = 0; i < maxNodeEntries; i++) {\r
- if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED) {\r
- entryStatus[i] = ENTRY_STATUS_ASSIGNED;\r
- \r
- if (n.entriesMinX[i] < n.mbrMinX) n.mbrMinX = n.entriesMinX[i];\r
- if (n.entriesMinY[i] < n.mbrMinY) n.mbrMinY = n.entriesMinY[i];\r
- if (n.entriesMaxX[i] > n.mbrMaxX) n.mbrMaxX = n.entriesMaxX[i];\r
- if (n.entriesMaxY[i] > n.mbrMaxY) n.mbrMaxY = n.entriesMaxY[i];\r
- \r
- n.entryCount++;\r
- }\r
- }\r
- break;\r
- } \r
- if (maxNodeEntries + 1 - n.entryCount == minNodeEntries) {\r
- // assign all remaining entries to new node\r
- for (int i = 0; i < maxNodeEntries; i++) {\r
- if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED) {\r
- entryStatus[i] = ENTRY_STATUS_ASSIGNED;\r
- newNode.addEntry(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i], n.ids[i]);\r
- n.ids[i] = -1; // an id of -1 indicates the entry is not in use\r
- }\r
- }\r
- break;\r
- }\r
- \r
- // [Select entry to assign] Invoke algorithm pickNext to choose the\r
- // next entry to assign. Add it to the group whose covering rectangle \r
- // will have to be enlarged least to accommodate it. Resolve ties\r
- // by adding the entry to the group with smaller area, then to the \r
- // the one with fewer entries, then to either. Repeat from S2\r
- pickNext(n, newNode); \r
- }\r
- \r
- n.reorganize(this);\r
- \r
- // check that the MBR stored for each node is correct.\r
- if (INTERNAL_CONSISTENCY_CHECKING) {\r
- Rectangle nMBR = new Rectangle(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY);\r
- if (!nMBR.equals(calculateMBR(n))) {\r
- log.error("Error: splitNode old node MBR wrong");\r
- }\r
- Rectangle newNodeMBR = new Rectangle(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY);\r
- if (!newNodeMBR.equals(calculateMBR(newNode))) {\r
- log.error("Error: splitNode new node MBR wrong");\r
- }\r
- }\r
- \r
- // debug code\r
- if (log.isDebugEnabled()) {\r
- float newArea = Rectangle.area(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY) + \r
- Rectangle.area(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY);\r
- float percentageIncrease = (100 * (newArea - initialArea)) / initialArea;\r
- log.debug("Node " + n.nodeId + " split. New area increased by " + percentageIncrease + "%"); \r
- }\r
- \r
- return newNode;\r
- }\r
- \r
- /**\r
- * Pick the seeds used to split a node.\r
- * Select two entries to be the first elements of the groups\r
- */\r
- private void pickSeeds(Node n, float newRectMinX, float newRectMinY, float newRectMaxX, float newRectMaxY, int newId, Node newNode) {\r
- // Find extreme rectangles along all dimension. Along each dimension,\r
- // find the entry whose rectangle has the highest low side, and the one \r
- // with the lowest high side. Record the separation.\r
- float maxNormalizedSeparation = -1; // initialize to -1 so that even overlapping rectangles will be considered for the seeds\r
- int highestLowIndex = -1;\r
- int lowestHighIndex = -1;\r
- \r
- // for the purposes of picking seeds, take the MBR of the node to include\r
- // the new rectangle aswell.\r
- if (newRectMinX < n.mbrMinX) n.mbrMinX = newRectMinX;\r
- if (newRectMinY < n.mbrMinY) n.mbrMinY = newRectMinY;\r
- if (newRectMaxX > n.mbrMaxX) n.mbrMaxX = newRectMaxX;\r
- if (newRectMaxY > n.mbrMaxY) n.mbrMaxY = newRectMaxY;\r
- \r
- float mbrLenX = n.mbrMaxX - n.mbrMinX;\r
- float mbrLenY = n.mbrMaxY - n.mbrMinY;\r
- \r
- if (log.isDebugEnabled()) {\r
- log.debug("pickSeeds(): NodeId = " + n.nodeId);\r
- }\r
- \r
- float tempHighestLow = newRectMinX;\r
- int tempHighestLowIndex = -1; // -1 indicates the new rectangle is the seed\r
- \r
- float tempLowestHigh = newRectMaxX;\r
- int tempLowestHighIndex = -1; // -1 indicates the new rectangle is the seed \r
- \r
- for (int i = 0; i < n.entryCount; i++) {\r
- float tempLow = n.entriesMinX[i];\r
- if (tempLow >= tempHighestLow) {\r
- tempHighestLow = tempLow;\r
- tempHighestLowIndex = i;\r
- } else { // ensure that the same index cannot be both lowestHigh and highestLow\r
- float tempHigh = n.entriesMaxX[i];\r
- if (tempHigh <= tempLowestHigh) {\r
- tempLowestHigh = tempHigh;\r
- tempLowestHighIndex = i;\r
- }\r
- }\r
- \r
- // PS2 [Adjust for shape of the rectangle cluster] Normalize the separations\r
- // by dividing by the widths of the entire set along the corresponding\r
- // dimension\r
- float normalizedSeparation = mbrLenX == 0 ? 1 : (tempHighestLow - tempLowestHigh) / mbrLenX;\r
- if (normalizedSeparation > 1 || normalizedSeparation < -1) {\r
- log.error("Invalid normalized separation X");\r
- }\r
- \r
- if (log.isDebugEnabled()) {\r
- log.debug("Entry " + i + ", dimension X: HighestLow = " + tempHighestLow + \r
- " (index " + tempHighestLowIndex + ")" + ", LowestHigh = " +\r
- tempLowestHigh + " (index " + tempLowestHighIndex + ", NormalizedSeparation = " + normalizedSeparation);\r
- }\r
- \r
- // PS3 [Select the most extreme pair] Choose the pair with the greatest\r
- // normalized separation along any dimension.\r
- // Note that if negative it means the rectangles overlapped. However still include\r
- // overlapping rectangles if that is the only choice available.\r
- if (normalizedSeparation >= maxNormalizedSeparation) {\r
- highestLowIndex = tempHighestLowIndex;\r
- lowestHighIndex = tempLowestHighIndex;\r
- maxNormalizedSeparation = normalizedSeparation;\r
- }\r
- }\r
- \r
- // Repeat for the Y dimension\r
- tempHighestLow = newRectMinY;\r
- tempHighestLowIndex = -1; // -1 indicates the new rectangle is the seed\r
- \r
- tempLowestHigh = newRectMaxY;\r
- tempLowestHighIndex = -1; // -1 indicates the new rectangle is the seed \r
- \r
- for (int i = 0; i < n.entryCount; i++) {\r
- float tempLow = n.entriesMinY[i];\r
- if (tempLow >= tempHighestLow) {\r
- tempHighestLow = tempLow;\r
- tempHighestLowIndex = i;\r
- } else { // ensure that the same index cannot be both lowestHigh and highestLow\r
- float tempHigh = n.entriesMaxY[i];\r
- if (tempHigh <= tempLowestHigh) {\r
- tempLowestHigh = tempHigh;\r
- tempLowestHighIndex = i;\r
- }\r
- }\r
- \r
- // PS2 [Adjust for shape of the rectangle cluster] Normalize the separations\r
- // by dividing by the widths of the entire set along the corresponding\r
- // dimension\r
- float normalizedSeparation = mbrLenY == 0 ? 1 : (tempHighestLow - tempLowestHigh) / mbrLenY;\r
- if (normalizedSeparation > 1 || normalizedSeparation < -1) {\r
- log.error("Invalid normalized separation Y");\r
- }\r
- \r
- if (log.isDebugEnabled()) {\r
- log.debug("Entry " + i + ", dimension Y: HighestLow = " + tempHighestLow + \r
- " (index " + tempHighestLowIndex + ")" + ", LowestHigh = " +\r
- tempLowestHigh + " (index " + tempLowestHighIndex + ", NormalizedSeparation = " + normalizedSeparation);\r
- }\r
- \r
- // PS3 [Select the most extreme pair] Choose the pair with the greatest\r
- // normalized separation along any dimension.\r
- // Note that if negative it means the rectangles overlapped. However still include\r
- // overlapping rectangles if that is the only choice available.\r
- if (normalizedSeparation >= maxNormalizedSeparation) {\r
- highestLowIndex = tempHighestLowIndex;\r
- lowestHighIndex = tempLowestHighIndex;\r
- maxNormalizedSeparation = normalizedSeparation;\r
- }\r
- }\r
- \r
- // At this point it is possible that the new rectangle is both highestLow and lowestHigh.\r
- // This can happen if all rectangles in the node overlap the new rectangle.\r
- // Resolve this by declaring that the highestLowIndex is the lowest Y and,\r
- // the lowestHighIndex is the largest X (but always a different rectangle)\r
- if (highestLowIndex == lowestHighIndex) { \r
- highestLowIndex = -1;\r
- float tempMinY = newRectMinY;\r
- lowestHighIndex = 0;\r
- float tempMaxX = n.entriesMaxX[0];\r
- \r
- for (int i = 1; i < n.entryCount; i++) {\r
- if (n.entriesMinY[i] < tempMinY) {\r
- tempMinY = n.entriesMinY[i];\r
- highestLowIndex = i;\r
- }\r
- else if (n.entriesMaxX[i] > tempMaxX) {\r
- tempMaxX = n.entriesMaxX[i];\r
- lowestHighIndex = i;\r
- }\r
- }\r
- }\r
- \r
- // highestLowIndex is the seed for the new node.\r
- if (highestLowIndex == -1) {\r
- newNode.addEntry(newRectMinX, newRectMinY, newRectMaxX, newRectMaxY, newId);\r
- } else {\r
- newNode.addEntry(n.entriesMinX[highestLowIndex], n.entriesMinY[highestLowIndex], \r
- n.entriesMaxX[highestLowIndex], n.entriesMaxY[highestLowIndex], \r
- n.ids[highestLowIndex]);\r
- n.ids[highestLowIndex] = -1;\r
- \r
- // move the new rectangle into the space vacated by the seed for the new node\r
- n.entriesMinX[highestLowIndex] = newRectMinX;\r
- n.entriesMinY[highestLowIndex] = newRectMinY;\r
- n.entriesMaxX[highestLowIndex] = newRectMaxX;\r
- n.entriesMaxY[highestLowIndex] = newRectMaxY;\r
- \r
- n.ids[highestLowIndex] = newId;\r
- }\r
- \r
- // lowestHighIndex is the seed for the original node. \r
- if (lowestHighIndex == -1) {\r
- lowestHighIndex = highestLowIndex;\r
- }\r
- \r
- entryStatus[lowestHighIndex] = ENTRY_STATUS_ASSIGNED;\r
- n.entryCount = 1;\r
- n.mbrMinX = n.entriesMinX[lowestHighIndex];\r
- n.mbrMinY = n.entriesMinY[lowestHighIndex];\r
- n.mbrMaxX = n.entriesMaxX[lowestHighIndex];\r
- n.mbrMaxY = n.entriesMaxY[lowestHighIndex];\r
- }\r
-\r
- /** \r
- * Pick the next entry to be assigned to a group during a node split.\r
- * \r
- * [Determine cost of putting each entry in each group] For each \r
- * entry not yet in a group, calculate the area increase required\r
- * in the covering rectangles of each group \r
- */\r
- private int pickNext(Node n, Node newNode) {\r
- float maxDifference = Float.NEGATIVE_INFINITY;\r
- int next = 0;\r
- int nextGroup = 0;\r
- \r
- maxDifference = Float.NEGATIVE_INFINITY;\r
- \r
- if (log.isDebugEnabled()) {\r
- log.debug("pickNext()");\r
- }\r
- \r
- for (int i = 0; i < maxNodeEntries; i++) {\r
- if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED) {\r
- \r
- if (n.ids[i] == -1) {\r
- log.error("Error: Node " + n.nodeId + ", entry " + i + " is null");\r
- }\r
- \r
- float nIncrease = Rectangle.enlargement(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY, \r
- n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i]);\r
- float newNodeIncrease = Rectangle.enlargement(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY,\r
- n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i]);\r
-\r
- float difference = Math.abs(nIncrease - newNodeIncrease);\r
- \r
- if (difference > maxDifference) {\r
- next = i;\r
- \r
- if (nIncrease < newNodeIncrease) {\r
- nextGroup = 0; \r
- } else if (newNodeIncrease < nIncrease) {\r
- nextGroup = 1;\r
- } else if (Rectangle.area(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY) < Rectangle.area(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY)) {\r
- nextGroup = 0;\r
- } else if (Rectangle.area(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY) < Rectangle.area(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY)) {\r
- nextGroup = 1;\r
- } else if (newNode.entryCount < maxNodeEntries / 2) {\r
- nextGroup = 0;\r
- } else {\r
- nextGroup = 1;\r
- }\r
- maxDifference = difference; \r
- }\r
- if (log.isDebugEnabled()) {\r
- log.debug("Entry " + i + " group0 increase = " + nIncrease + ", group1 increase = " + newNodeIncrease +\r
- ", diff = " + difference + ", MaxDiff = " + maxDifference + " (entry " + next + ")");\r
- }\r
- }\r
- }\r
- \r
- entryStatus[next] = ENTRY_STATUS_ASSIGNED;\r
- \r
- if (nextGroup == 0) {\r
- if (n.entriesMinX[next] < n.mbrMinX) n.mbrMinX = n.entriesMinX[next];\r
- if (n.entriesMinY[next] < n.mbrMinY) n.mbrMinY = n.entriesMinY[next];\r
- if (n.entriesMaxX[next] > n.mbrMaxX) n.mbrMaxX = n.entriesMaxX[next];\r
- if (n.entriesMaxY[next] > n.mbrMaxY) n.mbrMaxY = n.entriesMaxY[next];\r
- n.entryCount++;\r
- } else {\r
- // move to new node.\r
- newNode.addEntry(n.entriesMinX[next], n.entriesMinY[next], n.entriesMaxX[next], n.entriesMaxY[next], n.ids[next]);\r
- n.ids[next] = -1;\r
- }\r
- \r
- return next; \r
- }\r
-\r
- /**\r
- * Recursively searches the tree for the nearest entry. Other queries\r
- * call execute() on an IntProcedure when a matching entry is found; \r
- * however nearest() must store the entry Ids as it searches the tree,\r
- * in case a nearer entry is found.\r
- * Uses the member variable nearestIds to store the nearest\r
- * entry IDs.\r
- * \r
- * TODO rewrite this to be non-recursive?\r
- */\r
- private float nearest(Point p, Node n, float furthestDistanceSq) {\r
- for (int i = 0; i < n.entryCount; i++) {\r
- float tempDistanceSq = Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i], p.x, p.y);\r
- if (n.isLeaf()) { // for leaves, the distance is an actual nearest distance \r
- if (tempDistanceSq < furthestDistanceSq) {\r
- furthestDistanceSq = tempDistanceSq;\r
- nearestIds.reset();\r
- }\r
- if (tempDistanceSq <= furthestDistanceSq) {\r
- nearestIds.add(n.ids[i]);\r
- } \r
- } else { // for index nodes, only go into them if they potentially could have\r
- // a rectangle nearer than actualNearest\r
- if (tempDistanceSq <= furthestDistanceSq) {\r
- // search the child node\r
- furthestDistanceSq = nearest(p, getNode(n.ids[i]), furthestDistanceSq);\r
- }\r
- }\r
- }\r
- return furthestDistanceSq;\r
- }\r
- \r
- /** \r
- * Recursively searches the tree for all intersecting entries.\r
- * Immediately calls execute() on the passed IntProcedure when \r
- * a matching entry is found.\r
- * \r
- * TODO rewrite this to be non-recursive? Make sure it\r
- * doesn't slow it down.\r
- */\r
- private boolean intersects(Rectangle r, TIntProcedure v, Node n) {\r
- for (int i = 0; i < n.entryCount; i++) {\r
- if (Rectangle.intersects(r.minX, r.minY, r.maxX, r.maxY, n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i])) {\r
- if (n.isLeaf()) {\r
- if (!v.execute(n.ids[i])) {\r
- return false;\r
- }\r
- } else {\r
- Node childNode = getNode(n.ids[i]);\r
- if (!intersects(r, v, childNode)) {\r
- return false;\r
- }\r
- }\r
- }\r
- }\r
- return true;\r
- }\r
-\r
- /**\r
- * Used by delete(). Ensures that all nodes from the passed node\r
- * up to the root have the minimum number of entries.\r
- * \r
- * Note that the parent and parentEntry stacks are expected to\r
- * contain the nodeIds of all parents up to the root.\r
- */\r
- private void condenseTree(Node l) {\r
- // CT1 [Initialize] Set n=l. Set the list of eliminated\r
- // nodes to be empty.\r
- Node n = l;\r
- Node parent = null;\r
- int parentEntry = 0;\r
- \r
- TIntStack eliminatedNodeIds = new TIntStack();\r
- \r
- // CT2 [Find parent entry] If N is the root, go to CT6. Otherwise \r
- // let P be the parent of N, and let En be N's entry in P \r
- while (n.level != treeHeight) {\r
- parent = getNode(parents.pop());\r
- parentEntry = parentsEntry.pop();\r
- \r
- // CT3 [Eliminiate under-full node] If N has too few entries,\r
- // delete En from P and add N to the list of eliminated nodes\r
- if (n.entryCount < minNodeEntries) {\r
- parent.deleteEntry(parentEntry);\r
- eliminatedNodeIds.push(n.nodeId);\r
- } else {\r
- // CT4 [Adjust covering rectangle] If N has not been eliminated,\r
- // adjust EnI to tightly contain all entries in N\r
- if (n.mbrMinX != parent.entriesMinX[parentEntry] ||\r
- n.mbrMinY != parent.entriesMinY[parentEntry] ||\r
- n.mbrMaxX != parent.entriesMaxX[parentEntry] ||\r
- n.mbrMaxY != parent.entriesMaxY[parentEntry]) {\r
- float deletedMinX = parent.entriesMinX[parentEntry];\r
- float deletedMinY = parent.entriesMinY[parentEntry];\r
- float deletedMaxX = parent.entriesMaxX[parentEntry];\r
- float deletedMaxY = parent.entriesMaxY[parentEntry];\r
- parent.entriesMinX[parentEntry] = n.mbrMinX;\r
- parent.entriesMinY[parentEntry] = n.mbrMinY;\r
- parent.entriesMaxX[parentEntry] = n.mbrMaxX;\r
- parent.entriesMaxY[parentEntry] = n.mbrMaxY;\r
- parent.recalculateMBRIfInfluencedBy(deletedMinX, deletedMinY, deletedMaxX, deletedMaxY);\r
- }\r
- }\r
- // CT5 [Move up one level in tree] Set N=P and repeat from CT2\r
- n = parent;\r
- }\r
- \r
- // CT6 [Reinsert orphaned entries] Reinsert all entries of nodes in set Q.\r
- // Entries from eliminated leaf nodes are reinserted in tree leaves as in \r
- // Insert(), but entries from higher level nodes must be placed higher in \r
- // the tree, so that leaves of their dependent subtrees will be on the same\r
- // level as leaves of the main tree\r
- while (eliminatedNodeIds.size() > 0) {\r
- Node e = getNode(eliminatedNodeIds.pop());\r
- for (int j = 0; j < e.entryCount; j++) {\r
- add(e.entriesMinX[j], e.entriesMinY[j], e.entriesMaxX[j], e.entriesMaxY[j], e.ids[j], e.level); \r
- e.ids[j] = -1;\r
- }\r
- e.entryCount = 0;\r
- deletedNodeIds.push(e.nodeId);\r
- }\r
- }\r
-\r
- /**\r
- * Used by add(). Chooses a leaf to add the rectangle to.\r
- */\r
- private Node chooseNode(float minX, float minY, float maxX, float maxY, int level) {\r
- // CL1 [Initialize] Set N to be the root node\r
- Node n = getNode(rootNodeId);\r
- parents.reset();\r
- parentsEntry.reset();\r
- \r
- // CL2 [Leaf check] If N is a leaf, return N\r
- while (true) {\r
- if (n == null) {\r
- log.error("Could not get root node (" + rootNodeId + ")"); \r
- }\r
- \r
- if (n.level == level) {\r
- return n;\r
- }\r
- \r
- // CL3 [Choose subtree] If N is not at the desired level, let F be the entry in N \r
- // whose rectangle FI needs least enlargement to include EI. Resolve\r
- // ties by choosing the entry with the rectangle of smaller area.\r
- float leastEnlargement = Rectangle.enlargement(n.entriesMinX[0], n.entriesMinY[0], n.entriesMaxX[0], n.entriesMaxY[0],\r
- minX, minY, maxX, maxY);\r
- int index = 0; // index of rectangle in subtree\r
- for (int i = 1; i < n.entryCount; i++) {\r
- float tempMinX = n.entriesMinX[i];\r
- float tempMinY = n.entriesMinY[i];\r
- float tempMaxX = n.entriesMaxX[i];\r
- float tempMaxY = n.entriesMaxY[i];\r
- float tempEnlargement = Rectangle.enlargement(tempMinX, tempMinY, tempMaxX, tempMaxY, \r
- minX, minY, maxX, maxY);\r
- if ((tempEnlargement < leastEnlargement) ||\r
- ((tempEnlargement == leastEnlargement) && \r
- (Rectangle.area(tempMinX, tempMinY, tempMaxX, tempMaxY) < \r
- Rectangle.area(n.entriesMinX[index], n.entriesMinY[index], n.entriesMaxX[index], n.entriesMaxY[index])))) {\r
- index = i;\r
- leastEnlargement = tempEnlargement;\r
- }\r
- }\r
- \r
- parents.push(n.nodeId);\r
- parentsEntry.push(index);\r
- \r
- // CL4 [Descend until a leaf is reached] Set N to be the child node \r
- // pointed to by Fp and repeat from CL2\r
- n = getNode(n.ids[index]);\r
- }\r
- }\r
- \r
- /**\r
- * Ascend from a leaf node L to the root, adjusting covering rectangles and\r
- * propagating node splits as necessary.\r
- */\r
- private Node adjustTree(Node n, Node nn) {\r
- // AT1 [Initialize] Set N=L. If L was split previously, set NN to be \r
- // the resulting second node.\r
- \r
- // AT2 [Check if done] If N is the root, stop\r
- while (n.level != treeHeight) {\r
- \r
- // AT3 [Adjust covering rectangle in parent entry] Let P be the parent \r
- // node of N, and let En be N's entry in P. Adjust EnI so that it tightly\r
- // encloses all entry rectangles in N.\r
- Node parent = getNode(parents.pop());\r
- int entry = parentsEntry.pop(); \r
- \r
- if (parent.ids[entry] != n.nodeId) {\r
- log.error("Error: entry " + entry + " in node " + \r
- parent.nodeId + " should point to node " + \r
- n.nodeId + "; actually points to node " + parent.ids[entry]);\r
- }\r
- \r
- if (parent.entriesMinX[entry] != n.mbrMinX ||\r
- parent.entriesMinY[entry] != n.mbrMinY ||\r
- parent.entriesMaxX[entry] != n.mbrMaxX ||\r
- parent.entriesMaxY[entry] != n.mbrMaxY) {\r
- \r
- parent.entriesMinX[entry] = n.mbrMinX;\r
- parent.entriesMinY[entry] = n.mbrMinY;\r
- parent.entriesMaxX[entry] = n.mbrMaxX;\r
- parent.entriesMaxY[entry] = n.mbrMaxY;\r
-\r
- parent.recalculateMBR();\r
- }\r
- \r
- // AT4 [Propagate node split upward] If N has a partner NN resulting from \r
- // an earlier split, create a new entry Enn with Ennp pointing to NN and \r
- // Enni enclosing all rectangles in NN. Add Enn to P if there is room. \r
- // Otherwise, invoke splitNode to produce P and PP containing Enn and\r
- // all P's old entries.\r
- Node newNode = null;\r
- if (nn != null) {\r
- if (parent.entryCount < maxNodeEntries) {\r
- parent.addEntry(nn.mbrMinX, nn.mbrMinY, nn.mbrMaxX, nn.mbrMaxY, nn.nodeId);\r
- } else {\r
- newNode = splitNode(parent, nn.mbrMinX, nn.mbrMinY, nn.mbrMaxX, nn.mbrMaxY, nn.nodeId);\r
- }\r
- }\r
- \r
- // AT5 [Move up to next level] Set N = P and set NN = PP if a split \r
- // occurred. Repeat from AT2\r
- n = parent;\r
- nn = newNode;\r
- \r
- parent = null;\r
- newNode = null;\r
- }\r
- \r
- return nn;\r
- }\r
- \r
- \r
- /**\r
- * Check the consistency of the tree.\r
- * \r
- * @return false if an inconsistency is detected, true otherwise.\r
- */\r
- public boolean checkConsistency() {\r
- return checkConsistency(rootNodeId, treeHeight, null);\r
- }\r
- \r
- private boolean checkConsistency(int nodeId, int expectedLevel, Rectangle expectedMBR) {\r
- // go through the tree, and check that the internal data structures of \r
- // the tree are not corrupted. \r
- Node n = getNode(nodeId);\r
- \r
- if (n == null) {\r
- log.error("Error: Could not read node " + nodeId);\r
- return false;\r
- }\r
- \r
- // if tree is empty, then there should be exactly one node, at level 1\r
- // TODO: also check the MBR is as for a new node\r
- if (nodeId == rootNodeId && size() == 0) {\r
- if (n.level != 1) {\r
- log.error("Error: tree is empty but root node is not at level 1");\r
- return false;\r
- }\r
- }\r
- \r
- if (n.level != expectedLevel) {\r
- log.error("Error: Node " + nodeId + ", expected level " + expectedLevel + ", actual level " + n.level);\r
- return false;\r
- }\r
- \r
- Rectangle calculatedMBR = calculateMBR(n);\r
- Rectangle actualMBR = new Rectangle();\r
- actualMBR.minX = n.mbrMinX;\r
- actualMBR.minY = n.mbrMinY;\r
- actualMBR.maxX = n.mbrMaxX;\r
- actualMBR.maxY = n.mbrMaxY;\r
- if (!actualMBR.equals(calculatedMBR)) {\r
- log.error("Error: Node " + nodeId + ", calculated MBR does not equal stored MBR");\r
- if (actualMBR.minX != n.mbrMinX) log.error(" actualMinX=" + actualMBR.minX + ", calc=" + calculatedMBR.minX);\r
- if (actualMBR.minY != n.mbrMinY) log.error(" actualMinY=" + actualMBR.minY + ", calc=" + calculatedMBR.minY);\r
- if (actualMBR.maxX != n.mbrMaxX) log.error(" actualMaxX=" + actualMBR.maxX + ", calc=" + calculatedMBR.maxX);\r
- if (actualMBR.maxY != n.mbrMaxY) log.error(" actualMaxY=" + actualMBR.maxY + ", calc=" + calculatedMBR.maxY);\r
- return false;\r
- }\r
- \r
- if (expectedMBR != null && !actualMBR.equals(expectedMBR)) {\r
- log.error("Error: Node " + nodeId + ", expected MBR (from parent) does not equal stored MBR");\r
- return false;\r
- }\r
- \r
- // Check for corruption where a parent entry is the same object as the child MBR\r
- if (expectedMBR != null && actualMBR.sameObject(expectedMBR)) {\r
- log.error("Error: Node " + nodeId + " MBR using same rectangle object as parent's entry");\r
- return false;\r
- }\r
- \r
- for (int i = 0; i < n.entryCount; i++) {\r
- if (n.ids[i] == -1) {\r
- log.error("Error: Node " + nodeId + ", Entry " + i + " is null");\r
- return false;\r
- } \r
- \r
- if (n.level > 1) { // if not a leaf\r
- if (!checkConsistency(n.ids[i], n.level - 1, new Rectangle(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i]))) {\r
- return false;\r
- }\r
- } \r
- }\r
- return true;\r
- }\r
- \r
- /**\r
- * Given a node object, calculate the node MBR from it's entries.\r
- * Used in consistency checking\r
- */\r
- private Rectangle calculateMBR(Node n) {\r
- Rectangle mbr = new Rectangle();\r
- \r
- for (int i = 0; i < n.entryCount; i++) {\r
- if (n.entriesMinX[i] < mbr.minX) mbr.minX = n.entriesMinX[i];\r
- if (n.entriesMinY[i] < mbr.minY) mbr.minY = n.entriesMinY[i];\r
- if (n.entriesMaxX[i] > mbr.maxX) mbr.maxX = n.entriesMaxX[i];\r
- if (n.entriesMaxY[i] > mbr.maxY) mbr.maxY = n.entriesMaxY[i];\r
- }\r
- return mbr; \r
- }\r
-}\r
+// RTree.java
+// Java Spatial Index Library
+// Copyright (C) 2002-2005 Infomatiq Limited
+// Copyright (C) 2008-2010 aled@sourceforge.net
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public
+// License along with this library; if not, write to the Free Software
+// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+package com.infomatiq.jsi.rtree;
+
+import gnu.trove.TIntArrayList;
+import gnu.trove.TIntObjectHashMap;
+import gnu.trove.TIntProcedure;
+import gnu.trove.TIntStack;
+
+import java.util.Properties;
+
+import com.infomatiq.jsi.Point;
+import com.infomatiq.jsi.Rectangle;
+import com.infomatiq.jsi.PriorityQueue;
+import com.infomatiq.jsi.SpatialIndex;
+
+/**
+ * Stub replacement for org.apache.log4j.Logger to prevent dependency on log4j.
+ *
+ * @author Tuukka Lehtonen
+ */
+class Logger {
+ String name;
+
+ public Logger(String name) {
+ this.name = name;
+ }
+
+ public static Logger getLogger(String name) {
+ return new Logger(name);
+ }
+
+ public void warn(String string) {
+ //System.out.println(name + ": WARN " + string);
+ }
+
+ public boolean isDebugEnabled() {
+ return false;
+ }
+
+ public void debug(String string) {
+ //System.out.println(name + ": DEBUG " + string);
+ }
+
+ public void error(String string) {
+ System.out.println(name + ": ERROR " + string);
+ }
+}
+
+/**
+ * <p>This is a lightweight RTree implementation, specifically designed
+ * for the following features (in order of importance):
+ * <ul>
+ * <li>Fast intersection query performance. To achieve this, the RTree
+ * uses only main memory to store entries. Obviously this will only improve
+ * performance if there is enough physical memory to avoid paging.</li>
+ * <li>Low memory requirements.</li>
+ * <li>Fast add performance.</li>
+ * </ul></p>
+ *
+ * <p>The main reason for the high speed of this RTree implementation is the
+ * avoidance of the creation of unnecessary objects, mainly achieved by using
+ * primitive collections from the trove4j library.</p>
+ *
+ * @author aled@sourceforge.net
+ * @version 1.0b8
+ */
+public class RTree implements SpatialIndex {
+ private static final Logger log = Logger.getLogger(RTree.class.getName());
+ private static final Logger deleteLog = Logger.getLogger(RTree.class.getName() + "-delete");
+
+ private static final String version = "1.0b8";
+
+ // parameters of the tree
+ private final static int DEFAULT_MAX_NODE_ENTRIES = 10;
+ int maxNodeEntries;
+ int minNodeEntries;
+
+ // map of nodeId -> node object
+ // TODO eliminate this map - it should not be needed. Nodes
+ // can be found by traversing the tree.
+ private TIntObjectHashMap<Node> nodeMap = new TIntObjectHashMap<Node>();
+
+ // internal consistency checking - set to true if debugging tree corruption
+ private final static boolean INTERNAL_CONSISTENCY_CHECKING = false;
+
+ // used to mark the status of entries during a node split
+ private final static int ENTRY_STATUS_ASSIGNED = 0;
+ private final static int ENTRY_STATUS_UNASSIGNED = 1;
+ private byte[] entryStatus = null;
+ private byte[] initialEntryStatus = null;
+
+ // stacks used to store nodeId and entry index of each node
+ // from the root down to the leaf. Enables fast lookup
+ // of nodes when a split is propagated up the tree.
+ private TIntStack parents = new TIntStack();
+ private TIntStack parentsEntry = new TIntStack();
+
+ // initialisation
+ private int treeHeight = 1; // leaves are always level 1
+ private int rootNodeId = 0;
+ private int size = 0;
+
+ // Enables creation of new nodes
+ private int highestUsedNodeId = rootNodeId;
+
+ // Deleted node objects are retained in the nodeMap,
+ // so that they can be reused. Store the IDs of nodes
+ // which can be reused.
+ private TIntStack deletedNodeIds = new TIntStack();
+
+ // List of nearest rectangles. Use a member variable to
+ // avoid recreating the object each time nearest() is called.
+ private TIntArrayList nearestIds = new TIntArrayList();
+ private TIntArrayList savedValues = new TIntArrayList();
+ private float savedPriority = 0;
+
+ // List of nearestN rectangles
+ private SortedList nearestNIds = new SortedList();
+
+ // List of nearestN rectanges, used in the alternative nearestN implementation.
+ private PriorityQueue distanceQueue =
+ new PriorityQueue(PriorityQueue.SORT_ORDER_ASCENDING);
+
+ /**
+ * Constructor. Use init() method to initialize parameters of the RTree.
+ */
+ public RTree() {
+ return; // NOP
+ }
+
+ //-------------------------------------------------------------------------
+ // public implementation of SpatialIndex interface:
+ // init(Properties)
+ // add(Rectangle, int)
+ // delete(Rectangle, int)
+ // nearest(Point, TIntProcedure, float)
+ // intersects(Rectangle, TIntProcedure)
+ // contains(Rectangle, TIntProcedure)
+ // size()
+ //-------------------------------------------------------------------------
+ /**
+ * <p>Initialize implementation dependent properties of the RTree.
+ * Currently implemented properties are:
+ * <ul>
+ * <li>MaxNodeEntries</li> This specifies the maximum number of entries
+ * in a node. The default value is 10, which is used if the property is
+ * not specified, or is less than 2.
+ * <li>MinNodeEntries</li> This specifies the minimum number of entries
+ * in a node. The default value is half of the MaxNodeEntries value (rounded
+ * down), which is used if the property is not specified or is less than 1.
+ * </ul></p>
+ *
+ * @see com.infomatiq.jsi.SpatialIndex#init(Properties)
+ */
+ public void init(Properties props) {
+ if (props == null) {
+ // use sensible defaults if null is passed in.
+ maxNodeEntries = 50;
+ minNodeEntries = 20;
+ } else {
+ maxNodeEntries = Integer.parseInt(props.getProperty("MaxNodeEntries", "0"));
+ minNodeEntries = Integer.parseInt(props.getProperty("MinNodeEntries", "0"));
+
+ // Obviously a node with less than 2 entries cannot be split.
+ // The node splitting algorithm will work with only 2 entries
+ // per node, but will be inefficient.
+ if (maxNodeEntries < 2) {
+ log.warn("Invalid MaxNodeEntries = " + maxNodeEntries + " Resetting to default value of " + DEFAULT_MAX_NODE_ENTRIES);
+ maxNodeEntries = DEFAULT_MAX_NODE_ENTRIES;
+ }
+
+ // The MinNodeEntries must be less than or equal to (int) (MaxNodeEntries / 2)
+ if (minNodeEntries < 1 || minNodeEntries > maxNodeEntries / 2) {
+ log.warn("MinNodeEntries must be between 1 and MaxNodeEntries / 2");
+ minNodeEntries = maxNodeEntries / 2;
+ }
+ }
+
+ entryStatus = new byte[maxNodeEntries];
+ initialEntryStatus = new byte[maxNodeEntries];
+
+ for (int i = 0; i < maxNodeEntries; i++) {
+ initialEntryStatus[i] = ENTRY_STATUS_UNASSIGNED;
+ }
+
+ Node root = new Node(rootNodeId, 1, maxNodeEntries);
+ nodeMap.put(rootNodeId, root);
+
+ log.debug("init() " + " MaxNodeEntries = " + maxNodeEntries + ", MinNodeEntries = " + minNodeEntries);
+ }
+
+ /**
+ * @see com.infomatiq.jsi.SpatialIndex#add(Rectangle, int)
+ */
+ public void add(Rectangle r, int id) {
+ if (log.isDebugEnabled()) {
+ log.debug("Adding rectangle " + r + ", id " + id);
+ }
+
+ add(r.minX, r.minY, r.maxX, r.maxY, id, 1);
+
+ size++;
+
+ if (INTERNAL_CONSISTENCY_CHECKING) {
+ checkConsistency();
+ }
+ }
+
+ /**
+ * Adds a new entry at a specified level in the tree
+ */
+ private void add(float minX, float minY, float maxX, float maxY, int id, int level) {
+ // I1 [Find position for new record] Invoke ChooseLeaf to select a
+ // leaf node L in which to place r
+ Node n = chooseNode(minX, minY, maxX, maxY, level);
+ Node newLeaf = null;
+
+ // I2 [Add record to leaf node] If L has room for another entry,
+ // install E. Otherwise invoke SplitNode to obtain L and LL containing
+ // E and all the old entries of L
+ if (n.entryCount < maxNodeEntries) {
+ n.addEntry(minX, minY, maxX, maxY, id);
+ } else {
+ newLeaf = splitNode(n, minX, minY, maxX, maxY, id);
+ }
+
+ // I3 [Propagate changes upwards] Invoke AdjustTree on L, also passing LL
+ // if a split was performed
+ Node newNode = adjustTree(n, newLeaf);
+
+ // I4 [Grow tree taller] If node split propagation caused the root to
+ // split, create a new root whose children are the two resulting nodes.
+ if (newNode != null) {
+ int oldRootNodeId = rootNodeId;
+ Node oldRoot = getNode(oldRootNodeId);
+
+ rootNodeId = getNextNodeId();
+ treeHeight++;
+ Node root = new Node(rootNodeId, treeHeight, maxNodeEntries);
+ root.addEntry(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY, newNode.nodeId);
+ root.addEntry(oldRoot.mbrMinX, oldRoot.mbrMinY, oldRoot.mbrMaxX, oldRoot.mbrMaxY, oldRoot.nodeId);
+ nodeMap.put(rootNodeId, root);
+ }
+ }
+
+ /**
+ * @see com.infomatiq.jsi.SpatialIndex#delete(Rectangle, int)
+ */
+ public boolean delete(Rectangle r, int id) {
+ // FindLeaf algorithm inlined here. Note the "official" algorithm
+ // searches all overlapping entries. This seems inefficient to me,
+ // as an entry is only worth searching if it contains (NOT overlaps)
+ // the rectangle we are searching for.
+ //
+ // Also the algorithm has been changed so that it is not recursive.
+
+ // FL1 [Search subtrees] If root is not a leaf, check each entry
+ // to determine if it contains r. For each entry found, invoke
+ // findLeaf on the node pointed to by the entry, until r is found or
+ // all entries have been checked.
+ parents.reset();
+ parents.push(rootNodeId);
+
+ parentsEntry.reset();
+ parentsEntry.push(-1);
+ Node n = null;
+ int foundIndex = -1; // index of entry to be deleted in leaf
+
+ while (foundIndex == -1 && parents.size() > 0) {
+ n = getNode(parents.peek());
+ int startIndex = parentsEntry.peek() + 1;
+
+ if (!n.isLeaf()) {
+ deleteLog.debug("searching node " + n.nodeId + ", from index " + startIndex);
+ boolean contains = false;
+ for (int i = startIndex; i < n.entryCount; i++) {
+ if (Rectangle.contains(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i],
+ r.minX, r.minY, r.maxX, r.maxY)) {
+ parents.push(n.ids[i]);
+ parentsEntry.pop();
+ parentsEntry.push(i); // this becomes the start index when the child has been searched
+ parentsEntry.push(-1);
+ contains = true;
+ break; // ie go to next iteration of while()
+ }
+ }
+ if (contains) {
+ continue;
+ }
+ } else {
+ foundIndex = n.findEntry(r.minX, r.minY, r.maxX, r.maxY, id);
+ }
+
+ parents.pop();
+ parentsEntry.pop();
+ } // while not found
+
+ if (foundIndex != -1) {
+ n.deleteEntry(foundIndex);
+ condenseTree(n);
+ size--;
+ }
+
+ // shrink the tree if possible (i.e. if root node has exactly one entry,and that
+ // entry is not a leaf node, delete the root (it's entry becomes the new root)
+ Node root = getNode(rootNodeId);
+ while (root.entryCount == 1 && treeHeight > 1)
+ {
+ deletedNodeIds.push(rootNodeId);
+ root.entryCount = 0;
+ rootNodeId = root.ids[0];
+ treeHeight--;
+ root = getNode(rootNodeId);
+ }
+
+ // if the tree is now empty, then set the MBR of the root node back to it's original state
+ // (this is only needed when the tree is empty, as this is the only state where an empty node
+ // is not eliminated)
+ if (size == 0) {
+ root.mbrMinX = Float.MAX_VALUE;
+ root.mbrMinY = Float.MAX_VALUE;
+ root.mbrMaxX = -Float.MAX_VALUE;
+ root.mbrMaxY = -Float.MAX_VALUE;
+ }
+
+ if (INTERNAL_CONSISTENCY_CHECKING) {
+ checkConsistency();
+ }
+
+ return (foundIndex != -1);
+ }
+
+ /**
+ * @see com.infomatiq.jsi.SpatialIndex#nearest(Point, TIntProcedure, float)
+ */
+ public void nearest(Point p, TIntProcedure v, float furthestDistance) {
+ Node rootNode = getNode(rootNodeId);
+
+ float furthestDistanceSq = furthestDistance * furthestDistance;
+ nearest(p, rootNode, furthestDistanceSq);
+
+ nearestIds.forEach(v);
+ nearestIds.reset();
+ }
+
+ private void createNearestNDistanceQueue(Point p, int count, float furthestDistance) {
+ distanceQueue.reset();
+ distanceQueue.setSortOrder(PriorityQueue.SORT_ORDER_DESCENDING);
+
+ // return immediately if given an invalid "count" parameter
+ if (count <= 0) {
+ return;
+ }
+
+ parents.reset();
+ parents.push(rootNodeId);
+
+ parentsEntry.reset();
+ parentsEntry.push(-1);
+
+ // TODO: possible shortcut here - could test for intersection with the
+ // MBR of the root node. If no intersection, return immediately.
+
+ float furthestDistanceSq = furthestDistance * furthestDistance;
+
+ while (parents.size() > 0) {
+ Node n = getNode(parents.peek());
+ int startIndex = parentsEntry.peek() + 1;
+
+ if (!n.isLeaf()) {
+ // go through every entry in the index node to check
+ // if it could contain an entry closer than the farthest entry
+ // currently stored.
+ boolean near = false;
+ for (int i = startIndex; i < n.entryCount; i++) {
+ if (Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i],
+ n.entriesMaxX[i], n.entriesMaxY[i],
+ p.x, p.y) <= furthestDistanceSq) {
+ parents.push(n.ids[i]);
+ parentsEntry.pop();
+ parentsEntry.push(i); // this becomes the start index when the child has been searched
+ parentsEntry.push(-1);
+ near = true;
+ break; // ie go to next iteration of while()
+ }
+ }
+ if (near) {
+ continue;
+ }
+ } else {
+ // go through every entry in the leaf to check if
+ // it is currently one of the nearest N entries.
+ for (int i = 0; i < n.entryCount; i++) {
+ float entryDistanceSq = Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i],
+ n.entriesMaxX[i], n.entriesMaxY[i],
+ p.x, p.y);
+ int entryId = n.ids[i];
+
+ if (entryDistanceSq <= furthestDistanceSq) {
+ distanceQueue.insert(entryId, entryDistanceSq);
+
+ while (distanceQueue.size() > count) {
+ // normal case - we can simply remove the lowest priority (highest distance) entry
+ int value = distanceQueue.getValue();
+ float distanceSq = distanceQueue.getPriority();
+ distanceQueue.pop();
+
+ // rare case - multiple items of the same priority (distance)
+ if (distanceSq == distanceQueue.getPriority()) {
+ savedValues.add(value);
+ savedPriority = distanceSq;
+ } else {
+ savedValues.reset();
+ }
+ }
+
+ // if the saved values have the same distance as the
+ // next one in the tree, add them back in.
+ if (savedValues.size() > 0 && savedPriority == distanceQueue.getPriority()) {
+ for (int svi = 0; svi < savedValues.size(); svi++) {
+ distanceQueue.insert(savedValues.get(svi), savedPriority);
+ }
+ savedValues.reset();
+ }
+
+ // narrow the search, if we have already found N items
+ if (distanceQueue.getPriority() < furthestDistanceSq && distanceQueue.size() >= count) {
+ furthestDistanceSq = distanceQueue.getPriority();
+ }
+ }
+ }
+ }
+ parents.pop();
+ parentsEntry.pop();
+ }
+ }
+
+ /**
+ * @see com.infomatiq.jsi.SpatialIndex#nearestNUnsorted(Point, TIntProcedure, int, float)
+ */
+ public void nearestNUnsorted(Point p, TIntProcedure v, int count, float furthestDistance) {
+ // This implementation is designed to give good performance
+ // where
+ // o N is high (100+)
+ // o The results do not need to be sorted by distance.
+ //
+ // Uses a priority queue as the underlying data structure.
+ //
+ // The behaviour of this algorithm has been carefully designed to
+ // return exactly the same items as the the original version (nearestN_orig), in particular,
+ // more than N items will be returned if items N and N+x have the
+ // same priority.
+ createNearestNDistanceQueue(p, count, furthestDistance);
+
+ while (distanceQueue.size() > 0) {
+ v.execute(distanceQueue.getValue());
+ distanceQueue.pop();
+ }
+ }
+
+ /**
+ * @see com.infomatiq.jsi.SpatialIndex#nearestN(Point, TIntProcedure, int, float)
+ */
+ public void nearestN(Point p, TIntProcedure v, int count, float furthestDistance) {
+ createNearestNDistanceQueue(p, count, furthestDistance);
+
+ distanceQueue.setSortOrder(PriorityQueue.SORT_ORDER_ASCENDING);
+
+ while (distanceQueue.size() > 0) {
+ v.execute(distanceQueue.getValue());
+ distanceQueue.pop();
+ }
+ }
+
+ /**
+ * @see com.infomatiq.jsi.SpatialIndex#nearestN(Point, TIntProcedure, int, float)
+ * @deprecated Use new NearestN or NearestNUnsorted instead.
+ *
+ * This implementation of nearestN is only suitable for small values of N (ie less than 10).
+ */
+ public void nearestN_orig(Point p, TIntProcedure v, int count, float furthestDistance) {
+ // return immediately if given an invalid "count" parameter
+ if (count <= 0) {
+ return;
+ }
+
+ parents.reset();
+ parents.push(rootNodeId);
+
+ parentsEntry.reset();
+ parentsEntry.push(-1);
+
+ nearestNIds.init(count);
+
+ // TODO: possible shortcut here - could test for intersection with the
+ // MBR of the root node. If no intersection, return immediately.
+
+ float furthestDistanceSq = furthestDistance * furthestDistance;
+
+ while (parents.size() > 0) {
+ Node n = getNode(parents.peek());
+ int startIndex = parentsEntry.peek() + 1;
+
+ if (!n.isLeaf()) {
+ // go through every entry in the index node to check
+ // if it could contain an entry closer than the farthest entry
+ // currently stored.
+ boolean near = false;
+ for (int i = startIndex; i < n.entryCount; i++) {
+ if (Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i],
+ n.entriesMaxX[i], n.entriesMaxY[i],
+ p.x, p.y) <= furthestDistanceSq) {
+ parents.push(n.ids[i]);
+ parentsEntry.pop();
+ parentsEntry.push(i); // this becomes the start index when the child has been searched
+ parentsEntry.push(-1);
+ near = true;
+ break; // ie go to next iteration of while()
+ }
+ }
+ if (near) {
+ continue;
+ }
+ } else {
+ // go through every entry in the leaf to check if
+ // it is currently one of the nearest N entries.
+ for (int i = 0; i < n.entryCount; i++) {
+ float entryDistanceSq = Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i],
+ n.entriesMaxX[i], n.entriesMaxY[i],
+ p.x, p.y);
+ int entryId = n.ids[i];
+
+ if (entryDistanceSq <= furthestDistanceSq) {
+ // add the new entry to the tree. Note that the higher the distance, the lower the priority
+ nearestNIds.add(entryId, -entryDistanceSq);
+
+ float tempFurthestDistanceSq = -nearestNIds.getLowestPriority();
+ if (tempFurthestDistanceSq < furthestDistanceSq) {
+ furthestDistanceSq = tempFurthestDistanceSq;
+ }
+ }
+ }
+ }
+ parents.pop();
+ parentsEntry.pop();
+ }
+
+ nearestNIds.forEachId(v);
+ }
+
+ /**
+ * @see com.infomatiq.jsi.SpatialIndex#intersects(Rectangle, TIntProcedure)
+ */
+ public void intersects(Rectangle r, TIntProcedure v) {
+ Node rootNode = getNode(rootNodeId);
+ intersects(r, v, rootNode);
+ }
+
+ /**
+ * @see com.infomatiq.jsi.SpatialIndex#contains(Rectangle, TIntProcedure)
+ */
+ public void contains(Rectangle r, TIntProcedure v) {
+ // find all rectangles in the tree that are contained by the passed rectangle
+ // written to be non-recursive (should model other searches on this?)
+
+ parents.reset();
+ parents.push(rootNodeId);
+
+ parentsEntry.reset();
+ parentsEntry.push(-1);
+
+ // TODO: possible shortcut here - could test for intersection with the
+ // MBR of the root node. If no intersection, return immediately.
+
+ while (parents.size() > 0) {
+ Node n = getNode(parents.peek());
+ int startIndex = parentsEntry.peek() + 1;
+
+ if (!n.isLeaf()) {
+ // go through every entry in the index node to check
+ // if it intersects the passed rectangle. If so, it
+ // could contain entries that are contained.
+ boolean intersects = false;
+ for (int i = startIndex; i < n.entryCount; i++) {
+ if (Rectangle.intersects(r.minX, r.minY, r.maxX, r.maxY,
+ n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i])) {
+ parents.push(n.ids[i]);
+ parentsEntry.pop();
+ parentsEntry.push(i); // this becomes the start index when the child has been searched
+ parentsEntry.push(-1);
+ intersects = true;
+ break; // ie go to next iteration of while()
+ }
+ }
+ if (intersects) {
+ continue;
+ }
+ } else {
+ // go through every entry in the leaf to check if
+ // it is contained by the passed rectangle
+ for (int i = 0; i < n.entryCount; i++) {
+ if (Rectangle.contains(r.minX, r.minY, r.maxX, r.maxY,
+ n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i])) {
+ if (!v.execute(n.ids[i])) {
+ return;
+ }
+ }
+ }
+ }
+ parents.pop();
+ parentsEntry.pop();
+ }
+ }
+
+ /**
+ * @see com.infomatiq.jsi.SpatialIndex#size()
+ */
+ public int size() {
+ return size;
+ }
+
+ /**
+ * @see com.infomatiq.jsi.SpatialIndex#getBounds()
+ */
+ public Rectangle getBounds() {
+ Rectangle bounds = null;
+
+ Node n = getNode(getRootNodeId());
+ if (n != null && n.entryCount > 0) {
+ bounds = new Rectangle();
+ bounds.minX = n.mbrMinX;
+ bounds.minY = n.mbrMinY;
+ bounds.maxX = n.mbrMaxX;
+ bounds.maxY = n.mbrMaxY;
+ }
+ return bounds;
+ }
+
+ /**
+ * @see com.infomatiq.jsi.SpatialIndex#getVersion()
+ */
+ public String getVersion() {
+ return "RTree-" + version;
+ }
+ //-------------------------------------------------------------------------
+ // end of SpatialIndex methods
+ //-------------------------------------------------------------------------
+
+ /**
+ * Get the next available node ID. Reuse deleted node IDs if
+ * possible
+ */
+ private int getNextNodeId() {
+ int nextNodeId = 0;
+ if (deletedNodeIds.size() > 0) {
+ nextNodeId = deletedNodeIds.pop();
+ } else {
+ nextNodeId = 1 + highestUsedNodeId++;
+ }
+ return nextNodeId;
+ }
+
+ /**
+ * Get a node object, given the ID of the node.
+ */
+ public Node getNode(int id) {
+ return nodeMap.get(id);
+ }
+
+ /**
+ * Get the highest used node ID
+ */
+ public int getHighestUsedNodeId() {
+ return highestUsedNodeId;
+ }
+
+ /**
+ * Get the root node ID
+ */
+ public int getRootNodeId() {
+ return rootNodeId;
+ }
+
+ /**
+ * Split a node. Algorithm is taken pretty much verbatim from
+ * Guttman's original paper.
+ *
+ * @return new node object.
+ */
+ private Node splitNode(Node n, float newRectMinX, float newRectMinY, float newRectMaxX, float newRectMaxY, int newId) {
+ // [Pick first entry for each group] Apply algorithm pickSeeds to
+ // choose two entries to be the first elements of the groups. Assign
+ // each to a group.
+
+ // debug code
+ float initialArea = 0;
+ if (log.isDebugEnabled()) {
+ float unionMinX = Math.min(n.mbrMinX, newRectMinX);
+ float unionMinY = Math.min(n.mbrMinY, newRectMinY);
+ float unionMaxX = Math.max(n.mbrMaxX, newRectMaxX);
+ float unionMaxY = Math.max(n.mbrMaxY, newRectMaxY);
+
+ initialArea = (unionMaxX - unionMinX) * (unionMaxY - unionMinY);
+ }
+
+ System.arraycopy(initialEntryStatus, 0, entryStatus, 0, maxNodeEntries);
+
+ Node newNode = null;
+ newNode = new Node(getNextNodeId(), n.level, maxNodeEntries);
+ nodeMap.put(newNode.nodeId, newNode);
+
+ pickSeeds(n, newRectMinX, newRectMinY, newRectMaxX, newRectMaxY, newId, newNode); // this also sets the entryCount to 1
+
+ // [Check if done] If all entries have been assigned, stop. If one
+ // group has so few entries that all the rest must be assigned to it in
+ // order for it to have the minimum number m, assign them and stop.
+ while (n.entryCount + newNode.entryCount < maxNodeEntries + 1) {
+ if (maxNodeEntries + 1 - newNode.entryCount == minNodeEntries) {
+ // assign all remaining entries to original node
+ for (int i = 0; i < maxNodeEntries; i++) {
+ if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED) {
+ entryStatus[i] = ENTRY_STATUS_ASSIGNED;
+
+ if (n.entriesMinX[i] < n.mbrMinX) n.mbrMinX = n.entriesMinX[i];
+ if (n.entriesMinY[i] < n.mbrMinY) n.mbrMinY = n.entriesMinY[i];
+ if (n.entriesMaxX[i] > n.mbrMaxX) n.mbrMaxX = n.entriesMaxX[i];
+ if (n.entriesMaxY[i] > n.mbrMaxY) n.mbrMaxY = n.entriesMaxY[i];
+
+ n.entryCount++;
+ }
+ }
+ break;
+ }
+ if (maxNodeEntries + 1 - n.entryCount == minNodeEntries) {
+ // assign all remaining entries to new node
+ for (int i = 0; i < maxNodeEntries; i++) {
+ if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED) {
+ entryStatus[i] = ENTRY_STATUS_ASSIGNED;
+ newNode.addEntry(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i], n.ids[i]);
+ n.ids[i] = -1; // an id of -1 indicates the entry is not in use
+ }
+ }
+ break;
+ }
+
+ // [Select entry to assign] Invoke algorithm pickNext to choose the
+ // next entry to assign. Add it to the group whose covering rectangle
+ // will have to be enlarged least to accommodate it. Resolve ties
+ // by adding the entry to the group with smaller area, then to the
+ // the one with fewer entries, then to either. Repeat from S2
+ pickNext(n, newNode);
+ }
+
+ n.reorganize(this);
+
+ // check that the MBR stored for each node is correct.
+ if (INTERNAL_CONSISTENCY_CHECKING) {
+ Rectangle nMBR = new Rectangle(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY);
+ if (!nMBR.equals(calculateMBR(n))) {
+ log.error("Error: splitNode old node MBR wrong");
+ }
+ Rectangle newNodeMBR = new Rectangle(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY);
+ if (!newNodeMBR.equals(calculateMBR(newNode))) {
+ log.error("Error: splitNode new node MBR wrong");
+ }
+ }
+
+ // debug code
+ if (log.isDebugEnabled()) {
+ float newArea = Rectangle.area(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY) +
+ Rectangle.area(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY);
+ float percentageIncrease = (100 * (newArea - initialArea)) / initialArea;
+ log.debug("Node " + n.nodeId + " split. New area increased by " + percentageIncrease + "%");
+ }
+
+ return newNode;
+ }
+
+ /**
+ * Pick the seeds used to split a node.
+ * Select two entries to be the first elements of the groups
+ */
+ private void pickSeeds(Node n, float newRectMinX, float newRectMinY, float newRectMaxX, float newRectMaxY, int newId, Node newNode) {
+ // Find extreme rectangles along all dimension. Along each dimension,
+ // find the entry whose rectangle has the highest low side, and the one
+ // with the lowest high side. Record the separation.
+ float maxNormalizedSeparation = -1; // initialize to -1 so that even overlapping rectangles will be considered for the seeds
+ int highestLowIndex = -1;
+ int lowestHighIndex = -1;
+
+ // for the purposes of picking seeds, take the MBR of the node to include
+ // the new rectangle aswell.
+ if (newRectMinX < n.mbrMinX) n.mbrMinX = newRectMinX;
+ if (newRectMinY < n.mbrMinY) n.mbrMinY = newRectMinY;
+ if (newRectMaxX > n.mbrMaxX) n.mbrMaxX = newRectMaxX;
+ if (newRectMaxY > n.mbrMaxY) n.mbrMaxY = newRectMaxY;
+
+ float mbrLenX = n.mbrMaxX - n.mbrMinX;
+ float mbrLenY = n.mbrMaxY - n.mbrMinY;
+
+ if (log.isDebugEnabled()) {
+ log.debug("pickSeeds(): NodeId = " + n.nodeId);
+ }
+
+ float tempHighestLow = newRectMinX;
+ int tempHighestLowIndex = -1; // -1 indicates the new rectangle is the seed
+
+ float tempLowestHigh = newRectMaxX;
+ int tempLowestHighIndex = -1; // -1 indicates the new rectangle is the seed
+
+ for (int i = 0; i < n.entryCount; i++) {
+ float tempLow = n.entriesMinX[i];
+ if (tempLow >= tempHighestLow) {
+ tempHighestLow = tempLow;
+ tempHighestLowIndex = i;
+ } else { // ensure that the same index cannot be both lowestHigh and highestLow
+ float tempHigh = n.entriesMaxX[i];
+ if (tempHigh <= tempLowestHigh) {
+ tempLowestHigh = tempHigh;
+ tempLowestHighIndex = i;
+ }
+ }
+
+ // PS2 [Adjust for shape of the rectangle cluster] Normalize the separations
+ // by dividing by the widths of the entire set along the corresponding
+ // dimension
+ float normalizedSeparation = mbrLenX == 0 ? 1 : (tempHighestLow - tempLowestHigh) / mbrLenX;
+ if (normalizedSeparation > 1 || normalizedSeparation < -1) {
+ log.error("Invalid normalized separation X");
+ }
+
+ if (log.isDebugEnabled()) {
+ log.debug("Entry " + i + ", dimension X: HighestLow = " + tempHighestLow +
+ " (index " + tempHighestLowIndex + ")" + ", LowestHigh = " +
+ tempLowestHigh + " (index " + tempLowestHighIndex + ", NormalizedSeparation = " + normalizedSeparation);
+ }
+
+ // PS3 [Select the most extreme pair] Choose the pair with the greatest
+ // normalized separation along any dimension.
+ // Note that if negative it means the rectangles overlapped. However still include
+ // overlapping rectangles if that is the only choice available.
+ if (normalizedSeparation >= maxNormalizedSeparation) {
+ highestLowIndex = tempHighestLowIndex;
+ lowestHighIndex = tempLowestHighIndex;
+ maxNormalizedSeparation = normalizedSeparation;
+ }
+ }
+
+ // Repeat for the Y dimension
+ tempHighestLow = newRectMinY;
+ tempHighestLowIndex = -1; // -1 indicates the new rectangle is the seed
+
+ tempLowestHigh = newRectMaxY;
+ tempLowestHighIndex = -1; // -1 indicates the new rectangle is the seed
+
+ for (int i = 0; i < n.entryCount; i++) {
+ float tempLow = n.entriesMinY[i];
+ if (tempLow >= tempHighestLow) {
+ tempHighestLow = tempLow;
+ tempHighestLowIndex = i;
+ } else { // ensure that the same index cannot be both lowestHigh and highestLow
+ float tempHigh = n.entriesMaxY[i];
+ if (tempHigh <= tempLowestHigh) {
+ tempLowestHigh = tempHigh;
+ tempLowestHighIndex = i;
+ }
+ }
+
+ // PS2 [Adjust for shape of the rectangle cluster] Normalize the separations
+ // by dividing by the widths of the entire set along the corresponding
+ // dimension
+ float normalizedSeparation = mbrLenY == 0 ? 1 : (tempHighestLow - tempLowestHigh) / mbrLenY;
+ if (normalizedSeparation > 1 || normalizedSeparation < -1) {
+ log.error("Invalid normalized separation Y");
+ }
+
+ if (log.isDebugEnabled()) {
+ log.debug("Entry " + i + ", dimension Y: HighestLow = " + tempHighestLow +
+ " (index " + tempHighestLowIndex + ")" + ", LowestHigh = " +
+ tempLowestHigh + " (index " + tempLowestHighIndex + ", NormalizedSeparation = " + normalizedSeparation);
+ }
+
+ // PS3 [Select the most extreme pair] Choose the pair with the greatest
+ // normalized separation along any dimension.
+ // Note that if negative it means the rectangles overlapped. However still include
+ // overlapping rectangles if that is the only choice available.
+ if (normalizedSeparation >= maxNormalizedSeparation) {
+ highestLowIndex = tempHighestLowIndex;
+ lowestHighIndex = tempLowestHighIndex;
+ maxNormalizedSeparation = normalizedSeparation;
+ }
+ }
+
+ // At this point it is possible that the new rectangle is both highestLow and lowestHigh.
+ // This can happen if all rectangles in the node overlap the new rectangle.
+ // Resolve this by declaring that the highestLowIndex is the lowest Y and,
+ // the lowestHighIndex is the largest X (but always a different rectangle)
+ if (highestLowIndex == lowestHighIndex) {
+ highestLowIndex = -1;
+ float tempMinY = newRectMinY;
+ lowestHighIndex = 0;
+ float tempMaxX = n.entriesMaxX[0];
+
+ for (int i = 1; i < n.entryCount; i++) {
+ if (n.entriesMinY[i] < tempMinY) {
+ tempMinY = n.entriesMinY[i];
+ highestLowIndex = i;
+ }
+ else if (n.entriesMaxX[i] > tempMaxX) {
+ tempMaxX = n.entriesMaxX[i];
+ lowestHighIndex = i;
+ }
+ }
+ }
+
+ // highestLowIndex is the seed for the new node.
+ if (highestLowIndex == -1) {
+ newNode.addEntry(newRectMinX, newRectMinY, newRectMaxX, newRectMaxY, newId);
+ } else {
+ newNode.addEntry(n.entriesMinX[highestLowIndex], n.entriesMinY[highestLowIndex],
+ n.entriesMaxX[highestLowIndex], n.entriesMaxY[highestLowIndex],
+ n.ids[highestLowIndex]);
+ n.ids[highestLowIndex] = -1;
+
+ // move the new rectangle into the space vacated by the seed for the new node
+ n.entriesMinX[highestLowIndex] = newRectMinX;
+ n.entriesMinY[highestLowIndex] = newRectMinY;
+ n.entriesMaxX[highestLowIndex] = newRectMaxX;
+ n.entriesMaxY[highestLowIndex] = newRectMaxY;
+
+ n.ids[highestLowIndex] = newId;
+ }
+
+ // lowestHighIndex is the seed for the original node.
+ if (lowestHighIndex == -1) {
+ lowestHighIndex = highestLowIndex;
+ }
+
+ entryStatus[lowestHighIndex] = ENTRY_STATUS_ASSIGNED;
+ n.entryCount = 1;
+ n.mbrMinX = n.entriesMinX[lowestHighIndex];
+ n.mbrMinY = n.entriesMinY[lowestHighIndex];
+ n.mbrMaxX = n.entriesMaxX[lowestHighIndex];
+ n.mbrMaxY = n.entriesMaxY[lowestHighIndex];
+ }
+
+ /**
+ * Pick the next entry to be assigned to a group during a node split.
+ *
+ * [Determine cost of putting each entry in each group] For each
+ * entry not yet in a group, calculate the area increase required
+ * in the covering rectangles of each group
+ */
+ private int pickNext(Node n, Node newNode) {
+ float maxDifference = Float.NEGATIVE_INFINITY;
+ int next = 0;
+ int nextGroup = 0;
+
+ maxDifference = Float.NEGATIVE_INFINITY;
+
+ if (log.isDebugEnabled()) {
+ log.debug("pickNext()");
+ }
+
+ for (int i = 0; i < maxNodeEntries; i++) {
+ if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED) {
+
+ if (n.ids[i] == -1) {
+ log.error("Error: Node " + n.nodeId + ", entry " + i + " is null");
+ }
+
+ float nIncrease = Rectangle.enlargement(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY,
+ n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i]);
+ float newNodeIncrease = Rectangle.enlargement(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY,
+ n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i]);
+
+ float difference = Math.abs(nIncrease - newNodeIncrease);
+
+ if (difference > maxDifference) {
+ next = i;
+
+ if (nIncrease < newNodeIncrease) {
+ nextGroup = 0;
+ } else if (newNodeIncrease < nIncrease) {
+ nextGroup = 1;
+ } else if (Rectangle.area(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY) < Rectangle.area(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY)) {
+ nextGroup = 0;
+ } else if (Rectangle.area(newNode.mbrMinX, newNode.mbrMinY, newNode.mbrMaxX, newNode.mbrMaxY) < Rectangle.area(n.mbrMinX, n.mbrMinY, n.mbrMaxX, n.mbrMaxY)) {
+ nextGroup = 1;
+ } else if (newNode.entryCount < maxNodeEntries / 2) {
+ nextGroup = 0;
+ } else {
+ nextGroup = 1;
+ }
+ maxDifference = difference;
+ }
+ if (log.isDebugEnabled()) {
+ log.debug("Entry " + i + " group0 increase = " + nIncrease + ", group1 increase = " + newNodeIncrease +
+ ", diff = " + difference + ", MaxDiff = " + maxDifference + " (entry " + next + ")");
+ }
+ }
+ }
+
+ entryStatus[next] = ENTRY_STATUS_ASSIGNED;
+
+ if (nextGroup == 0) {
+ if (n.entriesMinX[next] < n.mbrMinX) n.mbrMinX = n.entriesMinX[next];
+ if (n.entriesMinY[next] < n.mbrMinY) n.mbrMinY = n.entriesMinY[next];
+ if (n.entriesMaxX[next] > n.mbrMaxX) n.mbrMaxX = n.entriesMaxX[next];
+ if (n.entriesMaxY[next] > n.mbrMaxY) n.mbrMaxY = n.entriesMaxY[next];
+ n.entryCount++;
+ } else {
+ // move to new node.
+ newNode.addEntry(n.entriesMinX[next], n.entriesMinY[next], n.entriesMaxX[next], n.entriesMaxY[next], n.ids[next]);
+ n.ids[next] = -1;
+ }
+
+ return next;
+ }
+
+ /**
+ * Recursively searches the tree for the nearest entry. Other queries
+ * call execute() on an IntProcedure when a matching entry is found;
+ * however nearest() must store the entry Ids as it searches the tree,
+ * in case a nearer entry is found.
+ * Uses the member variable nearestIds to store the nearest
+ * entry IDs.
+ *
+ * TODO rewrite this to be non-recursive?
+ */
+ private float nearest(Point p, Node n, float furthestDistanceSq) {
+ for (int i = 0; i < n.entryCount; i++) {
+ float tempDistanceSq = Rectangle.distanceSq(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i], p.x, p.y);
+ if (n.isLeaf()) { // for leaves, the distance is an actual nearest distance
+ if (tempDistanceSq < furthestDistanceSq) {
+ furthestDistanceSq = tempDistanceSq;
+ nearestIds.reset();
+ }
+ if (tempDistanceSq <= furthestDistanceSq) {
+ nearestIds.add(n.ids[i]);
+ }
+ } else { // for index nodes, only go into them if they potentially could have
+ // a rectangle nearer than actualNearest
+ if (tempDistanceSq <= furthestDistanceSq) {
+ // search the child node
+ furthestDistanceSq = nearest(p, getNode(n.ids[i]), furthestDistanceSq);
+ }
+ }
+ }
+ return furthestDistanceSq;
+ }
+
+ /**
+ * Recursively searches the tree for all intersecting entries.
+ * Immediately calls execute() on the passed IntProcedure when
+ * a matching entry is found.
+ *
+ * TODO rewrite this to be non-recursive? Make sure it
+ * doesn't slow it down.
+ */
+ private boolean intersects(Rectangle r, TIntProcedure v, Node n) {
+ for (int i = 0; i < n.entryCount; i++) {
+ if (Rectangle.intersects(r.minX, r.minY, r.maxX, r.maxY, n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i])) {
+ if (n.isLeaf()) {
+ if (!v.execute(n.ids[i])) {
+ return false;
+ }
+ } else {
+ Node childNode = getNode(n.ids[i]);
+ if (!intersects(r, v, childNode)) {
+ return false;
+ }
+ }
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Used by delete(). Ensures that all nodes from the passed node
+ * up to the root have the minimum number of entries.
+ *
+ * Note that the parent and parentEntry stacks are expected to
+ * contain the nodeIds of all parents up to the root.
+ */
+ private void condenseTree(Node l) {
+ // CT1 [Initialize] Set n=l. Set the list of eliminated
+ // nodes to be empty.
+ Node n = l;
+ Node parent = null;
+ int parentEntry = 0;
+
+ TIntStack eliminatedNodeIds = new TIntStack();
+
+ // CT2 [Find parent entry] If N is the root, go to CT6. Otherwise
+ // let P be the parent of N, and let En be N's entry in P
+ while (n.level != treeHeight) {
+ parent = getNode(parents.pop());
+ parentEntry = parentsEntry.pop();
+
+ // CT3 [Eliminiate under-full node] If N has too few entries,
+ // delete En from P and add N to the list of eliminated nodes
+ if (n.entryCount < minNodeEntries) {
+ parent.deleteEntry(parentEntry);
+ eliminatedNodeIds.push(n.nodeId);
+ } else {
+ // CT4 [Adjust covering rectangle] If N has not been eliminated,
+ // adjust EnI to tightly contain all entries in N
+ if (n.mbrMinX != parent.entriesMinX[parentEntry] ||
+ n.mbrMinY != parent.entriesMinY[parentEntry] ||
+ n.mbrMaxX != parent.entriesMaxX[parentEntry] ||
+ n.mbrMaxY != parent.entriesMaxY[parentEntry]) {
+ float deletedMinX = parent.entriesMinX[parentEntry];
+ float deletedMinY = parent.entriesMinY[parentEntry];
+ float deletedMaxX = parent.entriesMaxX[parentEntry];
+ float deletedMaxY = parent.entriesMaxY[parentEntry];
+ parent.entriesMinX[parentEntry] = n.mbrMinX;
+ parent.entriesMinY[parentEntry] = n.mbrMinY;
+ parent.entriesMaxX[parentEntry] = n.mbrMaxX;
+ parent.entriesMaxY[parentEntry] = n.mbrMaxY;
+ parent.recalculateMBRIfInfluencedBy(deletedMinX, deletedMinY, deletedMaxX, deletedMaxY);
+ }
+ }
+ // CT5 [Move up one level in tree] Set N=P and repeat from CT2
+ n = parent;
+ }
+
+ // CT6 [Reinsert orphaned entries] Reinsert all entries of nodes in set Q.
+ // Entries from eliminated leaf nodes are reinserted in tree leaves as in
+ // Insert(), but entries from higher level nodes must be placed higher in
+ // the tree, so that leaves of their dependent subtrees will be on the same
+ // level as leaves of the main tree
+ while (eliminatedNodeIds.size() > 0) {
+ Node e = getNode(eliminatedNodeIds.pop());
+ for (int j = 0; j < e.entryCount; j++) {
+ add(e.entriesMinX[j], e.entriesMinY[j], e.entriesMaxX[j], e.entriesMaxY[j], e.ids[j], e.level);
+ e.ids[j] = -1;
+ }
+ e.entryCount = 0;
+ deletedNodeIds.push(e.nodeId);
+ }
+ }
+
+ /**
+ * Used by add(). Chooses a leaf to add the rectangle to.
+ */
+ private Node chooseNode(float minX, float minY, float maxX, float maxY, int level) {
+ // CL1 [Initialize] Set N to be the root node
+ Node n = getNode(rootNodeId);
+ parents.reset();
+ parentsEntry.reset();
+
+ // CL2 [Leaf check] If N is a leaf, return N
+ while (true) {
+ if (n == null) {
+ log.error("Could not get root node (" + rootNodeId + ")");
+ }
+
+ if (n.level == level) {
+ return n;
+ }
+
+ // CL3 [Choose subtree] If N is not at the desired level, let F be the entry in N
+ // whose rectangle FI needs least enlargement to include EI. Resolve
+ // ties by choosing the entry with the rectangle of smaller area.
+ float leastEnlargement = Rectangle.enlargement(n.entriesMinX[0], n.entriesMinY[0], n.entriesMaxX[0], n.entriesMaxY[0],
+ minX, minY, maxX, maxY);
+ int index = 0; // index of rectangle in subtree
+ for (int i = 1; i < n.entryCount; i++) {
+ float tempMinX = n.entriesMinX[i];
+ float tempMinY = n.entriesMinY[i];
+ float tempMaxX = n.entriesMaxX[i];
+ float tempMaxY = n.entriesMaxY[i];
+ float tempEnlargement = Rectangle.enlargement(tempMinX, tempMinY, tempMaxX, tempMaxY,
+ minX, minY, maxX, maxY);
+ if ((tempEnlargement < leastEnlargement) ||
+ ((tempEnlargement == leastEnlargement) &&
+ (Rectangle.area(tempMinX, tempMinY, tempMaxX, tempMaxY) <
+ Rectangle.area(n.entriesMinX[index], n.entriesMinY[index], n.entriesMaxX[index], n.entriesMaxY[index])))) {
+ index = i;
+ leastEnlargement = tempEnlargement;
+ }
+ }
+
+ parents.push(n.nodeId);
+ parentsEntry.push(index);
+
+ // CL4 [Descend until a leaf is reached] Set N to be the child node
+ // pointed to by Fp and repeat from CL2
+ n = getNode(n.ids[index]);
+ }
+ }
+
+ /**
+ * Ascend from a leaf node L to the root, adjusting covering rectangles and
+ * propagating node splits as necessary.
+ */
+ private Node adjustTree(Node n, Node nn) {
+ // AT1 [Initialize] Set N=L. If L was split previously, set NN to be
+ // the resulting second node.
+
+ // AT2 [Check if done] If N is the root, stop
+ while (n.level != treeHeight) {
+
+ // AT3 [Adjust covering rectangle in parent entry] Let P be the parent
+ // node of N, and let En be N's entry in P. Adjust EnI so that it tightly
+ // encloses all entry rectangles in N.
+ Node parent = getNode(parents.pop());
+ int entry = parentsEntry.pop();
+
+ if (parent.ids[entry] != n.nodeId) {
+ log.error("Error: entry " + entry + " in node " +
+ parent.nodeId + " should point to node " +
+ n.nodeId + "; actually points to node " + parent.ids[entry]);
+ }
+
+ if (parent.entriesMinX[entry] != n.mbrMinX ||
+ parent.entriesMinY[entry] != n.mbrMinY ||
+ parent.entriesMaxX[entry] != n.mbrMaxX ||
+ parent.entriesMaxY[entry] != n.mbrMaxY) {
+
+ parent.entriesMinX[entry] = n.mbrMinX;
+ parent.entriesMinY[entry] = n.mbrMinY;
+ parent.entriesMaxX[entry] = n.mbrMaxX;
+ parent.entriesMaxY[entry] = n.mbrMaxY;
+
+ parent.recalculateMBR();
+ }
+
+ // AT4 [Propagate node split upward] If N has a partner NN resulting from
+ // an earlier split, create a new entry Enn with Ennp pointing to NN and
+ // Enni enclosing all rectangles in NN. Add Enn to P if there is room.
+ // Otherwise, invoke splitNode to produce P and PP containing Enn and
+ // all P's old entries.
+ Node newNode = null;
+ if (nn != null) {
+ if (parent.entryCount < maxNodeEntries) {
+ parent.addEntry(nn.mbrMinX, nn.mbrMinY, nn.mbrMaxX, nn.mbrMaxY, nn.nodeId);
+ } else {
+ newNode = splitNode(parent, nn.mbrMinX, nn.mbrMinY, nn.mbrMaxX, nn.mbrMaxY, nn.nodeId);
+ }
+ }
+
+ // AT5 [Move up to next level] Set N = P and set NN = PP if a split
+ // occurred. Repeat from AT2
+ n = parent;
+ nn = newNode;
+
+ parent = null;
+ newNode = null;
+ }
+
+ return nn;
+ }
+
+
+ /**
+ * Check the consistency of the tree.
+ *
+ * @return false if an inconsistency is detected, true otherwise.
+ */
+ public boolean checkConsistency() {
+ return checkConsistency(rootNodeId, treeHeight, null);
+ }
+
+ private boolean checkConsistency(int nodeId, int expectedLevel, Rectangle expectedMBR) {
+ // go through the tree, and check that the internal data structures of
+ // the tree are not corrupted.
+ Node n = getNode(nodeId);
+
+ if (n == null) {
+ log.error("Error: Could not read node " + nodeId);
+ return false;
+ }
+
+ // if tree is empty, then there should be exactly one node, at level 1
+ // TODO: also check the MBR is as for a new node
+ if (nodeId == rootNodeId && size() == 0) {
+ if (n.level != 1) {
+ log.error("Error: tree is empty but root node is not at level 1");
+ return false;
+ }
+ }
+
+ if (n.level != expectedLevel) {
+ log.error("Error: Node " + nodeId + ", expected level " + expectedLevel + ", actual level " + n.level);
+ return false;
+ }
+
+ Rectangle calculatedMBR = calculateMBR(n);
+ Rectangle actualMBR = new Rectangle();
+ actualMBR.minX = n.mbrMinX;
+ actualMBR.minY = n.mbrMinY;
+ actualMBR.maxX = n.mbrMaxX;
+ actualMBR.maxY = n.mbrMaxY;
+ if (!actualMBR.equals(calculatedMBR)) {
+ log.error("Error: Node " + nodeId + ", calculated MBR does not equal stored MBR");
+ if (actualMBR.minX != n.mbrMinX) log.error(" actualMinX=" + actualMBR.minX + ", calc=" + calculatedMBR.minX);
+ if (actualMBR.minY != n.mbrMinY) log.error(" actualMinY=" + actualMBR.minY + ", calc=" + calculatedMBR.minY);
+ if (actualMBR.maxX != n.mbrMaxX) log.error(" actualMaxX=" + actualMBR.maxX + ", calc=" + calculatedMBR.maxX);
+ if (actualMBR.maxY != n.mbrMaxY) log.error(" actualMaxY=" + actualMBR.maxY + ", calc=" + calculatedMBR.maxY);
+ return false;
+ }
+
+ if (expectedMBR != null && !actualMBR.equals(expectedMBR)) {
+ log.error("Error: Node " + nodeId + ", expected MBR (from parent) does not equal stored MBR");
+ return false;
+ }
+
+ // Check for corruption where a parent entry is the same object as the child MBR
+ if (expectedMBR != null && actualMBR.sameObject(expectedMBR)) {
+ log.error("Error: Node " + nodeId + " MBR using same rectangle object as parent's entry");
+ return false;
+ }
+
+ for (int i = 0; i < n.entryCount; i++) {
+ if (n.ids[i] == -1) {
+ log.error("Error: Node " + nodeId + ", Entry " + i + " is null");
+ return false;
+ }
+
+ if (n.level > 1) { // if not a leaf
+ if (!checkConsistency(n.ids[i], n.level - 1, new Rectangle(n.entriesMinX[i], n.entriesMinY[i], n.entriesMaxX[i], n.entriesMaxY[i]))) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Given a node object, calculate the node MBR from it's entries.
+ * Used in consistency checking
+ */
+ private Rectangle calculateMBR(Node n) {
+ Rectangle mbr = new Rectangle();
+
+ for (int i = 0; i < n.entryCount; i++) {
+ if (n.entriesMinX[i] < mbr.minX) mbr.minX = n.entriesMinX[i];
+ if (n.entriesMinY[i] < mbr.minY) mbr.minY = n.entriesMinY[i];
+ if (n.entriesMaxX[i] > mbr.maxX) mbr.maxX = n.entriesMaxX[i];
+ if (n.entriesMaxY[i] > mbr.maxY) mbr.maxY = n.entriesMaxY[i];
+ }
+ return mbr;
+ }
+}
Code Review / simantics / platform.git / blobdiff