Class Quadtree

java.lang.Object
org.locationtech.jts.index.quadtree.Quadtree
All Implemented Interfaces:
Serializable, SpatialIndex

public class Quadtree extends Object implements SpatialIndex, Serializable
A Quadtree is a spatial index structure for efficient range querying of items bounded by 2D rectangles. Geometrys can be indexed by using their Envelopes. Any type of Object can also be indexed as long as it has an extent that can be represented by an Envelope.

This Quadtree index provides a primary filter for range rectangle queries. The various query methods return a list of all items which may intersect the query rectangle. Note that it may thus return items which do not in fact intersect the query rectangle. A secondary filter is required to test for actual intersection between the query rectangle and the envelope of each candidate item. The secondary filter may be performed explicitly, or it may be provided implicitly by subsequent operations executed on the items (for instance, if the index query is followed by computing a spatial predicate between the query geometry and tree items, the envelope intersection check is performed automatically.

This implementation does not require specifying the extent of the inserted items beforehand. It will automatically expand to accommodate any extent of dataset.

This data structure is also known as an MX-CIF quadtree following the terminology of Samet and others.

Version:
1.7
See Also:
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private double
    minExtent is the minimum envelope extent of all items inserted into the tree so far.
    private Root
     
    private static final long
     
  • Constructor Summary

    Constructors
    Constructor
    Description
    Constructs a Quadtree with zero items.
  • Method Summary

    Modifier and Type
    Method
    Description
    private void
     
    int
    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
    boolean
    Tests whether the index contains any items.
    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.
    Return a list of all items in the Quadtree
    boolean
    remove(Envelope itemEnv, Object item)
    Removes a single item from the tree.
    int
    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
  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      See Also:
    • root

      private Root root
    • minExtent

      private double minExtent
      minExtent is the minimum envelope extent of all items inserted into the tree so far. It is used as a heuristic value to construct non-zero envelopes for features with zero X and/or Y extent. Start with a non-zero extent, in case the first feature inserted has a zero extent in both directions. This value may be non-optimal, but only one feature will be inserted with this value.
  • Constructor Details

    • Quadtree

      public Quadtree()
      Constructs a Quadtree with zero items.
  • Method Details

    • 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.
    • isEmpty

      public boolean isEmpty()
      Tests whether the index contains any items.
      Returns:
      true if the index does not contain any items
    • 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, 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, 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 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 List queryAll()
      Return a list of all items in the Quadtree
    • collectStats

      private void collectStats(Envelope itemEnv)