## 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 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.
`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 remove
    `item` - the item to remove
  Returns:
    `true` if the item was found

### query

    public java.util.List query(Envelope searchEnv)

  Description copied from interface: `SpatialIndex`
  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.

  Specified by:
    `query` in interface `SpatialIndex`
  Parameters:
    `searchEnv` - the envelope to query for
  Returns:
    a list of the items found by the query

### query

    public void query(Envelope searchEnv,
                      ItemVisitor visitor)

  Description copied from interface: `SpatialIndex`
  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.

  Specified by:
    `query` in interface `SpatialIndex`
  Parameters:
    `searchEnv` - the envelope to query for
    `visitor` - a visitor object to apply to the items found

### queryAll

    public java.util.List queryAll()

  Return a list of all items in the Quadtree