com.vividsolutions.jts.index.bintree
Class Bintree

java.lang.Object
  extended bycom.vividsolutions.jts.index.bintree.Bintree

public class Bintree
extends java.lang.Object

An BinTree (or "Binary Interval Tree") is a 1-dimensional version of a quadtree. It indexes 1-dimensional intervals (which of course may be the projection of 2-D objects on an axis). It supports range searching (where the range may be a single point).

This implementation does not require specifying the extent of the inserted items beforehand. It will automatically expand to accomodate any extent of dataset.

The bintree structure is used to provide a primary filter for interval queries. The query() method returns a list of all objects which may intersect the query interval. Note that it may return objects which do not in fact intersect. A secondary filter is required to test for exact intersection. Of course, this secondary filter may consist of other tests besides intersection, such as testing other kinds of spatial relationships.

This index is different to the Interval Tree of Edelsbrunner or the Segment Tree of Bentley.

Version:
1.7

Constructor Summary
Bintree()
           
 
Method Summary
 int depth()
           
static Interval ensureExtent(Interval itemInterval, double minExtent)
          Ensure that the Interval for the inserted item has non-zero extents.
 void insert(Interval itemInterval, java.lang.Object item)
           
 java.util.Iterator iterator()
           
 int nodeSize()
          Compute the total number of nodes in the tree
 java.util.List query(double x)
           
 java.util.List query(Interval interval)
          min and max may be the same value
 void query(Interval interval, java.util.Collection foundItems)
           
 int size()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Bintree

public Bintree()
Method Detail

ensureExtent

public static Interval ensureExtent(Interval itemInterval,
                                    double minExtent)
Ensure that the Interval for the inserted item has non-zero extents. Use the current minExtent to pad it, if necessary


depth

public int depth()

size

public int size()

nodeSize

public int nodeSize()
Compute the total number of nodes in the tree

Returns:
the number of nodes in the tree

insert

public void insert(Interval itemInterval,
                   java.lang.Object item)

iterator

public java.util.Iterator iterator()

query

public java.util.List query(double x)

query

public java.util.List query(Interval interval)
min and max may be the same value


query

public void query(Interval interval,
                  java.util.Collection foundItems)