Next: Grids, Previous: Heaps, Up: Data Structures [Contents][Index]

The `(chickadee data quadtree)`

module provides a 2D spatial
partitioning implementation known as a “quadtree”. A quadtree
recursively subdivides the world into rectangular quadrants. This
data structure is very useful for handling broad-phase collision
detection because it can quickly determine the objects that may
possibly be colliding with another, resulting in fewer narrow-phase
collision tests that are typically much more expensive.

- Procedure:
**make-quadtree***bounds [#:max-size 5] [#:max-depth 4]* Return a new quadtree that covers the area

`bounds`. Each node will try to hold at maximum`max-size`objects and the tree depth will be restricted to`max-depth`.

- Procedure:
**quadtree?***obj* Return

`#t`

if`obj`is a quadtree.

- Procedure:
**quadtree-clear!***quadtree* Clear all objects from

`quadtree`.

- Procedure:
**quadtree-insert!***quadtree rect object* Insert

`object`with bounding box`rect`into`quadtree`.

- Procedure:
**quadtree-delete!***quadtree rect object* Delete

`object`, who occupies the space`rect`, from`quadtree`.

- Procedure:
**quadtree-find***rect pred* Return the first object in

`quadtree`in the vicinity of`rect`that satisfies`pred`.

- Procedure:
**quadtree-fold***quadtree rect init proc* Apply

`proc`to all objects in the vicinity of`rect`in`quadtree`to build a result and return that result.`init`is the initial result. If there are no objects in the vicinity of`rect`, just`init`is returned.

- Procedure:
**quadtree-for-each***quadtree rect proc* Call

`proc`for all objects in the vicinity of`rect`in`quadtree`.

- Procedure:
**quadtree-leaf?***quadtree* Return

`#t`

if`quadtree`is a leaf node.

- Procedure:
**quadtree-bounds***quadtree* Return the bounding rectangle of

`quadtree`.

- Procedure:
**quadtree-max-depth***quadtree* Return the maximum depth of

`quadtree`.

- Procedure:
**quadtree-max-size***quadtree* Return the desired per-node maximum object count of

`quadtree`.

- Procedure:
**quadtree-depth***quadtree* Return the depth of the node

`quadtree`.

- Procedure:
**quadtree-size***quadtree* Return the number of objects stored in the node

`quadtree`.

Non-leaf nodes always have four child nodes, which correspond to the quadrants of a Cartesian coordinate system:

*------*------* | | | | Q2 | Q1 | | | | *------*------* | | | | Q3 | Q4 | | | | *------*------*

- Procedure:
**quadtree-q1***quadtree* Return the upper-right child node of

`quadtree`, or`#f`

if`quadtree`is a leaf node.

- Procedure:
**quadtree-q2***quadtree* Return the upper-left child node of

`quadtree`, or`#f`

if`quadtree`is a leaf node.

- Procedure:
**quadtree-q3***quadtree* Return the lower-left child node of

`quadtree`, or`#f`

if`quadtree`is a leaf node.

- Procedure:
**quadtree-q4***quadtree* Return the lower-right child node of

`quadtree`, or`#f`

if`quadtree`is a leaf node.

Next: Grids, Previous: Heaps, Up: Data Structures [Contents][Index]