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.
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.
Return #t
if obj is a quadtree.
Clear all objects from quadtree.
Insert object with bounding box rect into quadtree.
Delete object, who occupies the space rect, from quadtree.
Return the first object in quadtree in the vicinity of rect that satisfies pred.
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.
Call proc for all objects in the vicinity of rect in quadtree.
Return #t
if quadtree is a leaf node.
Return the bounding rectangle of quadtree.
Return the maximum depth of quadtree.
Return the desired per-node maximum object count of quadtree.
Return the depth of the node 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 | | | | *------*------*
Return the upper-right child node of quadtree, or #f
if
quadtree is a leaf node.
Return the upper-left child node of quadtree, or #f
if
quadtree is a leaf node.
Return the lower-left child node of quadtree, or #f
if
quadtree is a leaf node.
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]