rtree.java 1.3

R-Tree Java implementations 结构清晰

   * @see com.infomatiq.jsi.SpatialIndex#intersects(Rectangle, IntProcedure)
   */
  public void intersects(Rectangle r, IntProcedure v) {
    Node rootNode = getNode(rootNodeId);
    intersects(r, v, rootNode);
  }

  /**
   * @see com.infomatiq.jsi.SpatialIndex#contains(Rectangle, IntProcedure)
   */
  public void contains(Rectangle r, IntProcedure v) {}
  
  /**
   * @see com.infomatiq.jsi.SpatialIndex#getRevision()
   */
  public String getRevision() {
    return "RTree-" + revision;
  }
  //-------------------------------------------------------------------------
  // end of SpatialIndex methods
  //-------------------------------------------------------------------------
  
  //-------------------------------------------------------------------------
  // Implementation of Externalizable interface:
  //  writeExternal(ObjectOutput)
  //  readExternal(ObjectInput) 
  //-------------------------------------------------------------------------
  /**
   * Saves the spatial index to a disk file.
   * 
   * @see java.io.Externalizable#writeExternal(ObjectOutput)
   */
  public void writeExternal(ObjectOutput out) throws IOException {
    out.writeInt(maxNodeEntries);
    out.writeInt(minNodeEntries);
    out.writeInt(treeHeight);
    out.writeInt(rootNodeId);
    out.writeInt(nodeMap.size());
    
    TIntObjectIterator i = nodeMap.iterator();
    
    while (i.hasNext()) {
      i.advance();
      Node n = (Node) i.value();
      n.writeExternal(out);
    }
    
  }
  
  /**
   * Reads the rtree from a disk file. Not yet implemented.
   * 
   * @see java.io.Externalizable#readExternal(ObjectInput)
   */
  public void readExternal(ObjectInput in) {
    
  }
  //-------------------------------------------------------------------------
  // End of Externalizable interface
  //-------------------------------------------------------------------------
  
  /**
   * 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 index) {
    return (Node) nodeMap.get(index);
  }
  
  public int getHighestUsedNodeId() {
    return highestUsedNodeId;
  }

  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, Rectangle newRect, 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() || visualization) {
      Rectangle union = n.mbr.union(newRect);
      initialArea = union.area(); 
  
      // visualization code
      if (visualization) {
        vns.clear();
        vns.setBounds(union);
        vns.setRectangleStatus(newRect, n.isLeaf(), newId, VisualizeNodeSplit.STATUS_NEW_RECTANGLE);
        vns.setRectangleStatus(n.mbr, false, n.nodeId, VisualizeNodeSplit.STATUS_ORIGINAL_MBR);
        for (int i = 0; i < n.entryCount; i++) {
          vns.setRectangleStatus(n.entries[i], n.isLeaf(), n.ids[i], VisualizeNodeSplit.STATUS_UNASSIGNED); 
        }
        vns.redraw();
      }
    }
       
    System.arraycopy(initialEntryStatus, 0, entryStatus, 0, maxNodeEntries);
    
    Node newNode = null;
    newNode = new Node(getNextNodeId(), n.level, maxNodeEntries);
    nodeMap.put(newNode.nodeId, newNode);
    
    pickSeeds(n, newRect, 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;
            n.mbr.add(n.entries[i]);
            n.entryCount++;
            
            if (visualization) {
              vns.setRectangleStatus(n.entries[i], n.isLeaf(), n.ids[i], VisualizeNodeSplit.STATUS_ASSIGNED_TO_GROUP0);
              vns.setRectangleStatus(n.mbr, false, n.nodeId, VisualizeNodeSplit.STATUS_MBR_GROUP0);
              vns.redraw();
            }
          }
        }
        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) {
            
            if (visualization) {
              vns.setRectangleStatus(n.entries[i], n.isLeaf(), n.ids[i], VisualizeNodeSplit.STATUS_ASSIGNED_TO_GROUP1);
              vns.setRectangleStatus(n.mbr, false, n.nodeId, VisualizeNodeSplit.STATUS_MBR_GROUP1);
              vns.redraw();
            }
            
            entryStatus[i] = ENTRY_STATUS_ASSIGNED;
            newNode.addEntryNoCopy(n.entries[i], n.ids[i]);
            n.entries[i] = null;
          }
        }
        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 (internalConsistencyChecking) {
      if (!n.mbr.equals(calculateMBR(n))) {
        log.error("Error: splitNode old node MBR wrong");
      }
      
      if (!newNode.mbr.equals(calculateMBR(newNode))) {
        log.error("Error: splitNode new node MBR wrong");
      }
    }
    
    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();
    }
    
    // debug code
    if (log.isDebugEnabled()) {
      float newArea = n.mbr.area() + newNode.mbr.area();
      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, Rectangle newRect, 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 = 0;
    int highestLowIndex = 0;
    int lowestHighIndex = 0;
    
    // for the purposes of picking seeds, take the MBR of the node to include
    // the new rectangle aswell.
    n.mbr.add(newRect);
    
    if (log.isDebugEnabled()) {
      log.debug("pickSeeds(): NodeId = " + n.nodeId + ", newRect = " + newRect);
    }
    
    for (int d = 0; d < Rectangle.DIMENSIONS; d++) {
      float tempHighestLow = newRect.min[d];
      int tempHighestLowIndex = -1; // -1 indicates the new rectangle is the seed
      
      float tempLowestHigh = newRect.max[d];
      int tempLowestHighIndex = -1;
      
      for (int i = 0; i < n.entryCount; i++) {
        float tempLow = n.entries[i].min[d];
        if (tempLow >= tempHighestLow) {
           tempHighestLow = tempLow;
           tempHighestLowIndex = i;
        } else {  // ensure that the same index cannot be both lowestHigh and highestLow
          float tempHigh = n.entries[i].max[d];
          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 = (tempHighestLow - tempLowestHigh) / (n.mbr.max[d] - n.mbr.min[d]);
        
        if (normalizedSeparation > 1 || normalizedSeparation < -1) {
          log.error("Invalid normalized separation");
        }
      
        if (log.isDebugEnabled()) {
          log.debug("Entry " + i + ", dimension " + d + ": 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.
        if (normalizedSeparation > maxNormalizedSeparation) {
          maxNormalizedSeparation = normalizedSeparation;
          highestLowIndex = tempHighestLowIndex;
          lowestHighIndex = tempLowestHighIndex;
        }
      }
    }
      
    // highestLowIndex is the seed for the new node.
    if (highestLowIndex == -1) {
      newNode.addEntry(newRect, newId);
    } else {
      newNode.addEntryNoCopy(n.entries[highestLowIndex], n.ids[highestLowIndex]);
      n.entries[highestLowIndex] = null;
      
      // move the new rectangle into the space vacated by the seed for the new node
      n.entries[highestLowIndex] = newRect;
      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.mbr.set(n.entries[lowestHighIndex].min, n.entries[lowestHighIndex].max);
    
    if (visualization) {
      vns.setRectangleStatus(n.entries[lowestHighIndex], n.isLeaf(), n.ids[lowestHighIndex], VisualizeNodeSplit.STATUS_SEED_GROUP0);
      vns.setRectangleStatus(newNode.entries[0], newNode.isLeaf(), newNode.ids[0], VisualizeNodeSplit.STATUS_SEED_GROUP1);
      vns.redraw();
    }
  }

  /** 
   * 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.entries[i] == null) {
          log.error("Error: Node " + n.nodeId + ", entry " + i + " is null");
        }
        
        float nIncrease = n.mbr.enlargement(n.entries[i]);
        float newNodeIncrease = newNode.mbr.enlargement(n.entries[i]);
        float difference = Math.abs(nIncrease - newNodeIncrease);
         
        if (difference > maxDifference) {
          next = i;
          
          if (nIncrease < newNodeIncrease) {
            nextGroup = 0;