Class HPRtree
- java.lang.Object
-
- org.locationtech.jts.index.hprtree.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
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
-
-
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 nodesvoid
insert(Envelope itemEnv, java.lang.Object item)
Adds a spatial item with an extent specified by the givenEnvelope
to the indexjava.util.List
query(Envelope searchEnv)
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.void
query(Envelope searchEnv, ItemVisitor visitor)
Queries the index for all items whose extents intersect the given searchEnvelope
, and applies anItemVisitor
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.
-
-
-
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 givenEnvelope
to the index- Specified by:
insert
in interfaceSpatialIndex
-
query
public java.util.List query(Envelope searchEnv)
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
public void query(Envelope searchEnv, ItemVisitor visitor)
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
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 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
public Envelope[] getBounds()
Gets the extents of the internal index nodes- Returns:
- a list of the internal node extents
-
-