Class HPRtree

java.lang.Object
org.locationtech.jts.index.hprtree.HPRtree
All Implemented Interfaces:
SpatialIndex

public class HPRtree extends 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:
  • Constructor Summary

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

    Modifier and Type
    Method
    Description
    void
    Builds the index, if not already built.
    Gets the extents of the internal index nodes
    void
    insert(Envelope itemEnv, Object item)
    Adds a spatial item with an extent specified by the given Envelope to the index
    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, Object item)
    Removes a single item from the tree.
    int
    Gets the number of items in the index.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • 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 Details

    • size

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

      public void insert(Envelope itemEnv, 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 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, 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