gov.sandia.cognition.math.geometry
Class Quadtree<DataType extends Vectorizable>

java.lang.Object
  extended by gov.sandia.cognition.util.AbstractCloneableSerializable
      extended by gov.sandia.cognition.math.geometry.Quadtree<DataType>
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, Serializable, Cloneable

@CodeReview(reviewer="Kevin R. Dixon",
            date="2008-12-02",
            changesNeeded=false,
            comments={"Made Quadtree and Node extend AbstractCloneableSerializable","Otherwise, class looks great!"})
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
See Also:
Serialized Form

Nested Class Summary
 class Quadtree.Node
          Represents a node in the quadtree.
 
Field Summary
static int DEFAULT_SPLIT_THRESHOLD
          This is the default minimum number of items allowed in a leaf node, 10.
protected  Rectangle2D.Double initalBounds
          The initial bounds for the tree.
protected  LinkedList<DataType> items
          All of the items in the tree.
protected  Quadtree.Node root
          The root node of the tree.
protected  int splitThreshold
          The minimum number of items allowed in a leaf node.
 
Constructor Summary
Quadtree()
          Creates a new, empty Quadtree.
Quadtree(Collection<? extends DataType> items)
          Creates a new Quadtree, populating it with the given items.
Quadtree(int splitThreshold)
          Creates a new, empty Quadtree with the given split threshold.
Quadtree(int splitThreshold, Collection<? extends DataType> items)
          Creates a new Quadtree, populating it with the given items.
Quadtree(int splitThreshold, Rectangle2D.Double initialBounds)
          Creates a new, empty Quadtree with the given split threshold.
Quadtree(Rectangle2D.Double initialBounds)
          Creates a new, empty Quadtree with the given initial bounds.
 
Method Summary
 void add(DataType item)
          Adds an item to the tree.
 void addAll(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  Rectangle2D.Double computeBounds(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.
 Quadtree.Node find(DataType item)
          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.
 Quadtree.Node find(Vector2 point)
          Locates the node in the tree that has the smallest bounding box that contains the point.
 LinkedList<DataType> findItems(Rectangle2D rectangle)
          Finds all of the items in the quadtree that are contained in the given rectangle.
 LinkedList<Quadtree.Node> findNodes(Rectangle2D 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.
 Quadtree.Node getRoot()
          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.
 
Methods inherited from class gov.sandia.cognition.util.AbstractCloneableSerializable
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.

See Also:
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 LinkedList<DataType extends Vectorizable> items
All of the items in the tree. It should never be null.


initalBounds

protected Rectangle2D.Double initalBounds
The initial bounds for the tree. This may be null if they are not specified.


root

protected Quadtree.Node root
The root node of the tree. It should never be null.

Constructor Detail

Quadtree

public Quadtree()
Creates a new, empty Quadtree.


Quadtree

public Quadtree(int splitThreshold)
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.

Quadtree

public Quadtree(Rectangle2D.Double initialBounds)
Creates a new, empty Quadtree with the given initial bounds.

Parameters:
initialBounds - The initial bounds for the quadtree.

Quadtree

public Quadtree(int splitThreshold,
                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.

Quadtree

public Quadtree(Collection<? extends DataType> items)
Creates a new Quadtree, populating it with the given items.

Parameters:
items - The initial items to populate the tree with.

Quadtree

public Quadtree(int splitThreshold,
                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

add

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.

addAll

public void addAll(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 Rectangle2D.Double computeBounds(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 LinkedList<DataType> findItems(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

public LinkedList<Quadtree.Node> findNodes(Rectangle2D 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.

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.

getRoot

public Quadtree.Node getRoot()
Gets the root node of the quadtree.

Returns:
The root node of the quadtree.