Class STRtree
- java.lang.Object
-
- org.locationtech.jts.index.strtree.AbstractSTRtree
-
- org.locationtech.jts.index.strtree.STRtree
-
- All Implemented Interfaces:
java.io.Serializable
,SpatialIndex
public class STRtree extends AbstractSTRtree implements SpatialIndex, java.io.Serializable
A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. For two-dimensional spatial data.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, once the tree has been built (explicitly or on the first call to #query), items may not be added or removed.
Described in: P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With Application To GIS. Morgan Kaufmann, San Francisco, 2002.
This class is thread-safe. Building the tree is synchronized, and querying is stateless.
- Version:
- 1.7
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
STRtree.STRtreeNode
-
Nested classes/interfaces inherited from class org.locationtech.jts.index.strtree.AbstractSTRtree
AbstractSTRtree.IntersectsOp
-
-
Field Summary
Fields Modifier and Type Field Description private static int
DEFAULT_NODE_CAPACITY
private static AbstractSTRtree.IntersectsOp
intersectsOp
private static long
serialVersionUID
private static java.util.Comparator
xComparator
private static java.util.Comparator
yComparator
-
Fields inherited from class org.locationtech.jts.index.strtree.AbstractSTRtree
root
-
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private static double
avg(double a, double b)
private static double
centreX(Envelope e)
private static double
centreY(Envelope e)
protected AbstractNode
createNode(int level)
protected java.util.List
createParentBoundables(java.util.List childBoundables, int newLevel)
Creates the parent level for the given child level.protected java.util.List
createParentBoundablesFromVerticalSlice(java.util.List childBoundables, int newLevel)
private java.util.List
createParentBoundablesFromVerticalSlices(java.util.List[] verticalSlices, int newLevel)
int
depth()
Returns the number of items in the tree.protected java.util.Comparator
getComparator()
protected AbstractSTRtree.IntersectsOp
getIntersectsOp()
private static java.lang.Object[]
getItems(java.util.PriorityQueue<BoundablePair> kNearestNeighbors)
void
insert(Envelope itemEnv, java.lang.Object item)
Inserts an item having the given bounds into the tree.java.lang.Object
nearestNeighbour(Envelope env, java.lang.Object item, ItemDistance itemDist)
Finds the item in this tree which is nearest to the givenObject
, usingItemDistance
as the distance metric.java.lang.Object[]
nearestNeighbour(Envelope env, java.lang.Object item, ItemDistance itemDist, int k)
Finds k items in this tree which are the top k nearest neighbors to the givenitem
, usingitemDist
as the distance metric.private java.lang.Object[]
nearestNeighbour(BoundablePair initBndPair)
private java.lang.Object[]
nearestNeighbour(BoundablePair initBndPair, double maxDistance)
private java.lang.Object[]
nearestNeighbour(BoundablePair initBndPair, double maxDistance, int k)
private java.lang.Object[]
nearestNeighbour(BoundablePair initBndPair, int k)
java.lang.Object[]
nearestNeighbour(ItemDistance itemDist)
Finds the two nearest items in the tree, usingItemDistance
as the distance metric.java.lang.Object[]
nearestNeighbour(STRtree tree, ItemDistance itemDist)
Finds the two nearest items from this tree and another tree, usingItemDistance
as the distance metric.java.util.List
query(Envelope searchEnv)
Returns items whose bounds intersect the given envelope.void
query(Envelope searchEnv, ItemVisitor visitor)
Returns items whose bounds intersect the given envelope.boolean
remove(Envelope itemEnv, java.lang.Object item)
Removes a single item from the tree.int
size()
Returns the number of items in the tree.protected java.util.List[]
verticalSlices(java.util.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
-
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
xComparator
private static java.util.Comparator xComparator
-
yComparator
private static java.util.Comparator yComparator
-
intersectsOp
private static AbstractSTRtree.IntersectsOp intersectsOp
-
DEFAULT_NODE_CAPACITY
private static final int DEFAULT_NODE_CAPACITY
- See Also:
- Constant Field Values
-
-
Method Detail
-
centreX
private static double centreX(Envelope e)
-
centreY
private static double centreY(Envelope e)
-
avg
private static double avg(double a, double b)
-
createParentBoundables
protected java.util.List createParentBoundables(java.util.List childBoundables, int newLevel)
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
-
createParentBoundablesFromVerticalSlices
private java.util.List createParentBoundablesFromVerticalSlices(java.util.List[] verticalSlices, int newLevel)
-
createParentBoundablesFromVerticalSlice
protected java.util.List createParentBoundablesFromVerticalSlice(java.util.List childBoundables, int newLevel)
-
verticalSlices
protected java.util.List[] verticalSlices(java.util.List childBoundables, int sliceCount)
- Parameters:
childBoundables
- Must be sorted by the x-value of the envelope midpoints
-
createNode
protected AbstractNode createNode(int level)
- Specified by:
createNode
in classAbstractSTRtree
-
getIntersectsOp
protected AbstractSTRtree.IntersectsOp 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:
AbstractSTRtree.IntersectsOp
-
insert
public void insert(Envelope itemEnv, java.lang.Object item)
Inserts an item having the given bounds into the tree.- Specified by:
insert
in interfaceSpatialIndex
-
query
public java.util.List query(Envelope searchEnv)
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
public void query(Envelope searchEnv, ItemVisitor visitor)
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
public boolean remove(Envelope itemEnv, java.lang.Object item)
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
protected java.util.Comparator getComparator()
- Specified by:
getComparator
in classAbstractSTRtree
-
nearestNeighbour
public java.lang.Object[] nearestNeighbour(ItemDistance itemDist)
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.- Parameters:
itemDist
- a distance metric applicable to the items in this tree- Returns:
- the pair of the nearest items
-
nearestNeighbour
public java.lang.Object[] nearestNeighbour(Envelope env, java.lang.Object item, ItemDistance itemDist, int k)
Finds k items in this tree which are the top k 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.- 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 itemk
- the K nearest items in kNearestNeighbour- Returns:
- the K nearest items in this tree
-
nearestNeighbour
public java.lang.Object nearestNeighbour(Envelope env, java.lang.Object item, ItemDistance itemDist)
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
-
nearestNeighbour
public java.lang.Object[] nearestNeighbour(STRtree tree, ItemDistance itemDist)
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
-
nearestNeighbour
private java.lang.Object[] nearestNeighbour(BoundablePair initBndPair)
-
nearestNeighbour
private java.lang.Object[] nearestNeighbour(BoundablePair initBndPair, int k)
-
nearestNeighbour
private java.lang.Object[] nearestNeighbour(BoundablePair initBndPair, double maxDistance)
-
nearestNeighbour
private java.lang.Object[] nearestNeighbour(BoundablePair initBndPair, double maxDistance, int k)
-
getItems
private static java.lang.Object[] getItems(java.util.PriorityQueue<BoundablePair> kNearestNeighbors)
-
-