net.sourceforge.hatbox
Class RTree

java.lang.Object
  extended by net.sourceforge.hatbox.RTree

public class RTree
extends java.lang.Object

An r-tree implementation based on Antonin Guttman 1984 "R-TREES A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING"

Author:
Peter Yuill

Constructor Summary
RTree(RTreeSession session)
           
 
Method Summary
 void delete(Entry entry)
          Delete an entry from the index.
 double getMinNodeSplit()
           
 void insert(Entry entry)
          Insert a new index entry
protected  Entry pickNext(java.util.List<Entry> entryList, Envelope e1, Envelope e2)
          Pick the entry that has the biggest difference in affinity for the two groups
protected  Entry[] pickSeeds(java.util.List<Entry> entryList)
          Choose the most wasteful pair of entries to have in the same node and make them the seeds for each of the split nodes.
 java.util.List<java.lang.Long> search(Envelope searchEnv)
          Search the index for entries that intersect the search envelope
 void setMinNodeSplit(double minNodeSplit)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

RTree

public RTree(RTreeSession session)
Method Detail

search

public java.util.List<java.lang.Long> search(Envelope searchEnv)
                                      throws java.sql.SQLException
Search the index for entries that intersect the search envelope

(ref Guttman84 p48)

Parameters:
searchEnv -
Returns:
Throws:
java.sql.SQLException

insert

public void insert(Entry entry)
            throws java.sql.SQLException
Insert a new index entry

(ref Guttman84 p49)

Parameters:
entry -
Throws:
java.sql.SQLException

pickSeeds

protected Entry[] pickSeeds(java.util.List<Entry> entryList)
Choose the most wasteful pair of entries to have in the same node and make them the seeds for each of the split nodes.

(ref Guttman84 p52)

There is some doubt in my mind about the detail of the algorithm with respect to intersecting candidates. Guttman appears to 'double count' the area of intersection, giving rise to artificially low deltas.

Parameters:
entryList -
Returns:

pickNext

protected Entry pickNext(java.util.List<Entry> entryList,
                         Envelope e1,
                         Envelope e2)
Pick the entry that has the biggest difference in affinity for the two groups

(ref Guttman84 p52)

Parameters:
entryList - The remaining entries.
e1 - Envelope of the first group.
e2 - Envelope of the second group.
Returns:
The selected entry.

getMinNodeSplit

public double getMinNodeSplit()

setMinNodeSplit

public void setMinNodeSplit(double minNodeSplit)

delete

public void delete(Entry entry)
            throws java.sql.SQLException
Delete an entry from the index.

(ref Guttman84 p50)

Parameters:
entry -
Throws:
java.sql.SQLException


Copyright © 2010. All Rights Reserved.