# Class DynamicTree

java.lang.Object
com.codename1.gaming.physics.box2d.collision.broadphase.DynamicTree

All Implemented Interfaces:
  `BroadPhaseStrategy`

public class DynamicTree extends Object implements BroadPhaseStrategy
A dynamic tree arranges data in a binary tree to accelerate queries such as volume queries and ray casts. Leafs are proxies with an AABB. In the tree we expand the proxy AABB by _fatAABBFactor so that the proxy AABB is bigger than the client object. This allows the client object to move by small amounts without triggering a tree update.

- ## Nested Class Summary

  Nested Classes
  Modifier and Type
  Class
  Description
  `class`
  `DynamicTree.TreeNodeStack`

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `static final int`
  `MAX_STACK_SIZE`
  `static final int`
  `NULL_NODE`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `DynamicTree()`

- ## Method Summary

  Modifier and Type
  Method
  Description
  `final int`
  `computeHeight()`
  Compute the height of the tree.
  `final int`
  `createProxy(AABB aabb, Object userData)`
  Create a proxy.
  `final void`
  `destroyProxy(int proxyId)`
  Destroy a proxy
  `void`
  `drawTree(DebugDraw argDraw)`
  `void`
  `drawTree(DebugDraw argDraw, DynamicTreeNode node, int spot, int height)`
  `float`
  `getAreaRatio()`
  Get the ratio of the sum of the node areas to the root area.
  `final AABB`
  `getFatAABB(int proxyId)`
  `int`
  `getHeight()`
  Compute the height of the binary tree in O(N) time.
  `int`
  `getInsertionCount()`
  `int`
  `getMaxBalance()`
  Get the maximum balance of an node in the tree.
  `final Object`
  `getUserData(int proxyId)`
  `final boolean`
  `moveProxy(int proxyId, AABB aabb, Vec2 displacement)`
  Move a proxy with a swepted AABB.
  `final void`
  `query(TreeCallback callback, AABB aabb)`
  Query an AABB for overlapping proxies.
  `void`
  `raycast(TreeRayCastCallback callback, RayCastInput input)`
  Ray-cast against the proxies in the tree.
  `void`
  `rebuildBottomUp()`
  Build an optimal tree.
  `void`
  `validate()`
  Validate this tree.

  ### Methods inherited from class Object

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

- ## Field Details

  - ### MAX_STACK_SIZE

    public static final int MAX_STACK_SIZE
    See Also:
      - Constant Field Values

  - ### NULL_NODE

    public static final int NULL_NODE
    See Also:
      - Constant Field Values

- ## Constructor Details

  - ### DynamicTree

    public DynamicTree()

- ## Method Details

  - ### createProxy

    public final int createProxy(AABB aabb, Object userData)
    Description copied from interface: `BroadPhaseStrategy`
    Create a proxy. Provide a tight fitting AABB and a userData pointer.
    Specified by:
      `createProxy` in interface `BroadPhaseStrategy`
    Parameters:
      `aabb` -
      `userData` -
    Returns:

  - ### destroyProxy

    public final void destroyProxy(int proxyId)
    Description copied from interface: `BroadPhaseStrategy`
    Destroy a proxy
    Specified by:
      `destroyProxy` in interface `BroadPhaseStrategy`
    Parameters:
      `proxyId` -

  - ### moveProxy

    public final boolean moveProxy(int proxyId, AABB aabb, Vec2 displacement)
    Description copied from interface: `BroadPhaseStrategy`
    Move a proxy with a swepted AABB. If the proxy has moved outside of its fattened AABB, then the proxy is removed from the tree and re-inserted. Otherwise the function returns immediately.
    Specified by:
      `moveProxy` in interface `BroadPhaseStrategy`
    Returns:
      true if the proxy was re-inserted.

  - ### getUserData

    public final Object getUserData(int proxyId)
    Specified by:
      `getUserData` in interface `BroadPhaseStrategy`

  - ### getFatAABB

    public final AABB getFatAABB(int proxyId)
    Specified by:
      `getFatAABB` in interface `BroadPhaseStrategy`

  - ### query

    public final void query(TreeCallback callback, AABB aabb)
    Description copied from interface: `BroadPhaseStrategy`
    Query an AABB for overlapping proxies. The callback class is called for each proxy that overlaps the supplied AABB.
    Specified by:
      `query` in interface `BroadPhaseStrategy`
    Parameters:
      `callback` -

  - ### raycast

    public void raycast(TreeRayCastCallback callback, RayCastInput input)
    Description copied from interface: `BroadPhaseStrategy`
    Ray-cast against the proxies in the tree. This relies on the callback to perform a exact ray-cast in the case were the proxy contains a shape. The callback also performs the any collision filtering. This has performance roughly equal to k * log(n), where k is the number of collisions and n is the number of proxies in the tree.
    Specified by:
      `raycast` in interface `BroadPhaseStrategy`
    Parameters:
      `callback` - a callback class that is called for each proxy that is hit by the ray.
      `input` - the ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).

  - ### computeHeight

    public final int computeHeight()
    Description copied from interface: `BroadPhaseStrategy`
    Compute the height of the tree.
    Specified by:
      `computeHeight` in interface `BroadPhaseStrategy`

  - ### validate

    public void validate()
    Validate this tree. For testing.

  - ### getHeight

    public int getHeight()
    Description copied from interface: `BroadPhaseStrategy`
    Compute the height of the binary tree in O(N) time. Should not be called often.
    Specified by:
      `getHeight` in interface `BroadPhaseStrategy`
    Returns:

  - ### getMaxBalance

    public int getMaxBalance()
    Description copied from interface: `BroadPhaseStrategy`
    Get the maximum balance of an node in the tree. The balance is the difference in height of the two children of a node.
    Specified by:
      `getMaxBalance` in interface `BroadPhaseStrategy`
    Returns:

  - ### getAreaRatio

    public float getAreaRatio()
    Description copied from interface: `BroadPhaseStrategy`
    Get the ratio of the sum of the node areas to the root area.
    Specified by:
      `getAreaRatio` in interface `BroadPhaseStrategy`
    Returns:

  - ### rebuildBottomUp

    public void rebuildBottomUp()
    Build an optimal tree. Very expensive. For testing.

  - ### getInsertionCount

    public int getInsertionCount()
    Specified by:
      `getInsertionCount` in interface `BroadPhaseStrategy`

  - ### drawTree

    public void drawTree(DebugDraw argDraw)
    Specified by:
      `drawTree` in interface `BroadPhaseStrategy`

  - ### drawTree

    public void drawTree(DebugDraw argDraw, DynamicTreeNode node, int spot, int height)