gov.sandia.cognition.math.geometry

## Class Quadtree<DataType extends Vectorizable>

• Type Parameters:
DataType - The type of data that is to be stored in the tree. It must be able to be converted to a two-dimensional vector via the Vectorizable interface.
All Implemented Interfaces:
CloneableSerializable, java.io.Serializable, java.lang.Cloneable

@CodeReview(reviewer="Kevin R. Dixon",
date="2008-12-02",
changesNeeded=false,
public class Quadtree<DataType extends Vectorizable>
extends AbstractCloneableSerializable
Implements the quadtree region-partitioning algorithm and data structure. The quadtree works on two-dimensional data by building a tree over the data. Each node in the tree represents a square region of the data. Each interior node contains four children, corresponding to the four equal-sized quadrants of the node (hence the name quadtree). All of the data items are contained at the leaves of the tree. The algorithm maintains a threshold of the maximum number of items allowed in a leaf node. If a node exceeds that limit, then it is split into its four quadrants.
Since:
2.1
Author:
Justin Basilico
Serialized Form
• ### Nested Class Summary

Nested Classes
Modifier and Type Class and Description
Represents a node in the quadtree.
• ### Field Summary

Fields
Modifier and Type Field and Description
static int DEFAULT_SPLIT_THRESHOLD
This is the default minimum number of items allowed in a leaf node, 10.
protected java.awt.geom.Rectangle2D.Double initalBounds
The initial bounds for the tree.
All of the items in the tree.
The root node of the tree.
protected int splitThreshold
The minimum number of items allowed in a leaf node.
• ### Constructor Summary

Constructors
Constructor and Description
Creates a new, empty Quadtree.
Quadtree(java.util.Collection<? extends DataType> items)
Creates a new Quadtree, populating it with the given items.
Creates a new, empty Quadtree with the given split threshold.
Quadtree(int splitThreshold, java.util.Collection<? extends DataType> items)
Creates a new Quadtree, populating it with the given items.
Quadtree(int splitThreshold, java.awt.geom.Rectangle2D.Double initialBounds)
Creates a new, empty Quadtree with the given split threshold.
Creates a new, empty Quadtree with the given initial bounds.
• ### Method Summary

All Methods
Modifier and Type Method and Description
Adds an item to the tree.
void addAll(java.util.Collection<? extends DataType> newItems)
Adds all the items to the
boolean boundsContain(DataType item)
Determines if the given point is within the bounds of the quadtree.
boolean boundsContain(double x, double y)
Determines if the given point is within the bounds of the quadtree.
boolean boundsContain(Vector2 point)
Determines if the given point is within the bounds of the quadtree.
protected java.awt.geom.Rectangle2D.Double computeBounds(java.util.Collection<? extends DataType> items)
Computes the bounding rectangle of a given collection of points.
Vector2 convertTo2D(DataType item)
Converts the given item into a two-dimensional vector.
Locates the node in the tree that has the smallest bounding box that contains the item.
Quadtree.Node find(double x, double y)
Locates the node in the tree that has the smallest bounding box that contains the point.
Locates the node in the tree that has the smallest bounding box that contains the point.
Finds all of the items in the quadtree that are contained in the given rectangle.
Finds the list of nodes that overlap with the given rectangle, chosing the highest-level nodes in the tree that are contained in the rectangle.
Gets the root node of the quadtree.
int getSplitThreshold()
Gets the split threshold for the tree.
protected void rebuild()
Rebuilds the entire quadtree.
void setSplitThreshold(int splitThreshold)
Sets the split threshold for the node.
protected boolean shouldSplit(Quadtree.Node node)
Determines if a given node should be split.
protected void split(Quadtree.Node node)
Splits the given node.

clone
• ### Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Field Detail

• #### DEFAULT_SPLIT_THRESHOLD

public static final int DEFAULT_SPLIT_THRESHOLD
This is the default minimum number of items allowed in a leaf node, 10.
Constant Field Values
• #### splitThreshold

protected int splitThreshold
The minimum number of items allowed in a leaf node. If there are more than this, then a node must be split. This number must be greater than zero.
• #### items

protected java.util.LinkedList<DataType extends Vectorizable> items
All of the items in the tree. It should never be null.
• #### initalBounds

protected java.awt.geom.Rectangle2D.Double initalBounds
The initial bounds for the tree. This may be null if they are not specified.
• #### root

The root node of the tree. It should never be null.
• ### Constructor Detail

Creates a new, empty Quadtree.

Creates a new, empty Quadtree with the given split threshold.
Parameters:
splitThreshold - The maximum number of items allowed in a tree leaf node before it is split. Must be positive.

Creates a new, empty Quadtree with the given initial bounds.
Parameters:
initialBounds - The initial bounds for the quadtree.

java.awt.geom.Rectangle2D.Double initialBounds)
Creates a new, empty Quadtree with the given split threshold.
Parameters:
splitThreshold - The maximum number of items allowed in a tree leaf node before it is split. Must be positive.
initialBounds - The initial bounds for the quadtree.

