com.vividsolutions.jts.index.quadtree
Class Quadtree
java.lang.Object
com.vividsolutions.jts.index.quadtree.Quadtree
- SpatialIndex
public class Quadtree
extends java.lang.Object
A Quadtree is a spatial index structure for efficient querying
of 2D rectangles. If other kinds of spatial objects
need to be indexed they can be represented by their
envelopes
The quadtree structure is used to provide a primary filter
for range rectangle queries. The query() method returns a list of
all objects which
may intersect the query rectangle. Note that
it may return objects which do not in fact intersect.
A secondary filter is required to test for exact intersection.
Of course, this secondary filter may consist of other tests besides
intersection, such as testing other kinds of spatial relationships.
This implementation does not require specifying the extent of the inserted
items beforehand. It will automatically expand to accomodate any extent
of dataset.
This data structure is also known as an
MX-CIF quadtree
following the usage of Samet and others.
Quadtree() - Constructs a Quadtree with zero items.
|
int | depth() - Returns the number of levels in the tree.
|
static Envelope | ensureExtent(Envelope itemEnv, double minExtent) - Ensure that the envelope for the inserted item has non-zero extents.
|
void | insert(Envelope itemEnv, Object item) - Adds a spatial item with an extent specified by the given
Envelope to the index
|
List | query(Envelope searchEnv) - Queries the index for all items whose extents intersect the given search
Envelope
Note that some kinds of indexes may also return objects which do not in fact
intersect the query envelope.
|
void | query(Envelope searchEnv, ItemVisitor visitor) - Queries the index for all items whose extents intersect the given search
Envelope ,
and applies an ItemVisitor to them.
|
List | queryAll() - Return a list of all items in the Quadtree
|
boolean | remove(Envelope itemEnv, Object item) - Removes a single item from the tree.
|
int | size() - Returns the number of items in the tree.
|
Quadtree
public Quadtree()
Constructs a Quadtree with zero items.
depth
public int depth()
Returns the number of levels in the tree.
ensureExtent
public static Envelope ensureExtent(Envelope itemEnv,
double minExtent)
Ensure that the envelope for the inserted item has non-zero extents.
Use the current minExtent to pad the envelope, if necessary
query
public List query(Envelope searchEnv)
Queries the index for all items whose extents intersect the given search
Envelope
Note that some kinds of indexes may also return objects which do not in fact
intersect the query envelope.
- query in interface SpatialIndex
searchEnv
- the envelope to query for
- a list of the items found by the query
query
public void query(Envelope searchEnv,
ItemVisitor visitor)
Queries the index for all items whose extents intersect the given search
Envelope
,
and applies an
ItemVisitor
to them.
Note that some kinds of indexes may also return objects which do not in fact
intersect the query envelope.
- query in interface SpatialIndex
searchEnv
- the envelope to query forvisitor
- a visitor object to apply to the items found
queryAll
public List queryAll()
Return a list of all items in the Quadtree
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.
- the number of items in the tree