Class SortedPackedIntervalRTree


  • public class SortedPackedIntervalRTree
    extends java.lang.Object
    A static index on a set of 1-dimensional intervals, using an R-Tree packed based on the order of the interval midpoints. It supports range searching, where the range is an interval of the real line (which may be a single point). A common use is to index 1-dimensional intervals which are the projection of 2-D objects onto an axis of the coordinate system.

    This index structure is static - items cannot be added or removed once the first query has been made. The advantage of this characteristic is that the index performance can be optimized based on a fixed set of items.

    Author:
    Martin Davis
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void insert​(double min, double max, java.lang.Object item)
      Adds an item to the index which is associated with the given interval
      void query​(double min, double max, ItemVisitor visitor)
      Search for intervals in the index which intersect the given closed interval and apply the visitor to them.
      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • SortedPackedIntervalRTree

        public SortedPackedIntervalRTree()
    • Method Detail

      • insert

        public void insert​(double min,
                           double max,
                           java.lang.Object item)
        Adds an item to the index which is associated with the given interval
        Parameters:
        min - the lower bound of the item interval
        max - the upper bound of the item interval
        item - the item to insert
        Throws:
        java.lang.IllegalStateException - if the index has already been queried
      • query

        public void query​(double min,
                          double max,
                          ItemVisitor visitor)
        Search for intervals in the index which intersect the given closed interval and apply the visitor to them.
        Parameters:
        min - the lower bound of the query interval
        max - the upper bound of the query interval
        visitor - the visitor to pass any matched items to