Class 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 may be the projection of 2-D objects on an axis). It supports range searching (where the range may be a single point). This structure is dynamic - new items can be added at any time, and it will support deletion of items (although this is not currently implemented).

    This implementation does not require specifying the extent of the inserted items beforehand. It will automatically expand to accommodate 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

      Constructors 
      Constructor Description
      Bintree()  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      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)
      Queries the tree to find all candidate items which may overlap the query interval.
      void query​(Interval interval, java.util.Collection foundItems)
      Adds items in the tree which potentially overlap the query interval to the given collection.
      boolean remove​(Interval itemInterval, java.lang.Object item)
      Removes a single item from the tree.
      int size()  
      • Methods inherited from class java.lang.Object

        equals, 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)
      • remove

        public boolean remove​(Interval itemInterval,
                              java.lang.Object item)
        Removes a single item from the tree.
        Parameters:
        itemEnv - the Envelope of the item to be removed
        item - the item to remove
        Returns:
        true if the item was found (and thus removed)
      • iterator

        public java.util.Iterator iterator()
      • query

        public java.util.List query​(double x)
      • query

        public java.util.List query​(Interval interval)
        Queries the tree to find all candidate items which may overlap the query interval. If the query interval is null, all items in the tree are found. min and max may be the same value
      • query

        public void query​(Interval interval,
                          java.util.Collection foundItems)
        Adds items in the tree which potentially overlap the query interval to the given collection. If the query interval is null, add all items in the tree.
        Parameters:
        interval - a query interval, or null
        resultItems - the candidate items found