Class HPRtree
java.lang.Object
org.locationtech.jts.index.hprtree.HPRtree
- All Implemented Interfaces:
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
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 -
Method Summary
Modifier and TypeMethodDescriptionvoid
build()
Builds the index, if not already built.Envelope[]
Gets the extents of the internal index nodesvoid
Adds a spatial item with an extent specified by the givenEnvelope
to the indexQueries the index for all items whose extents intersect the given searchEnvelope
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 searchEnvelope
, and applies anItemVisitor
to them.boolean
Removes a single item from the tree.int
size()
Gets the number of items in the index.
-
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
Description copied from interface:SpatialIndex
Adds a spatial item with an extent specified by the givenEnvelope
to the index- Specified by:
insert
in interfaceSpatialIndex
-
query
Description copied from interface:SpatialIndex
Queries the index for all items whose extents intersect the given searchEnvelope
Note that some kinds of indexes may also return objects which do not in fact intersect the query envelope.- Specified by:
query
in interfaceSpatialIndex
- Parameters:
searchEnv
- the envelope to query for- Returns:
- a list of the items found by the query
-
query
Description copied from interface:SpatialIndex
Queries the index for all items whose extents intersect the given searchEnvelope
, and applies anItemVisitor
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 interfaceSpatialIndex
- Parameters:
searchEnv
- the envelope to query forvisitor
- a visitor object to apply to the items found
-
remove
Description copied from interface:SpatialIndex
Removes a single item from the tree.- Specified by:
remove
in interfaceSpatialIndex
- Parameters:
itemEnv
- the Envelope of the item to removeitem
- the item to remove- Returns:
true
if the item was found
-
build
public void build()Builds the index, if not already built. -
getBounds
Gets the extents of the internal index nodes- Returns:
- a list of the internal node extents
-