-
Notifications
You must be signed in to change notification settings - Fork 6
/
Copy pathindex.html
267 lines (235 loc) · 10.9 KB
/
index.html
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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
<!DOCTYPE html>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<html>
<head>
<title>An interactive explanation of quadtrees.</title>
<link rel="stylesheet" type="text/css" href="quadtreevis.css" />
<script>
(function(d) {
var config = {
kitId: 'med0yzx',
scriptTimeout: 3000
},
h=d.documentElement,t=setTimeout(function(){h.className=h.className.replace(/\bwf-loading\b/g,"")+" wf-inactive";},config.scriptTimeout),tk=d.createElement("script"),f=false,s=d.getElementsByTagName("script")[0],a;h.className+=" wf-loading";tk.src='//use.typekit.net/'+config.kitId+'.js';tk.async=true;tk.onload=tk.onreadystatechange=function(){a=this.readyState;if(f||a&&a!="complete"&&a!="loaded")return;f=true;clearTimeout(t);try{Typekit.load(config)}catch(e){}};s.parentNode.insertBefore(tk,s)
})(document);
</script>
</head>
<body>
<h2>An interactive explanation of quadtrees.</h2>
<p class="explanation">
Here is a map of points in a space.
</p>
<svg id="widemap" class="quadtreemap" width="100%" height="75%">
<g class="quadroot"></g>
<g class="pointroot"></g>
</svg>
<p class="explanation">
The space is divided into four <em>rectangles</em>. Each of those rectangles is divided such that it contains a maximum of <em>four children</em>. Each child is either a <em>point</em> or a smaller rectangle.
</p>
<p class="instructions">
Click a rectangle and count its children to verify. None of them will contain more than four points or direct subrectangles.
</p>
<br />
<p class="explanation">
Here is a graph of a <strong>quadtree</strong> representing the rectangles and points above.
</p>
<svg id="widetree" class="quadtreetree" width="100%" height="55%">
<g class="treeroot"></g>
</svg>
<p class="post-svg-spacer-hack"> </p>
<dl id="zoom-instructions" class="instructions">
<dt>
1. Zoom out to see more of the tree.
</dt>
<dd>
<p>Roll the mouse wheel inside of the tree view.</p>
<p>If you are on a touchscreen device, pinch out.</p>
</dd>
<dt>
2. Pan around the tree.
</dt>
<dd>
<p>Drag within the tree view.</p>
</dd>
<dt class="dismiss-link-container">
<button id="dismiss-zoom-instructions" data-target="zoom-instructions">Got it.</button>
</dt>
</dl>
<div class="explanation">
<h3>What am I looking at here?</h3>
<ul>
<li>
Each <span class="green reverse-highlight">green node</span> represents a <em>rectangle</em> in a space.
</li>
<li>
Each <span class="white reverse-highlight">white node</span> represents a <em>point</em> in that same space.
</li>
<li>
The green nodes can have up to <em>four children</em>, either white or green. These children are contained within the rectangle that the green node represents.
</li>
<li>
(Gray nodes represent vacancies, spots for children that are not yet occupied.)
</li>
</ul>
</div>
</div>
<!--
<div class="two-bars">
-->
<div class="mainbar explanation">
<h3>Why four children?</h3>
<p>
By <a href="http://en.wikipedia.org/wiki/Quadtree">definition</a>, a quadtree is a tree in which each node has at most four children. Quadtree implementations — like <a href="https://github.com/mbostock/d3/wiki/Quadtree-Geom">D3's</a> (<a href="https://github.com/mbostock/d3/blob/master/src/geom/quadtree.js">source</a>) — ensure that as points are added to the tree, nodes are rearranged such that none of them have more than four children.
</p>
<p>
Below are the graph of the quadtree and the map of the points and rectangles it represents again, <strong>side-by-side</strong> so that you can see how they relate to each other.
</p>
</div>
<!--
<div class="sidebar">
<p>
When a new point is inserted into a <a href="https://github.com/d3/d3-quadtree/blob/master/src/add.js#L44">D3 quadtree</a>:
<ol>
<li>It decides which quadrant</a> of the root node that the point should be in ( by checking the point's x and y against the horiontal center and vertical centers of the node's quad).
</li>
<li>
If there is a leaf node (let's call it N) in that quadrant, <a href="https://github.com/mbostock/d3/blob/master/src/geom/quadtree.js#L84">it moves N's point into a child of N</a> and adds the new point as a child of N as well.
</li>
<li>N is <a href="https://github.com/mbostock/d3/blob/master/src/geom/quadtree.js#L108">marked as a non-leaf</a> because it has children.
</li>
</ol>
</p>
</div>
</div>
-->
<dl id="sidebyside-instructions" class="instructions">
<dt>
1. Look at how the map correlates to the tree.
</dt>
<dd>
<p>
Click on an rectangle or point in the map view (below on the left). The tree view (below on the right) will pan to the corresponding node in the tree.
</p>
<p>
Zoom out and pan around the tree view to see the node in context.
</p>
</dd>
<dt>
2. Look at how the tree correlates to the map.
</dt>
<dd>
<p>
Click on a tree node in the tree view. The map will highlight the area or point that it represents.
</p>
</dd>
<dt class="dismiss-link-container">
<button id="dismiss-sidebyside-instructions" data-target="sidebyside-instructions">Yope. I see how that goes.</button>
</dt>
</dl>
<p class="post-svg-spacer-hack"> </p>
<svg id="sidebysidetree" class="quadtreetree" width="49%" height="70%">
<g class="treeroot"></g>
</svg>
<svg id="sidebysidemap" class="quadtreemap" width="49%" height="70%">
<g class="quadroot"></g>
<g class="pointroot"></g>
</svg>
<pre id="node-json-box" class="details-box">
</pre>
<div id="add-points-instructions" class="instructions">
<ul>
<li>
For fun, <button id="add-points-button">Add one hundred points</button> and see how the map and tree rearrange themselves.
</li>
<li>
<strong>If</strong> you are interested in D3's implementation of the quadtree, click on a node, rectangle, or point, then <button id="show-node-json" data-target="node-json-box">Show the quadtree node contents</button>.
</li>
</ul>
<!-- <button id="delete-point-button">Delete selected point</button> -->
</div>
<div class="explanation">
<h3>OK, so what is the point?</h3>
<p>
Quadtrees are a way of partitioning space so that it's easy to traverse and search. Some possible uses of that include:
</p>
<dl>
<dt>
Hit detection
</dt>
<dd>
<p>
Let's say you have a bunch of points in a space, like in the maps above. Someone asks you if some arbitrary point <em>p</em> is within your bunch of points. How can you find out if you have that point?
</p>
<p>
You could compare every single point you have to <em>p</em>, but if you had 1000 points, and none of them were <em>p</em>, you'd have to do 1000 comparisons to find that out. Alternatively, you could get very fast lookup by keeping a grid (a 2D array) of booleans for every single possible point in this space. However, if the space these points are on is 1,000,000 x 1,000,000, you need to store 1,000,000,000,000 variables.
</p>
<p>
Or you could set up a quadtree. When you have it search for <em>p</em>, it will find out which quadrant it is inside. Then, it will find out what quadrant within that quadrant it is inside. And so forth.
</p>
<p>
It will only have to do this at most seven times for a 100x100 space (assuming points can only have integer values), even if there are 1000 points in it. For a 1,000,000x1,000,000 space, it's a maximum of 20 times.
</p>
<p>
After it finds its way to that rectangle node, it merely needs to see if any of the four children equal <em>p</em>.
</p>
</dd>
<dt>
Finding the nearest neighbor
</dt>
<dd>
<p>
Again, let's say you have a bunch of points in a space. Rather than ask you whether any of them match a given point, someone asks you what the nearest point you have to an arbitrary point among your points.
</p>
<p>
With a quadtree, while searching, you can say, "OK, there's no way anything in this quadrant has any chance of being the nearest neighbor" and eliminate a lot of point comparisons that way. Patrick Surry has a <a href="http://bl.ocks.org/patricksurry/6478178">good example of that</a>.
</p>
</dd>
<dt>
…And more!
</dt>
<dd>
<p>
Really, quadtrees can help out any time you have sparse data that you need to search. A cellular automata simulation of a chemical reaction in which you want to save space by not storing data for cells containing inert substances? Sure. Just use quadtrees to map out the cells with the interesting data.
</p>
<p>
<a href="http://en.wikipedia.org/wiki/Quadtree#Polygonal_map_quadtree">Wikipedia lists a bunch of other uses.</a>
</p>
</dd>
</dl>
</div>
<p>
If you want to know more about using D3 quadtrees, check out the <a href="https://github.com/mbostock/d3/wiki/Quadtree-Geom">D3 API documentation</a>. Perhaps the <a href="https://github.com/jimkang/quadtreevis">source of this document</a> may be of help to you as well. Feel free to <a href="mailto:jimkang@fastmail.com">send me any requests</a> for clarification or comments.
</p>
<footer>
<div class="content-wrap">
<p>
And if this helped you understand quadtrees, consider <a href="https://ko-fi.com/jimkang">sending me a tip</a> to support my work!
</p>
<a href='https://ko-fi.com/B0B12GNVQ' target='_blank'><img height='36' style='border:0px;height:36px;' src='https://storage.ko-fi.com/cdn/kofi2.png?v=3' border='0' alt='Buy Me a Coffee at ko-fi.com' /></a>
<div class="nav"><a href="/">« jimkang.com</a></div>
<section class="copy">
<p>© 2014 Jim Kang</a>
</p>
</section>
</div>
</footer>
<script src="lib/d3.js"></script>
<script src="node_modules/quadtreenodereport/quadtreenodereport.js"></script>
<script src="node_modules/quadtreelabeler/quadtreelabeler.js"></script>
<script src="node_modules/quadtreetree/node_modules/lodash/dist/lodash.min.js"></script>
<script src="node_modules/quadtreetree/node_modules/one-at/one-at.js"></script>
<script src="node_modules/quadtreetree/accessors.js"></script>
<script src="node_modules/quadtreetree/idmaker.js"></script>
<script src="node_modules/quadtreetree/quadtree-to-layout-tree.js"></script>
<script src="node_modules/quadtreetree/quadtreetree.js"></script>
<script src="node_modules/quadtreemap/renderquadtreepoints.js"></script>
<script src="node_modules/quadtreemap/mapquadrenderer.js"></script>
<script src="node_modules/quadtreemap/quadtreemap.js"></script>
<script src="node_modules/svgcamera/camera.js"></script>
<script type="text/javascript" src="example-quadtree.js"></script>
<script type="text/javascript" src="exhibit-helpers.js"></script>
<script type="text/javascript" src="exhibit-reporter.js"></script>
<script type="text/javascript" src="exhibit-controller.js"></script>
</body>
</html>