gov.sandia.cognition.math.geometry
Class Quadtree.Node

java.lang.Object
  extended by gov.sandia.cognition.util.AbstractCloneableSerializable
      extended by gov.sandia.cognition.math.geometry.Quadtree.Node
All Implemented Interfaces:
CloneableSerializable, Serializable, Cloneable
Enclosing class:
Quadtree<DataType extends Vectorizable>

public class Quadtree.Node
extends AbstractCloneableSerializable

Represents a node in the quadtree.

See Also:
Serialized Form

Field Summary
protected  Rectangle2D.Double bounds
          The two-dimensional bounds for this node.
protected  ArrayList<Quadtree.Node> children
          The list of children for this node.
protected  int depth
          The depth of this node in the tree.
protected  LinkedList<DataType> localItems
          The local items stored at this node.
protected  Quadtree.Node lowerLeft
          The child for the lower-left quadrant of this node.
protected  Quadtree.Node lowerRight
          The child for the lower-right quadrant of this node.
protected  Quadtree.Node parent
          The parent of this node in the tree.
protected  Quadtree.Node upperLeft
          The child for the upper-left quadrant of this node.
protected  Quadtree.Node upperRight
          The child for the upper-right quadrant of this node.
 
Constructor Summary
Quadtree.Node(Quadtree.Node parent, Rectangle2D.Double bounds)
          Creates a new Node with the given parent and region bounds.
 
Method Summary
 boolean areLocalItemsSame()
          Returns true if this is a leaf and all the local items are the same.
 boolean boundsContain(double x, double y)
          Returns true if the given point is within the bounds of this node.
 boolean boundsContain(Point2D point)
          Returns true if the given point is within the bounds of this node.
 boolean boundsContain(Rectangle2D rectangle)
          Returns true if the given rectangle is completely within the bounds of this node.
 boolean boundsContain(Vector2 point)
          Returns true if the given point is within the bounds of this node.
 boolean boundsOverlap(Rectangle2D rectangle)
          Returns true if the given rectangle intersects the bounds for this node.
 Quadtree.Node findChild(DataType item)
          Finds the child corresponding to the given point.
 Quadtree.Node findChild(double x, double y)
          Finds the child corresponding to the given point.
 Quadtree.Node findChild(Vector2 point)
          Finds the child corresponding to the given point.
 void findItems(Rectangle2D rectangle, LinkedList<DataType> result)
          Finds all of the items that fall within the region defined by this node (and its children) and adds it to the given list.
 Rectangle2D.Double getBounds()
          Gets the bounding box of the region represented by this node.
 List<Quadtree.Node> getChildren()
          Gets the children of this node.
 int getDepth()
          The depth in the tree that this node exists at.
 Collection<DataType> getItems()
          Gets the collection of items contained in this node and all subnodes.
 int getLocalCount()
          Gets the number of items that are locally contained at the node.
 LinkedList<DataType> getLocalItems()
          Gets the list of items stored locally at the node in the tree.
 Quadtree.Node getLowerLeft()
          Gets the child representing lower-left quadrant of the node, when treating the 2D coordinate grid in a mathematical representation (positive x values go left and positive y values go up).
 Quadtree.Node getLowerRight()
          Gets the child representing lower-right quadrant of the node, when treating the 2D coordinate grid in a mathematical representation (positive x values go left and positive y values go up).
 Quadtree.Node getParent()
          Gets the parent node of this node.
 Quadtree.Node getUpperLeft()
          Gets the child representing upper-left quadrant of the node, when treating the 2D coordinate grid in a mathematical representation (positive x values go left and positive y values go up).
 Quadtree.Node getUpperRight()
          Gets the child representing upper-right quadrant of the node, when treating the 2D coordinate grid in a mathematical representation (positive x values go left and positive y values go up).
 boolean isEmpty()
          Returns true if this is a leaf node and has no items in it.
 boolean isInBounds(DataType item)
          Returns true if the given point is within the bounds of this node.
 boolean isLeaf()
          Returns true if this node is a leaf node, which means it has no children.
protected  void setBounds(Rectangle2D.Double bounds)
          Sets the bounding box of the region represented by this node.
protected  void setChildren(ArrayList<Quadtree.Node> children)
          Sets the list of child nodes of this node.
