Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD