Package org.djutils.quadtree

Class QuadTree<T extends Envelope>

java.lang.Object
org.djutils.quadtree.QuadTree<T>
Type Parameters:
T - Type of object stored in this quad tree
All Implemented Interfaces:
Iterable<T>, Collection<T>
public class QuadTree<T extends Envelope> extends Object implements Collection<T>
Quad tree for 2D objects. For now, this implementation needs an ultimate outer bounding box. No part of any 2D string object may exceed that bounding box. A link to each stored 2D object will be stored in each sub-box that it intersects.

Copyright (c) 2019-2025 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
BSD-style license. See DJUTILS License.

Author:
Peter Knoppers

  • Constructor Details

    • QuadTree

      public QuadTree(int maximumLoad, double minimumSize, double left, double bottom, double right, double top)
      Create a new QuadTree object (or a sub-tree).
      Parameters:
      maximumLoad - number of elements at any level that warrants investigating if the tree can be re-balanced
      minimumSize - minimum width or height of a sub tree Rectangle (smaller sub tree are never created)
      left - the lowest X-coordinate that is allowed (inclusive)
      bottom - the lowest Y-coordinate that is allowed (inclusive)
      right - the highest X-coordinate that is allowed (exclusive)
      top - the highest Y-coordinate that is allowed (exclusive)

  • Method Details

    • getMaxLoad

      public int getMaxLoad()
      Return the number of objects at which it is time to try to re-balance.
      Returns:
      the number of objects at which it is time to try to re-balance

    • getMinimumSize

      public double getMinimumSize()
      Return the minimum sub-tree rectangle size.
      Returns:
      the minimum sub-tree rectangle size

    • size

      public int size()
      Specified by:
      size in interface Collection<T extends Envelope>

    • isEmpty

      public boolean isEmpty()
      Specified by:
      isEmpty in interface Collection<T extends Envelope>

    • contains

      public boolean contains(Object o)
      Specified by:
      contains in interface Collection<T extends Envelope>

    • iterator

      public Iterator<T> iterator()
      Specified by:
      iterator in interface Collection<T extends Envelope>
      Specified by:
      iterator in interface Iterable<T extends Envelope>

    • iterator

      public Iterator<T> iterator(Rectangle searchArea)
      Find all elements intersecting a given bounding box. This iterator cannot be used to remove elements, but the remove method can be safely called while the iterator is active.
      Parameters:
      searchArea - the bounding box
      Returns:
      iterator that returns all elements that intersect the given bounding box

    • toArray

      public Object[] toArray()
      Specified by:
      toArray in interface Collection<T extends Envelope>

    • toArray

      public <T> T[] toArray(T[] a)
      Specified by:
      toArray in interface Collection<T extends Envelope>

    • add

      public boolean add(T e)
      Specified by:
      add in interface Collection<T extends Envelope>

    • remove

      public boolean remove(Object o)
      Specified by:
      remove in interface Collection<T extends Envelope>

    • containsAll

      public boolean containsAll(Collection<?> c)
      Specified by:
      containsAll in interface Collection<T extends Envelope>

    • addAll

      public boolean addAll(Collection<? extends T> c)
      Specified by:
      addAll in interface Collection<T extends Envelope>

    • removeAll

      public boolean removeAll(Collection<?> c)
      Specified by:
      removeAll in interface Collection<T extends Envelope>

    • retainAll

      public boolean retainAll(Collection<?> c)
      Specified by:
      retainAll in interface Collection<T extends Envelope>

    • clear

      public void clear()
      Specified by:
      clear in interface Collection<T extends Envelope>

    • incrementSubTreeCount

      void incrementSubTreeCount()
      Increment the number of sub trees created.

    • getSubTreeCount

      public int getSubTreeCount()
      Return the total number of sub trees.
      Returns:
      the total number of sub trees

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • toString

      public String toString(int expandDepth)
      Make a textual description of this quad tree drilling down to the prescribed depth.
      Parameters:
      expandDepth - maximum depth to descend
      Returns:
      textual description of this quad tree

    • dump

      public String dump(String indent)
      Dump a quad tree.
      Parameters:
      indent - prefix for each output line
      Returns:
      textual description of this quad tree.