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.@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
Modifier and Type | Class and Description |
---|---|
class |
Quadtree.Node
Represents a node in the quadtree.
|
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 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. |
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.
|
clone
public static final int DEFAULT_SPLIT_THRESHOLD
protected int splitThreshold
protected java.util.LinkedList<DataType extends Vectorizable> items
protected java.awt.geom.Rectangle2D.Double initalBounds
protected Quadtree.Node root
public Quadtree()
Quadtree
.public Quadtree(int splitThreshold)
Quadtree
with the given split threshold.splitThreshold
- The maximum number of items allowed in a tree leaf node before
it is split. Must be positive.public Quadtree(java.awt.geom.Rectangle2D.Double initialBounds)
Quadtree
with the given initial bounds.initialBounds
- The initial bounds for the quadtree.public Quadtree(int splitThreshold, java.awt.geom.Rectangle2D.Double initialBounds)
Quadtree
with the given split threshold.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)
Quadtree
, populating it with the given items.items
- The initial items to populate the tree with.public Quadtree(int splitThreshold, java.util.Collection<? extends DataType> items)
Quadtree
, populating it with the given items.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.public void add(DataType item)
item
- The item to add to the tree.public void addAll(java.util.Collection<? extends DataType> newItems)
newItems
- The new items to add to the tree.protected void rebuild()
protected java.awt.geom.Rectangle2D.Double computeBounds(java.util.Collection<? extends DataType> items)
items
- The items to compute the bounds for.protected boolean shouldSplit(Quadtree.Node node)
node
- The node to check to see if it should be split.protected void split(Quadtree.Node node)
node
- The node to split into its two children.public Vector2 convertTo2D(DataType item)
item
- The item to convert to a two-dimensional vector.public Quadtree.Node find(DataType item)
item
- The item to find the node for.public Quadtree.Node find(Vector2 point)
point
- The point to find the node for.public Quadtree.Node find(double x, double y)
x
- The x-coordinate of the point.y
- The y-coordinate of the point.public java.util.LinkedList<DataType> findItems(java.awt.geom.Rectangle2D rectangle)
rectangle
- The rectangle to search for.public java.util.LinkedList<Quadtree.Node> findNodes(java.awt.geom.Rectangle2D rectangle)
rectangle
- The rectangle to search for.public boolean boundsContain(DataType item)
item
- The point to determine if it is the bounds.public boolean boundsContain(Vector2 point)
point
- The point to determine if it is the bounds.public boolean boundsContain(double x, double y)
x
- The x-coordinate of the point.y
- The y-coordinate of the point.public int getSplitThreshold()
public void setSplitThreshold(int splitThreshold)
splitThreshold
- The new split threshold. Must be positive.public Quadtree.Node getRoot()