Class STRtree
- All Implemented Interfaces:
Serializable
,SpatialIndex
The STR packed R-tree is simple to implement and maximizes space
utilization; that is, as many leaves as possible are filled to capacity.
Overlap between nodes is far less than in a basic R-tree.
However, the index is semi-static; once the tree has been built
(which happens automatically upon the first query), items may
not be added.
Items may be removed from the tree using remove(Envelope, Object)
.
Described in: P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With Application To GIS. Morgan Kaufmann, San Francisco, 2002.
Note that inserting items into a tree is not thread-safe. Inserting performed on more than one thread must be synchronized externally.
Querying a tree is thread-safe. The building phase is done synchronously, and querying is stateless.
- Version:
- 1.7
- See Also:
-
Nested Class Summary
Nested classes/interfaces inherited from class org.locationtech.jts.index.strtree.AbstractSTRtree
AbstractSTRtree.IntersectsOp
-
Field Summary
Fields inherited from class org.locationtech.jts.index.strtree.AbstractSTRtree
root
-
Constructor Summary
ConstructorsConstructorDescriptionSTRtree()
Constructs an STRtree with the default node capacity.STRtree
(int nodeCapacity) Constructs an STRtree with the given maximum number of child nodes that a node may have.Constructs an STRtree with the given maximum number of child nodes that a node may have, and all leaf nodes in the treeSTRtree
(int nodeCapacity, org.locationtech.jts.index.strtree.STRtree.STRtreeNode root) Constructs an STRtree with the given maximum number of child nodes that a node may have, and the root that links to all other nodes -
Method Summary
Modifier and TypeMethodDescriptionprotected AbstractNode
createNode
(int level) protected List
createParentBoundables
(List childBoundables, int newLevel) Creates the parent level for the given child level.protected List
createParentBoundablesFromVerticalSlice
(List childBoundables, int newLevel) int
depth()
Returns the number of items in the tree.protected Comparator
protected AbstractSTRtree.IntersectsOp
void
Inserts an item having the given bounds into the tree.boolean
isWithinDistance
(STRtree tree, ItemDistance itemDist, double maxDistance) Tests whether some two items from this tree and another tree lie within a given distance.nearestNeighbour
(Envelope env, Object item, ItemDistance itemDist) Finds the item in this tree which is nearest to the givenObject
, usingItemDistance
as the distance metric.Object[]
nearestNeighbour
(Envelope env, Object item, ItemDistance itemDist, int k) Finds up to k items in this tree which are the nearest neighbors to the givenitem
, usingitemDist
as the distance metric.Object[]
nearestNeighbour
(ItemDistance itemDist) Finds the two nearest items in the tree, usingItemDistance
as the distance metric.Object[]
nearestNeighbour
(STRtree tree, ItemDistance itemDist) Finds the two nearest items from this tree and another tree, usingItemDistance
as the distance metric.Returns items whose bounds intersect the given envelope.void
query
(Envelope searchEnv, ItemVisitor visitor) Returns items whose bounds intersect the given envelope.boolean
Removes a single item from the tree.int
size()
Returns the number of items in the tree.protected List[]
verticalSlices
(List childBoundables, int sliceCount) Methods inherited from class org.locationtech.jts.index.strtree.AbstractSTRtree
boundablesAtLevel, build, compareDoubles, depth, getNodeCapacity, getRoot, insert, isEmpty, itemsTree, lastNode, query, query, remove, size
-
Constructor Details
-
STRtree
public STRtree()Constructs an STRtree with the default node capacity. -
STRtree
public STRtree(int nodeCapacity) Constructs an STRtree with the given maximum number of child nodes that a node may have.The minimum recommended capacity setting is 4.
-
STRtree
public STRtree(int nodeCapacity, org.locationtech.jts.index.strtree.STRtree.STRtreeNode root) Constructs an STRtree with the given maximum number of child nodes that a node may have, and the root that links to all other nodesThe minimum recommended capacity setting is 4.
-
STRtree
Constructs an STRtree with the given maximum number of child nodes that a node may have, and all leaf nodes in the treeThe minimum recommended capacity setting is 4.
-
-
Method Details
-
createParentBoundables
Creates the parent level for the given child level. First, orders the items by the x-values of the midpoints, and groups them into vertical slices. For each slice, orders the items by the y-values of the midpoints, and group them into runs of size M (the node capacity). For each run, creates a new (parent) node.- Overrides:
createParentBoundables
in classAbstractSTRtree
-
createParentBoundablesFromVerticalSlice
-
verticalSlices
- Parameters:
childBoundables
- Must be sorted by the x-value of the envelope midpoints
-
createNode
- Specified by:
createNode
in classAbstractSTRtree
-
getIntersectsOp
- Specified by:
getIntersectsOp
in classAbstractSTRtree
- Returns:
- a test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.
- See Also:
-
insert
Inserts an item having the given bounds into the tree.- Specified by:
insert
in interfaceSpatialIndex
-
query
Returns items whose bounds intersect the given envelope.- Specified by:
query
in interfaceSpatialIndex
- Parameters:
searchEnv
- the envelope to query for- Returns:
- a list of the items found by the query
-
query
Returns items whose bounds intersect the given envelope.- Specified by:
query
in interfaceSpatialIndex
- Parameters:
searchEnv
- the envelope to query forvisitor
- a visitor object to apply to the items found
-
remove
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
-
size
public int size()Returns the number of items in the tree.- Overrides:
size
in classAbstractSTRtree
- Returns:
- the number of items in the tree
-
depth
public int depth()Returns the number of items in the tree.- Overrides:
depth
in classAbstractSTRtree
- Returns:
- the number of items in the tree
-
getComparator
- Specified by:
getComparator
in classAbstractSTRtree
-
nearestNeighbour
Finds the two nearest items in the tree, usingItemDistance
as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.If the tree is empty, the return value is
nullinvalid input: '<'/code. If the tree contains only one item, the return value is a pair containing that item. If it is required to find only pairs of distinct items, the
ItemDistance
function must be anti-reflexive.- Parameters:
itemDist
- a distance metric applicable to the items in this tree- Returns:
- the pair of the nearest items
or
null
if the tree is empty
-
nearestNeighbour
Finds the item in this tree which is nearest to the givenObject
, usingItemDistance
as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.The query object does not have to be contained in the tree, but it does have to be compatible with the itemDist distance metric.
- Parameters:
env
- the envelope of the query itemitem
- the item to find the nearest neighbour ofitemDist
- a distance metric applicable to the items in this tree and the query item- Returns:
- the nearest item in this tree
or
null
if the tree is empty
-
nearestNeighbour
Finds the two nearest items from this tree and another tree, usingItemDistance
as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search. The result value is a pair of items, the first from this tree and the second from the argument tree.- Parameters:
tree
- another treeitemDist
- a distance metric applicable to the items in the trees- Returns:
- the pair of the nearest items, one from each tree
or
null
if no pair of distinct items can be found
-
isWithinDistance
Tests whether some two items from this tree and another tree lie within a given distance.ItemDistance
is used as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.- Parameters:
tree
- another treeitemDist
- a distance metric applicable to the items in the treesmaxDistance
- the distance limit for the search- Returns:
- true if there are items within the distance
-
nearestNeighbour
Finds up to k items in this tree which are the nearest neighbors to the givenitem
, usingitemDist
as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search. This method implements the KNN algorithm described in the following paper:Roussopoulos, Nick, Stephen Kelley, and Frédéric Vincent. "Nearest neighbor queries." ACM sigmod record. Vol. 24. No. 2. ACM, 1995.
The query
item
does not have to be contained in the tree, but it does have to be compatible with theitemDist
distance metric.If the tree size is smaller than k fewer items will be returned. If the tree is empty an array of size 0 is returned.
- Parameters:
env
- the envelope of the query itemitem
- the item to find the nearest neighbours ofitemDist
- a distance metric applicable to the items in this tree and the query itemk
- the maximum number of nearest items to search for- Returns:
- an array of the nearest items found (with length between 0 and K)
-