Class HPRtree

Hierarchy: Object , HPRtree

All Implemented Interfaces: SpatialIndex

public class HPRtree
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.

Authors:: Martin Davis

See also:: STRtree

public HPRtree()

Creates a new index with the default node capacity.

public HPRtree(int nodeCapacity)

Creates a new index with the given node capacity.

Parameters:: nodeCapacity - nodeCapacity the node capacity to use

public int size()

Gets the number of items in the index.

Returns:: the number of items

public void insert(Envelope itemEnv, Object item)

public List query(Envelope searchEnv)

public void query(Envelope searchEnv, ItemVisitor visitor)

public boolean remove(Envelope itemEnv, Object item)

public synchronized void build()

Builds the index, if not already built.

public Envelope[] getBounds()

Gets the extents of the internal index nodes

Returns:: a list of the internal node extents