1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 2017-2023 David Thompson dthompson2@worcester.edu
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3
or any later version published by the Free Software Foundation;
with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
A copy of the license is included in the section entitled "GNU
Free Documentation License".
A copy of the license is also available from the Free Software
Foundation Web site at http://www.gnu.org/licenses/fdl.html.
* Chickadee: (chickadee). Game programming toolkit for Guile.
The document was typeset with
http://www.texinfo.org/ (GNU Texinfo).
-->
<!-- Created by GNU Texinfo 6.7, http://www.gnu.org/software/texinfo/ -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Quadtrees (The Chickadee Game Toolkit)</title>
<meta name="description" content="Quadtrees (The Chickadee Game Toolkit)" />
<meta name="keywords" content="Quadtrees (The Chickadee Game Toolkit)" />
<meta name="resource-type" content="document" />
<meta name="distribution" content="global" />
<meta name="Generator" content="makeinfo" />
<link href="index.html" rel="start" title="Top" />
<link href="Index.html" rel="index" title="Index" />
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Data-Structures.html" rel="up" title="Data Structures" />
<link href="Grids.html" rel="next" title="Grids" />
<link href="Heaps.html" rel="prev" title="Heaps" />
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.indentedblock {margin-right: 0em}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
kbd {font-style: oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
span.nolinebreak {white-space: nowrap}
span.roman {font-family: initial; font-weight: normal}
span.sansserif {font-family: sans-serif; font-weight: normal}
ul.no-bullet {list-style: none}
@media (min-width: 1140px) {
body {
margin-left: 14rem;
margin-right: 4rem;
max-width: 52rem;
}
}
@media (min-width: 800px) and (max-width: 1140px) {
body {
margin-left: 6rem;
margin-right: 4rem;
max-width: 52rem;
}
}
@media (max-width: 800px) {
body {
margin: 1rem;
}
}
-->
</style>
<link rel="stylesheet" type="text/css" href="https://dthompson.us/css/dthompson.css" />
</head>
<body lang="en">
<span id="Quadtrees"></span><div class="header">
<p>
Next: <a href="Grids.html" accesskey="n" rel="next">Grids</a>, Previous: <a href="Heaps.html" accesskey="p" rel="prev">Heaps</a>, Up: <a href="Data-Structures.html" accesskey="u" rel="up">Data Structures</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Index.html" title="Index" rel="index">Index</a>]</p>
</div>
<hr />
<span id="Quadtrees-1"></span><h4 class="subsection">5.6.4 Quadtrees</h4>
<p>The <code>(chickadee data quadtree)</code> 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.
</p>
<dl>
<dt id="index-make_002dquadtree">Procedure: <strong>make-quadtree</strong> <em>bounds [#:max-size 5] [#:max-depth 4]</em></dt>
<dd><p>Return a new quadtree that covers the area <var>bounds</var>. Each node
will try to hold at maximum <var>max-size</var> objects and the tree depth
will be restricted to <var>max-depth</var>.
</p></dd></dl>
<dl>
<dt id="index-quadtree_003f">Procedure: <strong>quadtree?</strong> <em>obj</em></dt>
<dd><p>Return <code>#t</code> if <var>obj</var> is a quadtree.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dclear_0021">Procedure: <strong>quadtree-clear!</strong> <em>quadtree</em></dt>
<dd><p>Clear all objects from <var>quadtree</var>.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dinsert_0021">Procedure: <strong>quadtree-insert!</strong> <em>quadtree rect object</em></dt>
<dd><p>Insert <var>object</var> with bounding box <var>rect</var> into <var>quadtree</var>.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002ddelete_0021">Procedure: <strong>quadtree-delete!</strong> <em>quadtree rect object</em></dt>
<dd><p>Delete <var>object</var>, who occupies the space <var>rect</var>, from
<var>quadtree</var>.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dfind">Procedure: <strong>quadtree-find</strong> <em>rect pred</em></dt>
<dd><p>Return the first object in <var>quadtree</var> in the vicinity of
<var>rect</var> that satisfies <var>pred</var>.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dfold">Procedure: <strong>quadtree-fold</strong> <em>quadtree rect init proc</em></dt>
<dd><p>Apply <var>proc</var> to all objects in the vicinity of <var>rect</var> in
<var>quadtree</var> to build a result and return that result. <var>init</var>
is the initial result. If there are no objects in the vicinity of
<var>rect</var>, just <var>init</var> is returned.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dfor_002deach">Procedure: <strong>quadtree-for-each</strong> <em>quadtree rect proc</em></dt>
<dd><p>Call <var>proc</var> for all objects in the vicinity of <var>rect</var> in
<var>quadtree</var>.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dleaf_003f">Procedure: <strong>quadtree-leaf?</strong> <em>quadtree</em></dt>
<dd><p>Return <code>#t</code> if <var>quadtree</var> is a leaf node.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dbounds">Procedure: <strong>quadtree-bounds</strong> <em>quadtree</em></dt>
<dd><p>Return the bounding rectangle of <var>quadtree</var>.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dmax_002ddepth">Procedure: <strong>quadtree-max-depth</strong> <em>quadtree</em></dt>
<dd><p>Return the maximum depth of <var>quadtree</var>.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dmax_002dsize">Procedure: <strong>quadtree-max-size</strong> <em>quadtree</em></dt>
<dd><p>Return the desired per-node maximum object count of <var>quadtree</var>.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002ddepth">Procedure: <strong>quadtree-depth</strong> <em>quadtree</em></dt>
<dd><p>Return the depth of the node <var>quadtree</var>.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dsize">Procedure: <strong>quadtree-size</strong> <em>quadtree</em></dt>
<dd><p>Return the number of objects stored in the node <var>quadtree</var>.
</p></dd></dl>
<p>Non-leaf nodes always have four child nodes, which correspond to the
quadrants of a Cartesian coordinate system:
</p>
<pre class="verbatim">*------*------*
| | |
| Q2 | Q1 |
| | |
*------*------*
| | |
| Q3 | Q4 |
| | |
*------*------*
</pre>
<dl>
<dt id="index-quadtree_002dq1">Procedure: <strong>quadtree-q1</strong> <em>quadtree</em></dt>
<dd><p>Return the upper-right child node of <var>quadtree</var>, or <code>#f</code> if
<var>quadtree</var> is a leaf node.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dq2">Procedure: <strong>quadtree-q2</strong> <em>quadtree</em></dt>
<dd><p>Return the upper-left child node of <var>quadtree</var>, or <code>#f</code> if
<var>quadtree</var> is a leaf node.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dq3">Procedure: <strong>quadtree-q3</strong> <em>quadtree</em></dt>
<dd><p>Return the lower-left child node of <var>quadtree</var>, or <code>#f</code> if
<var>quadtree</var> is a leaf node.
</p></dd></dl>
<dl>
<dt id="index-quadtree_002dq4">Procedure: <strong>quadtree-q4</strong> <em>quadtree</em></dt>
<dd><p>Return the lower-right child node of <var>quadtree</var>, or <code>#f</code> if
<var>quadtree</var> is a leaf node.
</p></dd></dl>
<hr />
<div class="header">
<p>
Next: <a href="Grids.html" accesskey="n" rel="next">Grids</a>, Previous: <a href="Heaps.html" accesskey="p" rel="prev">Heaps</a>, Up: <a href="Data-Structures.html" accesskey="u" rel="up">Data Structures</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Index.html" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
