rtree.java

来自「R-Tree Java implementations 结构清晰」· Java 代码 · 共 951 行 · 第 1/3 页

    nearestIds.clear();
  }
   
  /**
   * @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) {
    // 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.clear();
    parents.push(rootNodeId);
    
    parentsEntry.clear();
    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 (r.intersects(n.entries[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 (r.contains(n.entries[i])) {
            v.execute(n.ids[i]);
          } 
        }                       
      }
      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.getMBR() != null) {
      bounds = n.getMBR().copy();
    }
    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 index) {
    return (Node) nodeMap.get(index);
  }

  /**
   * 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, 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()) {
      Rectangle union = n.mbr.union(newRect);
      initialArea = union.area();
    }
       
    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++;
          }
        }
        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.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 (INTERNAL_CONSISTENCY_CHECKING) {
      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");
      }
    }
    
    // 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);
  }

  /** 
   * 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()");
    }