com.vividsolutions.jts.index.strtree

Class STRtree

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

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 List
createParentBoundables(List childBoundables, int newLevel)
Creates the parent level for the given child level.
protected List
createParentBoundablesFromVerticalSlice(List childBoundables, int newLevel)
int
depth()
Returns the number of items in the tree.
protected Comparator
getComparator()
protected AbstractSTRtree.IntersectsOp
getIntersectsOp()
void
insert(Envelope itemEnv, Object item)
Inserts an item having the given bounds into the tree.
List
query(Envelope searchEnv)
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.
protected List[]
verticalSlices(List childBoundables, int sliceCount)

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

boundablesAtLevel, build, compareDoubles, createNode, createParentBoundables, depth, depth, getComparator, getIntersectsOp, getNodeCapacity, getRoot, insert, lastNode, query, remove, size, size

Constructor Details

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

Method Details

createNode

protected AbstractNode createNode(int level)
Overrides:
createNode in interface AbstractSTRtree

createParentBoundables

protected List createParentBoundables(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 interface AbstractSTRtree

createParentBoundablesFromVerticalSlice

protected List createParentBoundablesFromVerticalSlice(List childBoundables,
                                                       int newLevel)

depth

public int depth()
Returns the number of items in the tree.
Overrides:
depth in interface AbstractSTRtree
Returns:
the number of items in the tree

getComparator

protected Comparator getComparator()
Overrides:
getComparator in interface AbstractSTRtree

getIntersectsOp

protected AbstractSTRtree.IntersectsOp getIntersectsOp()
Overrides:
getIntersectsOp in interface AbstractSTRtree

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

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.
Overrides:
size in interface AbstractSTRtree
Returns:
the number of items in the tree

verticalSlices

protected List[] verticalSlices(List childBoundables,
                                int sliceCount)
Parameters:
childBoundables - Must be sorted by the x-value of the envelope midpoints