public class STRtree extends AbstractSTRtree implements SpatialIndex, Serializable
The STR packed Rtree 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 Rtree.
However, the index is semistatic; 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 threadsafe. Inserting performed on more than one thread must be synchronized externally.
Querying a tree is threadsafe. The building phase is done synchronously, and querying is stateless.
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.

STRtree(int nodeCapacity,
ArrayList itemBoundables)
Constructs an STRtree with the given maximum number of child nodes that
a node may have, and all leaf nodes in the tree

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 nodes

Modifier and Type  Method and Description 

int 
depth()
Returns the number of items in the tree.

void 
insert(Envelope itemEnv,
Object item)
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.

Object 
nearestNeighbour(Envelope env,
Object item,
ItemDistance itemDist)
Finds the item in this tree which is nearest to the given
Object ,
using ItemDistance 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 given
item ,
using itemDist as the distance metric. 
Object[] 
nearestNeighbour(ItemDistance itemDist)
Finds the two nearest items in the tree,
using
ItemDistance as the distance metric. 
Object[] 
nearestNeighbour(STRtree tree,
ItemDistance itemDist)
Finds the two nearest items from this tree
and another tree,
using
ItemDistance as the distance metric. 
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,
Object item)
Removes a single item from the tree.

int 
size()
Returns the number of items in the tree.

build, getNodeCapacity, getRoot, isEmpty, itemsTree
public STRtree()
public STRtree(int nodeCapacity)
The minimum recommended capacity setting is 4.
public STRtree(int nodeCapacity, org.locationtech.jts.index.strtree.STRtree.STRtreeNode root)
The minimum recommended capacity setting is 4.
public STRtree(int nodeCapacity, ArrayList itemBoundables)
The minimum recommended capacity setting is 4.
public void insert(Envelope itemEnv, Object item)
insert
in interface SpatialIndex
public 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, 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()
public int depth()
public Object[] nearestNeighbour(ItemDistance itemDist)
ItemDistance
as the distance metric.
A BranchandBound tree traversal algorithm is used
to provide an efficient search.
If the tree is empty, the return value is null
If it is required to find only pairs of distinct items,
the
ItemDistance
function must be antireflexive.
 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
public Object nearestNeighbour(Envelope env,
Object item,
ItemDistance itemDist)
Finds the item in this tree which is nearest to the given Object
,
using ItemDistance
as the distance metric.
A BranchandBound 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 item
item
 the item to find the nearest neighbour of
itemDist
 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
public Object[] nearestNeighbour(STRtree tree,
ItemDistance itemDist)
Finds the two nearest items from this tree
and another tree,
using ItemDistance
as the distance metric.
A BranchandBound 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 tree
itemDist
 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
public boolean isWithinDistance(STRtree tree,
ItemDistance itemDist,
double maxDistance)
Tests whether some two items from this tree and another tree
lie within a given distance.
ItemDistance
is used as the distance metric.
A BranchandBound tree traversal algorithm is used
to provide an efficient search.
 Parameters:
tree
 another tree
itemDist
 a distance metric applicable to the items in the trees
maxDistance
 the distance limit for the search
 Returns:
 true if there are items within the distance

nearestNeighbour
public 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 given item
,
using itemDist
as the distance metric.
A BranchandBound 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.
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 item
item
 the item to find the nearest neighbours of
itemDist
 a distance metric applicable to the items in this tree and the query item
k
 the maximum number of nearest items to search for
 Returns:
 an array of the nearest items found (with length between 0 and K)
Copyright © 2022. All rights reserved.