STRtree (org.locationtech.jts:jts-core 1.20.0 API)

java.lang.Object
- org.locationtech.jts.index.strtree.AbstractSTRtree
- - org.locationtech.jts.index.strtree.STRtree

All Implemented Interfaces:

Serializable, SpatialIndex
```
public class STRtree
extends AbstractSTRtree
implements SpatialIndex, 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, 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:

Serialized Form

Constructor Summary

Constructors
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

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`int`	`depth()` Returns the number of levels 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.

Methods inherited from class org.locationtech.jts.index.strtree.AbstractSTRtree
build, getNodeCapacity, getRoot, isEmpty, itemsTree

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - 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 nodes
    The minimum recommended capacity setting is 4.
  - STRtree
```
public 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
    The minimum recommended capacity setting is 4.
- Method Detail
  - insert
```
public void insert(Envelope itemEnv,
                   Object item)
```
    Inserts an item having the given bounds into the tree.
    
    Specified by:
    
    insert in interface SpatialIndex
  - query
```
public List query(Envelope searchEnv)
```
    Returns items whose bounds intersect the given envelope.
    
    Specified by:
    
    query in interface SpatialIndex
    
    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 interface SpatialIndex
    
    Parameters:
    
    searchEnv - the envelope to query for
    
    visitor - a visitor object to apply to the items found
  - remove
```
public boolean remove(Envelope itemEnv,
                      Object item)
```
    Removes a single item from the tree.
    
    Specified by:
    
    remove in interface SpatialIndex
    
    Parameters:
    
    itemEnv - the Envelope of the item to remove
    
    item - the item to remove
    
    Returns:
    
    true if the item was found
  - size
```
public int size()
```
    Returns the number of items in the tree.
    
    Returns:
    
    the number of items in the tree
  - depth
```
public int depth()
```
    Returns the number of levels in the tree.
    
    Returns:
    
    the number of levels in the tree
  - nearestNeighbour
```
public Object[] nearestNeighbour(ItemDistance itemDist)
```
    Finds the two nearest items in the tree, using ItemDistance 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 null 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 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 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 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 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 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 Branch-and-Bound 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 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. 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)

Class STRtree

Constructor Summary

Method Summary

Methods inherited from class org.locationtech.jts.index.strtree.AbstractSTRtree

Methods inherited from class java.lang.Object

Constructor Detail

STRtree

STRtree

STRtree

STRtree

Method Detail

insert

query

query

remove

size

depth

nearestNeighbour

nearestNeighbour

nearestNeighbour

isWithinDistance

nearestNeighbour