Package arc.math.geom

Class QuadTree<T extends QuadTree.QuadTreeObject>

java.lang.Object

arc.math.geom.QuadTree<T>

Type Parameters:

T - The type of object this quad tree should contain. An object only requires some way of getting rough bounds.

public class QuadTree<T extends QuadTree.QuadTreeObject>
extends Object

A basic quad tree.

This class represents any node, but you will likely only interact with the root node.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static interface	QuadTree.QuadTreeObject	Represents an object in a QuadTree.

Field Summary

Fields

Modifier and Type	Field	Description
QuadTree<T>	botLeft
QuadTree<T>	botRight
Rect	bounds
boolean	leaf
protected static final int	maxObjectsPerNode
Seq<T>	objects
protected final Rect	tmp
QuadTree<T>	topLeft
QuadTree<T>	topRight
int	totalObjects

Constructor Summary

Constructors

Constructor	Description
QuadTree(Rect bounds)

Method Summary

Modifier and Type	Method	Description
boolean	any(float x, float y, float width, float height)
void	clear()	Removes all objects.
protected QuadTree<T>	getFittingChild(Rect boundingBox)
void	getObjects(Seq<T> out)	Adds all quadtree objects to the specified Seq.
protected void	hitbox(T t)
void	insert(T obj)	Inserts an object into this node or its child nodes.
void	intersect(float x, float y, float width, float height, Cons<T> out)	Processes objects that may intersect the given rectangle.
void	intersect(float x, float y, float width, float height, Seq<T> out)	Fills the out parameter with any objects that may intersect the given rectangle.
void	intersect(Rect rect, Cons<T> out)	Processes objects that may intersect the given rectangle.
void	intersect(Rect toCheck, Seq<T> out)	Fills the out parameter with any objects that may intersect the given rectangle.
protected QuadTree<T>	newChild(Rect rect)
boolean	remove(T obj)	Removes an object from this node or its child nodes.
protected void	split()
protected void	unsplit()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

tmp

protected final Rect tmp

maxObjectsPerNode

protected static final int maxObjectsPerNode

See Also:

• Constant Field Values

bounds

public Rect bounds

objects

public Seq<T extends QuadTree.QuadTreeObject> objects

botLeft

public QuadTree<T extends QuadTree.QuadTreeObject> botLeft

botRight

public QuadTree<T extends QuadTree.QuadTreeObject> botRight

topLeft

public QuadTree<T extends QuadTree.QuadTreeObject> topLeft

topRight

public QuadTree<T extends QuadTree.QuadTreeObject> topRight

leaf

public boolean leaf

totalObjects

public int totalObjects

Constructor Details

QuadTree

public QuadTree(Rect bounds)

Method Details

split

protected void split()

unsplit

protected void unsplit()

insert

public void insert(T obj)

Inserts an object into this node or its child nodes. This will split a leaf node if it exceeds the object limit.

remove

public boolean remove(T obj)

Removes an object from this node or its child nodes.

clear

public void clear()

Removes all objects.

getFittingChild

protected QuadTree<T> getFittingChild(Rect boundingBox)

intersect

public void intersect(float x,
 float y,
 float width,
 float height,
 Cons<T> out)

Processes objects that may intersect the given rectangle.

This will never result in false positives.

any

public boolean any(float x,
 float y,
 float width,
 float height)

Returns:

whether an object overlaps this rectangle. This will never result in false positives.

intersect

public void intersect(Rect rect,
 Cons<T> out)

Processes objects that may intersect the given rectangle.

This will never result in false positives.

intersect

public void intersect(Rect toCheck,
 Seq<T> out)

Fills the out parameter with any objects that may intersect the given rectangle.

This will result in false positives, but never a false negative.

intersect

public void intersect(float x,
 float y,
 float width,
 float height,
 Seq<T> out)

Fills the out parameter with any objects that may intersect the given rectangle.

getObjects

public void getObjects(Seq<T> out)

Adds all quadtree objects to the specified Seq.

newChild

protected QuadTree<T> newChild(Rect rect)

hitbox

protected void hitbox(T t)