From 1ef0c9b18263ee1354987e8f104aff562a953fe6 Mon Sep 17 00:00:00 2001
From: David Thompson <dthompson2@worcester.edu>
Date: Fri, 1 Oct 2021 08:19:52 -0400
Subject: Add (chickadee data quadtree) module.

---
 doc/api.texi | 111 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 111 insertions(+)

(limited to 'doc')

diff --git a/doc/api.texi b/doc/api.texi
index 96803b8..f3b8013 100644
--- a/doc/api.texi
+++ b/doc/api.texi
@@ -5210,10 +5210,121 @@ Clear all messages and scripts awaiting messages in @var{channel}.
 @section Data Structures
 
 @menu
+* Quadtrees::                   Spatial partitioning with recursive subdivision.
 * Grids::                       Spatial partitioning with a fixed grid.
 * Path Finding::                Generic A* path finding.
 @end menu
 
+@node Quadtrees
+@subsection Quadtrees
+
+The @code{(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.
+
+@deffn {Procedure} make-quadtree bounds [#:max-size 5] [#:make-depth 4]
+Return a new quadtree that covers the area @var{bounds}.  Each node
+will try to hold at maximum @var{max-size} objects and the tree depth
+will be restricted to @var{max-depth}.
+@end deffn
+
+@deffn {Procedure} quadtree? obj
+Return @code{#t} if @var{obj} is a quadtree.
+@end deffn
+
+@deffn {Procedure} quadtree-clear! quadtree
+Clear all objects from @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-insert! quadtree rect object
+Insert @var{object} with bounding box @var{rect} into @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-delete! quadtree rect object
+Delete @var{object}, who occupies the space @var{rect}, from
+@var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-find rect pred
+Return the first object in @var{quadtree} in the vicinity of
+@var{rect} that satisfies @var{pred}.
+@end deffn
+
+@deffn {Procedure} quadtree-fold quadtree rect init proc
+Apply @var{proc} to all objects in the vicinity of @var{rect} in
+@var{quadtree} to build a result and return that result.  @var{init}
+is the initial result.  If there are no objects in the vicinity of
+@var{rect}, just @var{init} is returned.
+@end deffn
+
+@deffn {Procedure} quadtree-for-each quadtree rect proc
+Call @var{proc} for all objects in the vicinity of @var{rect} in
+@var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-leaf? quadtree
+Return @code{#t} if @var{quadtree} is a leaf node.
+@end deffn
+
+@deffn {Procedure} quadtree-bounds quadtree
+Return the bounding rectangle of @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-max-depth quadtree
+Return the maximum depth of @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-max-size quadtree
+Return the desired per-node maximum object count of @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-depth quadtree
+Return the depth of the node @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-size quadtree
+Return the number of objects stored in the node @var{quadtree}.
+@end deffn
+
+Non-leaf nodes always have four child nodes, which correspond to the
+quadrants of a Cartesian coordinate system:
+
+@verbatim
+*------*------*
+|      |      |
+|  Q2  |  Q1  |
+|      |      |
+*------*------*
+|      |      |
+|  Q3  |  Q4  |
+|      |      |
+*------*------*
+@end verbatim
+
+@deffn {Procedure} quadtree-q1 quadtree
+Return the upper-right child node of @var{quadtree}, or @code{#f} if
+@var{quadtree} is a leaf node.
+@end deffn
+
+@deffn {Procedure} quadtree-q2 quadtree
+Return the upper-left child node of @var{quadtree}, or @code{#f} if
+@var{quadtree} is a leaf node.
+@end deffn
+
+@deffn {Procedure} quadtree-q3 quadtree
+Return the lower-left child node of @var{quadtree}, or @code{#f} if
+@var{quadtree} is a leaf node.
+@end deffn
+
+@deffn {Procedure} quadtree-q4 quadtree
+Return the lower-right child node of @var{quadtree}, or @code{#f} if
+@var{quadtree} is a leaf node.
+@end deffn
+
 @node Grids
 @subsection Grids
 
-- 
cgit v1.2.3