protected  void setDepth(int depth)
          Sets the depth in the tree of this node.
protected  void setLocalItems(LinkedList<DataType> localItems)
          Gets the list of items stored locally at the node in the tree.
protected  void setLowerLeft(Quadtree.Node lowerLeft)
          Sets the lower-left child.
protected  void setLowerRight(Quadtree.Node lowerRight)
          Sets the lower-right child.
protected  void setParent(Quadtree.Node parent)
          Sets the parent node of this node.
protected  void setUpperLeft(Quadtree.Node upperLeft)
          Sets the upper-left child.
protected  void setUpperRight(Quadtree.Node upperRight)
          Sets the upper-right child.
 
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

parent

protected Quadtree.Node parent
The parent of this node in the tree. Null only for the root node.


bounds

protected Rectangle2D.Double bounds
The two-dimensional bounds for this node. This is only null if it is the root node and has no elements and no default bounds.


depth

protected int depth
The depth of this node in the tree.


localItems

protected LinkedList<DataType extends Vectorizable> localItems
The local items stored at this node.


lowerRight

protected Quadtree.Node lowerRight
The child for the lower-right quadrant of this node.


lowerLeft

protected Quadtree.Node lowerLeft
The child for the lower-left quadrant of this node.


upperLeft

protected Quadtree.Node upperLeft
The child for the upper-left quadrant of this node.


upperRight

protected Quadtree.Node upperRight
The child for the upper-right quadrant of this node.


children

protected ArrayList<Quadtree.Node> children
The list of children for this node. Null to indicate that it has no children and thus is a leaf node.

Constructor Detail

Quadtree.Node

public Quadtree.Node(Quadtree.Node parent,
                     Rectangle2D.Double bounds)
Creates a new Node with the given parent and region bounds.

Parameters:
parent - The parent node. Null for the root node.
bounds - The bounding rectangle for the region the node represents.
Method Detail

isInBounds

public boolean isInBounds(DataType item)
Returns true if the given point is within the bounds of this node.

Parameters:
item - The point.
Returns:
True if-and-only-if the point is in the bounds of this node.

boundsContain

public boolean boundsContain(Vector2 point)
Returns true if the given point is within the bounds of this node.

Parameters:
point - The point.
Returns:
True if-and-only-if the point is in the bounds of this node.

boundsContain

public boolean boundsContain(Point2D point)
Returns true if the given point is within the bounds of this node.

Parameters:
point - The point.
Returns:
True if-and-only-if the point is in the bounds of this node.

boundsContain

public boolean boundsContain(double x,
                             double y)
Returns true if the given point is within the bounds of this node.

Parameters:
x - The x-coordinate of the point.
y - The y-coordinate of the point.
Returns:
True if-and-only-if the point is in the bounds of this node.

boundsContain

public boolean boundsContain(Rectangle2D rectangle)
Returns true if the given rectangle is completely within the bounds of this node.

Parameters:
rectangle - The rectangle to test.
Returns:
True if-and-only-if the given rectangle is within the bounds of this rectangle.

boundsOverlap

public boolean boundsOverlap(Rectangle2D rectangle)
Returns true if the given rectangle intersects the bounds for this node.

Parameters:
rectangle - The rectangle to test.
Returns:
True if-and-only-if the given rectangle intersects with the bounds of this node.

findChild

public Quadtree.Node findChild(DataType item)
Finds the child corresponding to the given point. Note that if the point is outide the bounds of the node, it will still return a child node, because it just compares to the splitting planes in the node for efficiency.

Parameters:
item - The item to query.
Returns:
The node that most closely matches the given point.

findChild

public Quadtree.Node findChild(Vector2 point)
Finds the child corresponding to the given point. Note that if the point is outide the bounds of the node, it will still return a child node, because it just compares to the splitting planes in the node for efficiency.

Parameters:
point - The point to query.
Returns:
The node that most closely matches the given point.

findChild

public Quadtree.Node findChild(double x,
                               double y)
Finds the child corresponding to the given point. Note that if the point is outide the bounds of the node, it will still return a child node, because it just compares to the splitting planes in the node for efficiency.

Parameters:
x - The x-coordinate to query.
y - The y-coordinate to query.
Returns:
The node that most closely matches the given point.

findItems

