5.6.4 Quadtrees

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.