org.locationtech.jts.index.hprtree

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:

STRtree

Constructor Summary

Constructors

Constructor and 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

Modifier and Type	Method and Description
void	build() Builds the index, if not already built.
Envelope[]	getBounds() 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
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, 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,
                   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