Quadtrees (The Chickadee Game Toolkit)

From 25c5eac5e6ca1035db1eddd7bea9ac78531da57e Mon Sep 17 00:00:00 2001 From: David Thompson Date: Thu, 28 Dec 2023 11:23:49 -0500 Subject: Delete manuals! Good riddance! These are hosted on files.dthompson.us now! --- manuals/chickadee/Quadtrees.html | 222 --------------------------------------- 1 file changed, 222 deletions(-) delete mode 100644 manuals/chickadee/Quadtrees.html (limited to 'manuals/chickadee/Quadtrees.html') diff --git a/manuals/chickadee/Quadtrees.html b/manuals/chickadee/Quadtrees.html deleted file mode 100644 index 5675542..0000000 --- a/manuals/chickadee/Quadtrees.html +++ /dev/null @@ -1,222 +0,0 @@ - - - - - - -Quadtrees (The Chickadee Game Toolkit) - - - - - - - - - - - - - - - - - - - - -

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. -

- -

- - - - - - -- cgit v1.2.3