com.vividsolutions.jts.index.quadtree
Class Quadtree

java.lang.Object
  com.vividsolutions.jts.index.quadtree.Quadtree

All Implemented Interfaces:

SpatialIndex

public class Quadtree
extends java.lang.Object
implements SpatialIndex

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.

Version:

1.7

Constructor Summary

Quadtree()
Constructs a Quadtree with zero items.

Method Summary

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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Quadtree

public Quadtree()

Constructs a Quadtree with zero items.

Method Detail

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

depth

public int depth()

Returns the number of levels in the tree.

size

public int size()

Returns the number of items in the tree.

Returns:

the number of items in the tree

insert

public void insert(Envelope itemEnv,
                   java.lang.Object item)

Description copied from interface: SpatialIndex

Adds a spatial item with an extent specified by the given Envelope to the index

Specified by:

insert in interface SpatialIndex

remove

public boolean remove(Envelope itemEnv,
                      java.lang.Object item)

Removes a single item from the tree.

Specified by:

remove in interface SpatialIndex

Parameters:

itemEnv - the Envelope of the item to be removed

item - the item to remove

Returns:

true if the item was found (and thus removed)

query

public java.util.List query(Envelope searchEnv)

Queries the tree and returns items which may lie in the given search envelope. Precisely, the items that are returned are all items in the tree whose envelope may intersect the search Envelope. Note that some items with non-intersecting envelopes may be returned as well; the client is responsible for filtering these out. In most situations there will be many items in the tree which do not intersect the search envelope and which are not returned - thus providing improved performance over a simple linear scan.

Specified by:

query in interface SpatialIndex

Parameters:

searchEnv - the envelope of the desired query area.

Returns:

a List of items which may intersect the search envelope

query

public void query(Envelope searchEnv,
                  ItemVisitor visitor)

Queries the tree and visits items which may lie in the given search envelope. Precisely, the items that are visited are all items in the tree whose envelope may intersect the search Envelope. Note that some items with non-intersecting envelopes may be visited as well; the client is responsible for filtering these out. In most situations there will be many items in the tree which do not intersect the search envelope and which are not visited - thus providing improved performance over a simple linear scan.

Specified by:

query in interface SpatialIndex

Parameters:

searchEnv - the envelope of the desired query area.

visitor - a visitor object which is passed the visited items

queryAll

public java.util.List queryAll()

Return a list of all items in the Quadtree