public Quadtree(java.util.Collection<? extends DataType> items)
Creates a new Quadtree, populating it with the given items.
Parameters:
items - The initial items to populate the tree with.

java.util.Collection<? extends DataType> items)
Creates a new Quadtree, populating it with the given items.
Parameters:
splitThreshold - The maximum number of items allowed in a tree leaf node before it is split. Must be positive.
items - The initial items to populate the tree with.
• ### Method Detail

public void add(DataType item)
Adds an item to the tree. If the item is outside the current bounds of the tree, it will rebuild the tree to fit the new item.
Parameters:
item - The item to add to the tree.

public void addAll(java.util.Collection<? extends DataType> newItems)
Adds all the items to the
Parameters:
newItems - The new items to add to the tree.
• #### rebuild

protected void rebuild()
Rebuilds the entire quadtree. It destroys the current root node and then repopulates the tree from the current list of items for the tree.
• #### computeBounds

protected java.awt.geom.Rectangle2D.Double computeBounds(java.util.Collection<? extends DataType> items)
Computes the bounding rectangle of a given collection of points. This takes into account the initial bounds of the quadtree, fi they are specified.
Parameters:
items - The items to compute the bounds for.
Returns:
The minimum bounding rectangle for the given items.
• #### shouldSplit

protected boolean shouldSplit(Quadtree.Node node)
Determines if a given node should be split. This is done according to the split threshold.
Parameters:
node - The node to check to see if it should be split.
Returns:
True if the node should be split and false otherwise.
• #### split

protected void split(Quadtree.Node node)
Splits the given node. This is the real meat of the algorithm.
Parameters:
node - The node to split into its two children.
• #### convertTo2D

public Vector2 convertTo2D(DataType item)
Converts the given item into a two-dimensional vector. It throws an illegal argument exception
Parameters:
item - The item to convert to a two-dimensional vector.
Returns:
The two-dimenaional vector version of the item.
• #### find

public Quadtree.Node find(DataType item)
Locates the node in the tree that has the smallest bounding box that contains the item.
Parameters:
item - The item to find the node for.
Returns:
The node with the smallest bounding box that contains the item.
• #### find

public Quadtree.Node find(Vector2 point)
Locates the node in the tree that has the smallest bounding box that contains the point.
Parameters:
point - The point to find the node for.
Returns:
The node with the smallest bounding box that contains the point.
• #### find

public Quadtree.Node find(double x,
double y)
Locates the node in the tree that has the smallest bounding box that contains the point.
Parameters:
x - The x-coordinate of the point.
y - The y-coordinate of the point.
Returns:
The node with the smallest bounding box that contains the point.
• #### findItems

public java.util.LinkedList<DataType> findItems(java.awt.geom.Rectangle2D rectangle)
Finds all of the items in the quadtree that are contained in the given rectangle.
Parameters:
rectangle - The rectangle to search for.
Returns:
The items in the quad tree that fit in the given rectangle.
• #### findNodes

Finds the list of nodes that overlap with the given rectangle, chosing the highest-level nodes in the tree that are contained in the rectangle.
Parameters:
rectangle - The rectangle to search for.
Returns:
The list of the highest-level nodes that are contained in the given rectangle plus the leaves that intersect the rectangle.
• #### boundsContain

public boolean boundsContain(DataType item)
Determines if the given point is within the bounds of the quadtree.
Parameters:
item - The point to determine if it is the bounds.
Returns:
True if the given point is in the bounds of the quadtree; otherwise, false.
• #### boundsContain

public boolean boundsContain(Vector2 point)
Determines if the given point is within the bounds of the quadtree.
Parameters:
point - The point to determine if it is the bounds.
Returns:
True if the given point is in the bounds of the quadtree; otherwise, false.
• #### boundsContain

public boolean boundsContain(double x,
double y)
Determines if the given point is within the bounds of the quadtree.
Parameters:
x - The x-coordinate of the point.
y - The y-coordinate of the point.
Returns:
True if the given point is in the bounds of the quadtree; otherwise, false.
• #### getSplitThreshold

public int getSplitThreshold()
Gets the split threshold for the tree. This is the maximum number of items that are allowed in a leaf node.
Returns:
The split threshold for a node in the tree.
• #### setSplitThreshold

public void setSplitThreshold(int splitThreshold)
Sets the split threshold for the node. If this changes threshold, then the tree is rebuilt.
Parameters:
splitThreshold - The new split threshold. Must be positive.