toxi.geom
Class PointQuadtree

java.lang.Object
  toxi.geom.Rect
      toxi.geom.PointQuadtree

All Implemented Interfaces:

Shape2D

public class PointQuadtree
extends Rect
implements Shape2D

Implements a spatial subdivision tree to work efficiently with large numbers of 2D particles. This quadtree can only be used for particle type objects and does NOT support 2D mesh geometry as other forms of quadtree might do. For further reference also see the QuadtreeDemo in the /examples folder.

Field Summary

Fields inherited from class toxi.geom.Rect

height, width, x, y

Constructor Summary

PointQuadtree(Vec2D o, float size)
Constructs a new PointQuadtree node within the Rect: {o.x, o.y} ...

Method Summary

boolean	addAll(java.util.Collection<Vec2D> points) Adds all points of the collection to the quadtree.
boolean	addPoint(Vec2D p) Adds a new point/particle to the tree structure.
boolean	containsPoint(ReadonlyVec2D p) Checks if the given point is within the rectangle's bounds.
void	empty()
PointQuadtree[]	getChildren()
int	getDepth()
PointQuadtree	getLeafForPoint(ReadonlyVec2D p) Finds the leaf node which spatially relates to the given point
float	getMinNodeSize() Returns the minimum size of nodes (in world units).
float	getNodeSize()
int	getNumChildren()
ReadonlyVec2D	getOffset()
PointQuadtree	getParent()
java.util.List<Vec2D>	getPoints()
java.util.ArrayList<Vec2D>	getPointsWithinRect(Rect r) Selects all stored points within the given axis-aligned bounding box.
float	getSize()
boolean	remove(ReadonlyVec2D p) Removes a point from the tree and (optionally) tries to release memory by reducing now empty sub-branches.
void	removeAll(java.util.Collection<Vec2D> points)
void	setMinNodeSize(float minNodeSize)
void	setTreeAutoReduction(boolean state) Enables/disables auto reduction of branches after points have been deleted from the tree.
java.lang.String	toString()

Methods inherited from class toxi.geom.Rect

copy, fromCenterExtent, getArea, getAspect, getBottom, getBottomRight, getCentroid, getCircumference, getDimensions, getEdge, getLeft, getRight, getTop, getTopLeft, intersectsRay, intersectsRect, scale, set, set, setDimension, setPosition, toPolygon2D, union

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface toxi.geom.Shape2D

getArea, getCircumference

Constructor Detail

PointQuadtree

public PointQuadtree(Vec2D o,
                     float size)

Constructs a new PointQuadtree node within the Rect: {o.x, o.y} ... {o.x+size, o.y+size}

Parameters:

o - tree origin

size - size of the tree along a single axis

Method Detail

addAll

public boolean addAll(java.util.Collection<Vec2D> points)

Adds all points of the collection to the quadtree. IMPORTANT: Points need be of type Vec2D or have subclassed it.

Parameters:

points - point collection

Returns:

true, if all points have been added successfully.

addPoint

public boolean addPoint(Vec2D p)

Adds a new point/particle to the tree structure. All points are stored within leaf nodes only. The tree implementation is using lazy instantiation for all intermediate tree levels.

Parameters:

p -

Returns:

true, if point has been added successfully

containsPoint

public boolean containsPoint(ReadonlyVec2D p)

Description copied from class: Rect

Checks if the given point is within the rectangle's bounds.

Specified by:

containsPoint in interface Shape2D

Overrides:

containsPoint in class Rect

Parameters:

p - point to check

Returns:

true, if point is contained

empty

public void empty()

getChildren

public PointQuadtree[] getChildren()

Returns:

a copy of the child nodes array

getDepth

public int getDepth()

Returns:

the depth

getLeafForPoint

public PointQuadtree getLeafForPoint(ReadonlyVec2D p)

Finds the leaf node which spatially relates to the given point

Parameters:

p - point to check

Returns:

leaf node or null if point is outside the tree dimensions

getMinNodeSize

public float getMinNodeSize()

Returns the minimum size of nodes (in world units). This value acts as tree recursion limit since nodes smaller than this size are not subdivided further. Leaf node are always smaller or equal to this size.

Returns:

the minimum size of tree nodes

getNodeSize

public float getNodeSize()

getNumChildren

public int getNumChildren()

Returns:

the number of child nodes (max. 8)

getOffset

public ReadonlyVec2D getOffset()

Returns:

the offset

getParent

public PointQuadtree getParent()

Returns:

the parent

getPoints

public java.util.List<Vec2D> getPoints()

Returns:

the points

getPointsWithinRect

public java.util.ArrayList<Vec2D> getPointsWithinRect(Rect r)

Selects all stored points within the given axis-aligned bounding box.

Parameters:

r - clipping rect

Returns:

all points with the rect

getSize

public float getSize()

Returns:

the size

remove

public boolean remove(ReadonlyVec2D p)

Removes a point from the tree and (optionally) tries to release memory by reducing now empty sub-branches.

Parameters:

p - point to delete

Returns:

true, if the point was found & removed

removeAll

public void removeAll(java.util.Collection<Vec2D> points)

setMinNodeSize

public void setMinNodeSize(float minNodeSize)

Parameters:

minNodeSize -

setTreeAutoReduction

public void setTreeAutoReduction(boolean state)

Enables/disables auto reduction of branches after points have been deleted from the tree. Turned off by default.

Parameters:

state - true, to enable feature

toString

public java.lang.String toString()

Overrides:

toString in class Rect