Quadtree (Cognitive Foundry)

java.lang.Object
- gov.sandia.cognition.util.AbstractCloneableSerializable
- - 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, java.io.Serializable, java.lang.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

Nested Classes
Modifier and Type Class and Description

class Quadtree.Node
Represents a node in the quadtree.

Nested Classes
Modifier and Type	Class and Description
`class`	`Quadtree.Node` 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.
`protected java.util.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

Constructors
Constructor and Description
`Quadtree()` Creates a new, empty `Quadtree`.
`Quadtree(java.util.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, 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.
`Quadtree(java.awt.geom.Rectangle2D.Double initialBounds)` Creates a new, empty `Quadtree` with the given initial bounds.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`add(DataType item)` 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.
`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.
`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.
`java.util.LinkedList<Quadtree.Node>`	`findNodes(java.awt.geom.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 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
```
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(java.awt.geom.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,
                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.
  - 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.
  - Quadtree
```
public Quadtree(int splitThreshold,
                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
  - 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(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
```
public java.util.LinkedList<Quadtree.Node> findNodes(java.awt.geom.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.

Class Quadtree<DataType extends Vectorizable>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class gov.sandia.cognition.util.AbstractCloneableSerializable

Methods inherited from class java.lang.Object

Field Detail

DEFAULT_SPLIT_THRESHOLD

splitThreshold

items

initalBounds

root

Constructor Detail

Quadtree

Quadtree

Quadtree

Quadtree

Quadtree

Quadtree

Method Detail

add

addAll

rebuild

computeBounds

shouldSplit

split

convertTo2D

find

find

find

findItems

findNodes

boundsContain

boundsContain

boundsContain

getSplitThreshold

setSplitThreshold

getRoot