com.vividsolutions.jts.index.strtree
Class STRtree
- 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.
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
|
boundablesAtLevel , build , compareDoubles , createNode , createParentBoundables , depth , depth , getComparator , getIntersectsOp , getNodeCapacity , getRoot , insert , lastNode , query , query , remove , size , size |
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
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.
- createParentBoundables in interface AbstractSTRtree
createParentBoundablesFromVerticalSlice
protected List createParentBoundablesFromVerticalSlice(List childBoundables,
int newLevel)
depth
public int depth()
Returns the number of items in the tree.
- depth in interface AbstractSTRtree
- the number of items in the tree
insert
public void insert(Envelope itemEnv,
Object item)
Inserts an item having the given bounds into the tree.
- insert in interface SpatialIndex
query
public List query(Envelope searchEnv)
Returns items whose bounds intersect the given envelope.
- query in interface SpatialIndex
remove
public boolean remove(Envelope itemEnv,
Object item)
Removes a single item from the tree.
- remove in interface SpatialIndex
itemEnv
- the Envelope of the item to removeitem
- the item to remove
true
if the item was found
size
public int size()
Returns the number of items in the tree.
- size in interface AbstractSTRtree
- the number of items in the tree
verticalSlices
protected List[] verticalSlices(List childBoundables,
int sliceCount)
childBoundables
- Must be sorted by the x-value of the envelope midpoints