Class HPRtree

  • All Implemented Interfaces:
    SpatialIndex

    public class HPRtree
    extends java.lang.Object
    implements SpatialIndex
    A Hilbert-Packed R-tree. This is a static R-tree which is packed by using the Hilbert ordering of the tree items.

    The tree is constructed by sorting the items by the Hilbert code of the midpoint of their envelope. Then, a set of internal layers is created recursively as follows:

    • The items/nodes of the previous are partitioned into blocks of size nodeCapacity
    • For each block a layer node is created with range equal to the envelope of the items/nodess in the block
    The internal layers are stored using an array to store the node bounds. The link between a node and its children is stored implicitly in the indexes of the array. For efficiency, the offsets to the layers within the node array are pre-computed and stored.

    NOTE: Based on performance testing, the HPRtree is somewhat faster than the STRtree. It should also be more memory-efficent, due to fewer object allocations. However, it is not clear whether this will produce a significant improvement for use in JTS operations.

    Author:
    Martin Davis
    See Also:
    STRtree
    • Constructor Summary

      Constructors 
      Constructor Description
      HPRtree()
      Creates a new index with the default node capacity.
      HPRtree​(int nodeCapacity)
      Creates a new index with the given node capacity.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void build()
      Builds the index, if not already built.
      Envelope[] getBounds()
      Gets the extents of the internal index nodes
      void insert​(Envelope itemEnv, java.lang.Object item)
      Adds a spatial item with an extent specified by the given Envelope to the index
      java.util.List query​(Envelope searchEnv)
      Queries the index for all items whose extents intersect the given search Envelope Note that some kinds of indexes may also return objects which do not in fact intersect the query envelope.
      void query​(Envelope searchEnv, ItemVisitor visitor)
      Queries the index for all items whose extents intersect the given search Envelope, and applies an ItemVisitor to them.
      boolean remove​(Envelope itemEnv, java.lang.Object item)
      Removes a single item from the tree.
      int size()
      Gets the number of items in the index.
      • Methods inherited from class java.lang.Object

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

      • HPRtree

        public HPRtree()
        Creates a new index with the default node capacity.
      • HPRtree

        public HPRtree​(int nodeCapacity)
        Creates a new index with the given node capacity.
        Parameters:
        nodeCapacity - the node capacity to use
    • Method Detail

      • size

        public int size()
        Gets the number of items in the index.
        Returns:
        the number of items
      • insert

        public void insert​(Envelope itemEnv,
                           java.lang.Object item)
        Description copied from interface: SpatialIndex
        Adds a spatial item with an extent specified by the given Envelope to the index
        Specified by:
        insert in interface SpatialIndex
      • query

        public java.util.List query​(Envelope searchEnv)
        Description copied from interface: SpatialIndex
        Queries the index for all items whose extents intersect the given search Envelope Note that some kinds of indexes may also return objects which do not in fact intersect the query envelope.
        Specified by:
        query in interface SpatialIndex
        Parameters:
        searchEnv - the envelope to query for
        Returns:
        a list of the items found by the query
      • query

        public void query​(Envelope searchEnv,
                          ItemVisitor visitor)
        Description copied from interface: SpatialIndex
        Queries the index for all items whose extents intersect the given search Envelope, and applies an ItemVisitor to them. Note that some kinds of indexes may also return objects which do not in fact intersect the query envelope.
        Specified by:
        query in interface SpatialIndex
        Parameters:
        searchEnv - the envelope to query for
        visitor - a visitor object to apply to the items found
      • remove

        public boolean remove​(Envelope itemEnv,
                              java.lang.Object item)
        Description copied from interface: SpatialIndex
        Removes a single item from the tree.
        Specified by:
        remove in interface SpatialIndex
        Parameters:
        itemEnv - the Envelope of the item to remove
        item - the item to remove
        Returns:
        true if the item was found
      • build

        public void build()
        Builds the index, if not already built.
      • getBounds

        public Envelope[] getBounds()
        Gets the extents of the internal index nodes
        Returns:
        a list of the internal node extents