public class Quadtree extends java.lang.Object implements SpatialIndex
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.
Constructor and Description |
---|
Quadtree()
Constructs a Quadtree with zero items.
|
Modifier and Type | Method and Description |
---|---|
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,
java.lang.Object item)
Adds a spatial item with an extent specified by the given
Envelope to the index |
java.util.List |
query(Envelope searchEnv)
Queries the tree and returns items which may lie in the given search envelope.
|
void |
query(Envelope searchEnv,
ItemVisitor visitor)
Queries the tree and visits items which may lie in the given search envelope.
|
java.util.List |
queryAll()
Return a list of all items in the Quadtree
|
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.
|
public static Envelope ensureExtent(Envelope itemEnv, double minExtent)
public int depth()
public int size()
public void insert(Envelope itemEnv, java.lang.Object item)
SpatialIndex
Envelope
to the indexinsert
in interface SpatialIndex
public boolean remove(Envelope itemEnv, java.lang.Object item)
remove
in interface SpatialIndex
itemEnv
- the Envelope of the item to be removeditem
- the item to removetrue
if the item was found (and thus removed)public java.util.List query(Envelope searchEnv)
query
in interface SpatialIndex
searchEnv
- the envelope of the desired query area.public void query(Envelope searchEnv, ItemVisitor visitor)
query
in interface SpatialIndex
searchEnv
- the envelope of the desired query area.visitor
- a visitor object which is passed the visited itemspublic java.util.List queryAll()