rtree.java 1.3

R-Tree Java implementations 结构清晰

          } else if (newNodeIncrease < nIncrease) {
            nextGroup = 1;
          } else if (n.mbr.area() < newNode.mbr.area()) {
            nextGroup = 0;
          } else if (newNode.mbr.area() < n.mbr.area()) {
            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 (visualization) {
      int s = (nextGroup == 0 ? VisualizeNodeSplit.STATUS_ASSIGNED_TO_GROUP0 :
                                VisualizeNodeSplit.STATUS_ASSIGNED_TO_GROUP1);
      vns.setRectangleStatus(n.entries[next], n.isLeaf(), n.ids[next], s);
      vns.redraw();
    }
      
    if (nextGroup == 0) {
      n.mbr.add(n.entries[next]);
      n.entryCount++;
    } else {
      // move to new node.
      newNode.addEntryNoCopy(n.entries[next], n.ids[next]);
      n.entries[next] = null;
    }
    
    if (visualization) {
      vns.setRectangleStatus(n.mbr, false, n.nodeId, VisualizeNodeSplit.STATUS_MBR_GROUP0);
      vns.setRectangleStatus(newNode.mbr, false, newNode.nodeId, VisualizeNodeSplit.STATUS_MBR_GROUP1);      
      vns.redraw();
    }
    
    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.
   * 
   * [x] TODO rewrite this to be non-recursive?
   */
  private void nearest(Point p, Node n, float nearestDistance) {
    for (int i = 0; i < n.entryCount; i++) {
      float tempDistance = n.entries[i].distance(p);  
      if (n.isLeaf()) { // for leaves, the distance is an actual nearest distance 
        if (tempDistance <= nearestDistance) {
          nearestIds.add(n.ids[i]);
          nearestDistance = tempDistance;
        }     
      } else { // for index nodes, only go into them if they potentially could have
               // a rectangle nearer than actualNearest
         if (tempDistance < nearestDistance) {
           // search the child node
           nearest(p, getNode(n.ids[i]), nearestDistance);
         }
      }
    }
  }
  
  /** 
   * Recursively searches the tree for all intersecting entries.
   * Immediately calls execute() on the passed IntProcedure when 
   * a matching entry is found.
   * 
   * [x] TODO rewrite this to be non-recursive? Make sure it
   * doesn't slow it down.
   */
  private void intersects(Rectangle r, IntProcedure v, Node n) {
    for (int i = 0; i < n.entryCount; i++) {
      if (r.intersects(n.entries[i])) {
        if (n.isLeaf()) {
          v.execute(n.ids[i]);
        } else {
          Node childNode = getNode(n.ids[i]);
          intersects(r, v, childNode);
        }
      }
    }
  }

  /**
   * 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.
   */
  Rectangle oldRectangle = new Rectangle(0, 0, 0, 0);
  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, minNodeEntries);
        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.mbr.equals(parent.entries[parentEntry])) {
          oldRectangle.set(parent.entries[parentEntry].min, parent.entries[parentEntry].max);
          parent.entries[parentEntry].set(n.mbr.min, n.mbr.max);
          parent.recalculateMBR(oldRectangle);
        }
      }
      // 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.entries[j], e.ids[j], e.level); 
        e.entries[j] = null;
      }
      e.entryCount = 0;
      deletedNodeIds.push(e.nodeId);
    }
  }

  /**
   *  Used by add(). Chooses a leaf to add the rectangle to.
   */
  private Node chooseNode(Rectangle r, int level) {
    // CL1 [Initialize] Set N to be the root node
    Node n = getNode(rootNodeId);
    parents.clear();
    parentsEntry.clear();
     
    // CL2 [Leaf check] If N is a leaf, return N
    while (true) {
      if (n == null) {
        System.out.println("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 = n.getEntry(0).enlargement(r);
      int index = 0; // index of rectangle in subtree
      for (int i = 1; i < n.entryCount; i++) {
        Rectangle tempRectangle = n.getEntry(i);
        float tempEnlargement = tempRectangle.enlargement(r);
        if ((tempEnlargement < leastEnlargement) ||
            ((tempEnlargement == leastEnlargement) && 
             (tempRectangle.area() < n.getEntry(index).area()))) {
          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.entries[entry].equals(n.mbr)) {
        parent.entries[entry].set(n.mbr.min, n.mbr.max);
        parent.mbr.set(parent.entries[0].min, parent.entries[0].max);
        for (int i = 1; i < parent.entryCount; i++) {
          parent.mbr.add(parent.entries[i]);
        }
      }
      
      // 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.mbr, nn.nodeId);
        } else {
          newNode = splitNode(parent, nn.mbr.copy(), 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.
   */
  private void 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);
    }
    
    if (n.level != expectedLevel) {
      log.error("Error: Node " + nodeId + ", expected level " + expectedLevel + ", actual level " + n.level);
    }
    
    Rectangle calculatedMBR = calculateMBR(n);
    
    if (!n.mbr.equals(calculatedMBR)) {
      log.error("Error: Node " + nodeId + ", calculated MBR does not equal stored MBR");
    }
    
    if (expectedMBR != null && !n.mbr.equals(expectedMBR)) {
      log.error("Error: Node " + nodeId + ", expected MBR (from parent) does not equal stored MBR");
    }
    
    // Check for corruption where a parent entry is the same object as the child MBR
    if (expectedMBR != null && n.mbr.sameObject(expectedMBR)) {
      log.error("Error: Node " + nodeId + " MBR using same rectangle object as parent's entry");
    }
    
    for (int i = 0; i < n.entryCount; i++) {
      if (n.entries[i] == null) {
        log.error("Error: Node " + nodeId + ", Entry " + i + " is null");
      }     
      
      if (n.level > 1) { // if not a leaf
        checkConsistency(n.ids[i], n.level - 1, n.entries[i]); 
      }   
    } 
  }
  
  /**
   * 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(n.entries[0].min, n.entries[0].max);
    
    for (int i = 1; i < n.entryCount; i++) {
      mbr.add(n.entries[i]);
    }
    return mbr; 
  }
  
  /**
   * Computes a checksum for the RTree. The checksum depends only on the entries
   * in the RTree, and is independent of the RTree variant or its properties.
   */
  private long getChecksum() {
  	final SpatialIndexChecksum c = new SpatialIndexChecksum();
    nodeMap.forEachValue(new TObjectProcedure() {
      public boolean execute(Object o) {
      	Node n = (Node) o;
      	if (n.isLeaf()) {
          for (int i = 0; i < n.getEntryCount(); i++) {
            c.update(n.entries[i], n.ids[i]);
          }
      	}
      	return true;
      }	
    });
    return c.getValue();
  }  
  
  
}