public class STRtree extends AbstractSTRtree implements SpatialIndex, java.io.Serializable
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.
Modifier and Type | Class and Description |
---|---|
private static class |
STRtree.STRtreeNode |
AbstractSTRtree.IntersectsOp
Modifier and Type | Field and 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 |
root
Constructor and Description |
---|
STRtree()
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.
|
Modifier and Type | Method and 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.
|
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(Envelope env,
java.lang.Object item,
ItemDistance itemDist)
Finds the item in this tree which is nearest to the given
Object ,
using ItemDistance 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 given
item ,
using itemDist as the distance metric. |
java.lang.Object[] |
nearestNeighbour(ItemDistance itemDist)
Finds the two nearest items in the tree,
using
ItemDistance as the distance metric. |
java.lang.Object[] |
nearestNeighbour(STRtree tree,
ItemDistance itemDist)
Finds the two nearest items from this tree
and another tree,
using
ItemDistance 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) |
boundablesAtLevel, build, compareDoubles, depth, getNodeCapacity, getRoot, insert, isEmpty, itemsTree, lastNode, query, query, remove, size
private static final long serialVersionUID
private static java.util.Comparator xComparator
private static java.util.Comparator yComparator
private static AbstractSTRtree.IntersectsOp intersectsOp
private static final int DEFAULT_NODE_CAPACITY
public STRtree()
public STRtree(int nodeCapacity)
The minimum recommended capacity setting is 4.
private static double centreX(Envelope e)
private static double centreY(Envelope e)
private static double avg(double a, double b)
protected java.util.List createParentBoundables(java.util.List childBoundables, int newLevel)
createParentBoundables
in class AbstractSTRtree
private java.util.List createParentBoundablesFromVerticalSlices(java.util.List[] verticalSlices, int newLevel)
protected java.util.List createParentBoundablesFromVerticalSlice(java.util.List childBoundables, int newLevel)
protected java.util.List[] verticalSlices(java.util.List childBoundables, int sliceCount)
childBoundables
- Must be sorted by the x-value of the envelope midpointsprotected AbstractNode createNode(int level)
createNode
in class AbstractSTRtree
protected AbstractSTRtree.IntersectsOp getIntersectsOp()
getIntersectsOp
in class AbstractSTRtree
AbstractSTRtree.IntersectsOp
public void insert(Envelope itemEnv, java.lang.Object item)
insert
in interface SpatialIndex
public java.util.List query(Envelope searchEnv)
query
in interface SpatialIndex
searchEnv
- the envelope to query forpublic void query(Envelope searchEnv, ItemVisitor visitor)
query
in interface SpatialIndex
searchEnv
- the envelope to query forvisitor
- a visitor object to apply to the items foundpublic boolean remove(Envelope itemEnv, java.lang.Object item)
remove
in interface SpatialIndex
itemEnv
- the Envelope of the item to removeitem
- the item to removetrue
if the item was foundpublic int size()
size
in class AbstractSTRtree
public int depth()
depth
in class AbstractSTRtree
protected java.util.Comparator getComparator()
getComparator
in class AbstractSTRtree
public java.lang.Object[] nearestNeighbour(ItemDistance itemDist)
ItemDistance
as the distance metric.
A Branch-and-Bound tree traversal algorithm is used
to provide an efficient search.itemDist
- a distance metric applicable to the items in this treepublic java.lang.Object[] nearestNeighbour(Envelope env, java.lang.Object item, ItemDistance itemDist, int k)
item
,
using itemDist
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 the itemDist
distance metric.
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 kNearestNeighbourpublic java.lang.Object nearestNeighbour(Envelope env, java.lang.Object item, ItemDistance itemDist)
Object
,
using ItemDistance
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.
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 itempublic java.lang.Object[] nearestNeighbour(STRtree tree, ItemDistance itemDist)
ItemDistance
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.tree
- another treeitemDist
- a distance metric applicable to the items in the treesprivate java.lang.Object[] nearestNeighbour(BoundablePair initBndPair)
private java.lang.Object[] nearestNeighbour(BoundablePair initBndPair, int k)
private java.lang.Object[] nearestNeighbour(BoundablePair initBndPair, double maxDistance)
private java.lang.Object[] nearestNeighbour(BoundablePair initBndPair, double maxDistance, int k)
private static java.lang.Object[] getItems(java.util.PriorityQueue<BoundablePair> kNearestNeighbors)