rtree.java 1.3

R-Tree Java implementations 结构清晰

//   RTree.java
//   Java Spatial Index Library
//   Copyright (C) 2002 Infomatiq Limited
//  
//  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.TIntObjectIterator;
import gnu.trove.TIntProcedure;
import gnu.trove.TIntStack;
import gnu.trove.TObjectProcedure;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.util.ArrayList;
import java.util.Properties;

import org.apache.log4j.Logger;

import com.infomatiq.jsi.CvsUtil;
import com.infomatiq.jsi.IntProcedure;
import com.infomatiq.jsi.Point;
import com.infomatiq.jsi.Rectangle;
import com.infomatiq.jsi.SpatialIndex;
import com.infomatiq.jsi.SpatialIndexChecksum;
import com.infomatiq.jsi.rtree.visualization.VisualizeNodeSplit;

/**
 * <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>In addition, the RTree must be externalizable, using a checksum of all entries
 * to determine whether the serialized RTree is valid.</p>
 * 
 * <p>Currently, the only tested methods are add() and intersects(). These methods have 
 * been benchmarked against the Spatial Index Library (version 0.2b beta), and run
 * approximately 4 to 5 times faster. The memory usage has not yet been benchmarked. 
 * It is recommended you use that library if you need a fully featured spatial index.
 * 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 [e-mail]
 * @version $Revision: 1.7 $
 */
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 revision = CvsUtil.getShortRevisionNumber("$Revision: 1.7 $");
  
  // parameters of the tree
  private final static int DEFAULT_MAX_NODE_ENTRIES = 10;
  int maxNodeEntries;
  int minNodeEntries;
  
  // visualization classes
  private VisualizeNodeSplit vns = null;
  
  // map of nodeId -> node object
  // [x] TODO eliminate this map - it should not be needed. Nodes
  // can be found by traversing the tree.
  private TIntObjectHashMap nodeMap = new TIntObjectHashMap();
  
  // internal consistency checking - set to true if debugging tree corruption
  private final boolean internalConsistencyChecking = false;
  
  // visualization - currently more for novelty value, but could be useful
  // for debugging node splitting problems
  private final boolean visualization = 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;
  
  // 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();
  
  // Inner class used as a bridge between the trove4j TIntProcedure
  // and the SpatialIndex IntProcedure. This is used because 
  // the nearest rectangles must be stored as they are found, in
  // case a closer one is found later. 
  // 
  // A single instance of this class is used to avoid creating a new 
  // one every time nearest() is called.
  class TIntProcedureVisit implements TIntProcedure {
  	public IntProcedure m_intProcedure = null;
  	
  	public void setProcedure(IntProcedure ip) {
  	  m_intProcedure = ip;
  	}
  	public boolean execute(int i) {
  	  m_intProcedure.execute(i);
  	  return true;
  	}
  }; 
  private TIntProcedureVisit visitProc = new TIntProcedureVisit();
  
  /**
   * 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, IntProcedure, float)
  //  intersects(Rectangle, IntProcedure)
  //  contains(Rectangle, IntProcedure)
  //-------------------------------------------------------------------------
  /**
   * <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) {
    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);
    
    if (visualization) {
      vns = new VisualizeNodeSplit();
      vns.start();
    }
    
    log.info("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.copy(), id, 1);  
  }
  
  /**
   * Adds a new entry at a specified level in the tree
   */
  private void add(Rectangle r, 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(r, 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.addEntryNoCopy(r, id);
    } else {
      newLeaf = splitNode(n, r, 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.mbr, newNode.nodeId);
      root.addEntry(oldRoot.mbr, oldRoot.nodeId);
      nodeMap.put(rootNodeId, root);
    }
    
    if (internalConsistencyChecking) {
      checkConsistency(rootNodeId, treeHeight, null);
    }
  } 
  
  /**
   * @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.clear();
  	parents.push(rootNodeId);
  	
  	parentsEntry.clear();
  	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 (n.entries[i].contains(r)) {
	  	      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, id);        
      }
      
      parents.pop();
      parentsEntry.pop();
  	} // while not found
  	
  	if (foundIndex != -1) {
  	  n.deleteEntry(foundIndex, minNodeEntries);
      condenseTree(n);
  	}
    
    return (foundIndex != -1);
  }
  
  /**
   * @see com.infomatiq.jsi.SpatialIndex#nearest(Rectangle, IntProcedure)
   */
  public void nearest(Point p, IntProcedure v, float furthestDistance) {
    Node rootNode = getNode(rootNodeId);
   
    nearest(p, rootNode, furthestDistance);
   
    visitProc.setProcedure(v);
    nearestIds.forEach(visitProc);
    nearestIds.clear();
  }
   
  /**