com.vividsolutions.jts.index.strtree
Class STRtree

java.lang.Object
  com.vividsolutions.jts.index.strtree.AbstractSTRtree
      com.vividsolutions.jts.index.strtree.STRtree

All Implemented Interfaces:

SpatialIndex

public class STRtree
extends AbstractSTRtree
implements SpatialIndex

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.

Version:

1.7

Nested Class Summary

Nested classes/interfaces inherited from class com.vividsolutions.jts.index.strtree.AbstractSTRtree

AbstractSTRtree.IntersectsOp

Field Summary

Fields inherited from class com.vividsolutions.jts.index.strtree.AbstractSTRtree

root

Constructor Summary

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.

Method Summary

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)
int	depth() Returns the number of items in the tree.
protected java.util.Comparator	getComparator()
protected AbstractSTRtree.IntersectsOp	getIntersectsOp()
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 nearest item to the given object in this tree, using ItemDistance 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)

Methods inherited from class com.vividsolutions.jts.index.strtree.AbstractSTRtree

boundablesAtLevel, build, compareDoubles, depth, getNodeCapacity, getRoot, insert, itemsTree, lastNode, query, query, remove, size

Methods inherited from class java.lang.Object

clone, equals, finalize, 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.

Method Detail

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 class AbstractSTRtree

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 class AbstractSTRtree

getIntersectsOp

protected AbstractSTRtree.IntersectsOp getIntersectsOp()

Specified by:

getIntersectsOp in class AbstractSTRtree

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 interface SpatialIndex

query

public java.util.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,
                      java.lang.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.

Overrides:

size in class AbstractSTRtree

Returns:

the number of items in the tree

depth

public int depth()

Returns the number of items in the tree.

Overrides:

depth in class AbstractSTRtree

Returns:

the number of items in the tree

getComparator

protected java.util.Comparator getComparator()

Specified by:

getComparator in class AbstractSTRtree

nearestNeighbour

public java.lang.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.

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)

Finds the nearest item to the given object in this tree, using ItemDistance as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.

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

nearestNeighbour

public 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. 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