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:
Serializable
,Iterable<T>
,Collection<T>
public class QuadTree<T extends Envelope> extends Object implements Collection<T>, Serializable
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.- Author:
- Peter Knoppers
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
QuadTree.SubTree<T extends Envelope>
Sub tree of a quad tree.
-
Constructor Summary
Constructors Constructor Description QuadTree(int maximumLoad, double minimumSize, double left, double bottom, double right, double top)
Create a new QuadTree object (or a sub-tree).
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(T e)
boolean
addAll(Collection<? extends T> c)
void
clear()
boolean
contains(Object o)
boolean
containsAll(Collection<?> c)
String
dump(String indent)
Dump a quad tree.int
getMaxLoad()
Return the number of objects at which it is time to try to re-balance.double
getMinimumSize()
Return the minimum sub-tree rectangle size.int
getSubTreeCount()
Return the total number of sub trees.(package private) void
incrementSubTreeCount()
Increment the number of sub trees created.boolean
isEmpty()
Iterator<T>
iterator()
Iterator<T>
iterator(Rectangle searchArea)
Find all elements intersecting a given bounding box.boolean
remove(Object o)
boolean
removeAll(Collection<?> c)
boolean
retainAll(Collection<?> c)
int
size()
Object[]
toArray()
<T> T[]
toArray(T[] a)
String
toString()
String
toString(int expandDepth)
Make a textual description of this quad tree drilling down to the prescribed depth.-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface java.util.Collection
equals, hashCode, parallelStream, removeIf, spliterator, stream, toArray
-
-
-
-
Constructor Detail
-
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
- int; number of elements at any level that warrants investigating if the tree can be re-balancedminimumSize
- double; minimum width or height of a sub tree Rectangle (smaller sub tree are never created)left
- double; the lowest X-coordinate that is allowed (inclusive)bottom
- double; the lowest Y-coordinate that is allowed (inclusive)right
- double; the highest X-coordinate that is allowed (exclusive)top
- double; the highest Y-coordinate that is allowed (exclusive)
-
-
Method Detail
-
getMaxLoad
public int getMaxLoad()
Return the number of objects at which it is time to try to re-balance.- Returns:
- int; 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:
- double; the minimum sub-tree rectangle size
-
size
public int size()
- Specified by:
size
in interfaceCollection<T extends Envelope>
-
isEmpty
public boolean isEmpty()
- Specified by:
isEmpty
in interfaceCollection<T extends Envelope>
-
contains
public boolean contains(Object o)
- Specified by:
contains
in interfaceCollection<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
- Rectangle; the bounding box- Returns:
- Iterator<T>; iterator that returns all elements that intersect the given bounding box
-
toArray
public Object[] toArray()
- Specified by:
toArray
in interfaceCollection<T extends Envelope>
-
toArray
public <T> T[] toArray(T[] a)
- Specified by:
toArray
in interfaceCollection<T extends Envelope>
-
add
public boolean add(T e)
- Specified by:
add
in interfaceCollection<T extends Envelope>
-
remove
public boolean remove(Object o)
- Specified by:
remove
in interfaceCollection<T extends Envelope>
-
containsAll
public boolean containsAll(Collection<?> c)
- Specified by:
containsAll
in interfaceCollection<T extends Envelope>
-
addAll
public boolean addAll(Collection<? extends T> c)
- Specified by:
addAll
in interfaceCollection<T extends Envelope>
-
removeAll
public boolean removeAll(Collection<?> c)
- Specified by:
removeAll
in interfaceCollection<T extends Envelope>
-
retainAll
public boolean retainAll(Collection<?> c)
- Specified by:
retainAll
in interfaceCollection<T extends Envelope>
-
clear
public void clear()
- Specified by:
clear
in interfaceCollection<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:
- int; the total number of sub trees
-
toString
public String toString(int expandDepth)
Make a textual description of this quad tree drilling down to the prescribed depth.- Parameters:
expandDepth
- int; maximum depth to descend- Returns:
- String; textual description of this quad tree
-
-