com.vividsolutions.jts.index.strtree

Class AbstractSTRtree

Known Direct Subclasses:
SIRtree, STRtree

public abstract class AbstractSTRtree
extends java.lang.Object

Base class for STRtree and SIRtree. STR-packed R-trees are described in: P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With Application To GIS. Morgan Kaufmann, San Francisco, 2002.

This implementation is based on Boundables rather than just AbstractNodes, because the STR algorithm operates on both nodes and data, both of which are treated here as Boundables.

Version:
1.7
See Also:
STRtree, SIRtree

Nested Class Summary

protected static interface
AbstractSTRtree.IntersectsOp
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.

Field Summary

protected AbstractNode
root

Constructor Summary

AbstractSTRtree(int nodeCapacity)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have

Method Summary

protected List
boundablesAtLevel(int level)
void
build()
Creates parent nodes, grandparent nodes, and so forth up to the root node, for the data that has been inserted into the tree.
protected int
compareDoubles(double a, double b)
protected abstract AbstractNode
createNode(int level)
protected List
createParentBoundables(List childBoundables, int newLevel)
Sorts the childBoundables then divides them into groups of size M, where M is the node capacity.
protected int
depth()
protected int
depth(AbstractNode node)
protected abstract Comparator
getComparator()
protected abstract AbstractSTRtree.IntersectsOp
getIntersectsOp()
int
getNodeCapacity()
Returns the maximum number of child nodes that a node may have
protected AbstractNode
getRoot()
protected void
insert(Object bounds, Object item)
protected AbstractNode
lastNode(List nodes)
protected List
query(Object searchBounds)
Also builds the tree, if necessary.
protected void
query(Object searchBounds, ItemVisitor visitor)
Also builds the tree, if necessary.
protected boolean
remove(Object searchBounds, Object item)
Also builds the tree, if necessary.
protected int
size()
protected int
size(AbstractNode node)

Field Details

root

protected AbstractNode root

Constructor Details

AbstractSTRtree

public AbstractSTRtree(int nodeCapacity)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have

Method Details

boundablesAtLevel

protected List boundablesAtLevel(int level)

build

public void build()
Creates parent nodes, grandparent nodes, and so forth up to the root node, for the data that has been inserted into the tree. Can only be called once, and thus can be called only after all of the data has been inserted into the tree.

compareDoubles

protected int compareDoubles(double a,
                             double b)

createNode

protected abstract AbstractNode createNode(int level)

createParentBoundables

protected List createParentBoundables(List childBoundables,
                                      int newLevel)
Sorts the childBoundables then divides them into groups of size M, where M is the node capacity.

depth

protected int depth()

depth

protected int depth(AbstractNode node)

getComparator

protected abstract Comparator getComparator()

getIntersectsOp

protected abstract AbstractSTRtree.IntersectsOp getIntersectsOp()
Returns:
a test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.

getNodeCapacity

public int getNodeCapacity()
Returns the maximum number of child nodes that a node may have

getRoot

protected AbstractNode getRoot()

insert

protected void insert(Object bounds,
                      Object item)

lastNode

protected AbstractNode lastNode(List nodes)

query

protected List query(Object searchBounds)
Also builds the tree, if necessary.

query

protected void query(Object searchBounds,
                     ItemVisitor visitor)
Also builds the tree, if necessary.

remove

protected boolean remove(Object searchBounds,
                         Object item)
Also builds the tree, if necessary.

size

protected int size()

size

protected int size(AbstractNode node)