public void findItems(Rectangle2D rectangle,
                      LinkedList<DataType> result)
Finds all of the items that fall within the region defined by this node (and its children) and adds it to the given list.

Parameters:
rectangle - The rectangle to search in.
result - The result list to put the items in.

areLocalItemsSame

public boolean areLocalItemsSame()
Returns true if this is a leaf and all the local items are the same.

Returns:
True if the local items are the same.

getItems

public Collection<DataType> getItems()
Gets the collection of items contained in this node and all subnodes.

Returns:
The collection of items contained in this node and all subnodes.

getChildren

public List<Quadtree.Node> getChildren()
Gets the children of this node.

Returns:
The children of this node.

isEmpty

public boolean isEmpty()
Returns true if this is a leaf node and has no items in it.

Returns:
True if this is a leaf node and has no items in it.

isLeaf

public boolean isLeaf()
Returns true if this node is a leaf node, which means it has no children.

Returns:
True if-and-only-if this is a leaf node.

getLocalCount

public int getLocalCount()
Gets the number of items that are locally contained at the node. This does not count items at child nodes. For non-leaf nodes, this should be zero.

Returns:
The number of items locally at the node.

getDepth

public int getDepth()
The depth in the tree that this node exists at. The root starts at depth 0.

Returns:
The depth in the tree of this node.

setDepth

protected void setDepth(int depth)
Sets the depth in the tree of this node.

Parameters:
depth - The new depth in the tree for the node.

getParent

public Quadtree.Node getParent()
Gets the parent node of this node. This is only null if it is a root node.

Returns:
The parent node of this node.

setParent

protected void setParent(Quadtree.Node parent)
Sets the parent node of this node. It should only be null if this is the root node.

Parameters:
parent - The parent node of this node.

getBounds

public Rectangle2D.Double getBounds()
Gets the bounding box of the region represented by this node.

Returns:
The bounding box of the region represented by this node.

setBounds

protected void setBounds(Rectangle2D.Double bounds)
Sets the bounding box of the region represented by this node.

Parameters:
bounds - The bounding box of the region represented by this node.

getLocalItems

public LinkedList<DataType> getLocalItems()
Gets the list of items stored locally at the node in the tree.

Returns:
The local items stored at the node.

setLocalItems

protected void setLocalItems(LinkedList<DataType> localItems)
Gets the list of items stored locally at the node in the tree.

Parameters:
localItems - The local items stored at the node.

getLowerLeft

public Quadtree.Node getLowerLeft()
Gets the child representing lower-left quadrant of the node, when treating the 2D coordinate grid in a mathematical representation (positive x values go left and positive y values go up).

Returns:
The child representing the lower-left quadrant of the node.

setLowerLeft

protected void setLowerLeft(Quadtree.Node lowerLeft)
Sets the lower-left child.

Parameters:
lowerLeft - The lower-left child.

getLowerRight

public Quadtree.Node getLowerRight()
Gets the child representing lower-right quadrant of the node, when treating the 2D coordinate grid in a mathematical representation (positive x values go left and positive y values go up).

Returns:
The child representing the lower-right quadrant of the node.

setLowerRight

protected void setLowerRight(Quadtree.Node lowerRight)
Sets the lower-right child.

Parameters:
lowerRight - The lower-right child.

getUpperLeft

public Quadtree.Node getUpperLeft()
Gets the child representing upper-left quadrant of the node, when treating the 2D coordinate grid in a mathematical representation (positive x values go left and positive y values go up).

Returns:
The child representing the upper-left quadrant of the node.

setUpperLeft

protected void setUpperLeft(Quadtree.Node upperLeft)
Sets the upper-left child.

Parameters:
upperLeft - The upper-left child.

getUpperRight

public Quadtree.Node getUpperRight()
Gets the child representing upper-right quadrant of the node, when treating the 2D coordinate grid in a mathematical representation (positive x values go left and positive y values go up).

Returns:
The child representing the upper-right quadrant of the node.

setUpperRight

protected void setUpperRight(Quadtree.Node upperRight)
Sets the upper-right child.

Parameters:
upperRight - The upper-right child.

setChildren

protected void setChildren(ArrayList<Quadtree.Node> children)
Sets the list of child nodes of this node. It should only be the four defined children that have pointers.

Parameters:
children - The list of child nodes of this node.