UNPKG

8.11 kBHTMLView Raw
1<!doctype html>
2<html>
3 <head>
4 <title>quadtree-js 1.2.0 Performance Test</title>
5 <link rel="stylesheet" type="text/css" href="style.css?v=2" />
6 <meta name="viewport" content="width=device-width, initial-scale=1" />
7
8 <!-- prism syntax highlighting (https://prismjs.com/) -->
9 <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/themes/prism.min.css" integrity="sha512-tN7Ec6zAFaVSG3TpNAKtk4DOHNpSwKHxxrsiw4GHKESGPs5njn/0sMCUMl2svV4wo4BK/rCP7juYz+zx+l6oeQ==" crossorigin="anonymous" />
10 <style>
11 .outer {
12 max-width: 800px;
13 }
14 </style>
15 </head>
16 <body>
17
18 <div class="outer">
19
20 <h1><a href="https://github.com/timohausmann/quadtree-js">quadtree-js</a> 1.2.0 <small>performance test</small></h1>
21
22 <nav>
23 <div class="nav">
24 <strong>Demos:</strong>
25 <a href="simple.html">simple</a>
26 <a href="dynamic.html">dynamic</a>
27 <a href="many.html">many to many</a>
28 <a href="test-retrieve.html">benchmark</a>
29 </div>
30 <div class="nav">
31 <strong>Old Benchmarks:</strong>
32 <span>benchmark 1.2</span>
33 <a href="test-10000-1.1.3.html">benchmark 1.1.3</a>
34 </div>
35 </nav>
36
37
38 <div id="canvasContainer">
39 <canvas id="canvas" width="800" height="600"></canvas>
40 </div>
41
42 <div class="ctrl">
43 <div class="ctrl-left">
44 Time spend for insert of <span id="cnt_total2">0</span> objects and retrieve once:<br />
45 <strong><span id="cnt_time">0</span></strong>
46 </div>
47
48 <div class="ctrl-right">
49 Total Objects: <span id="cnt_total">0</span><br />
50 Candidates: <span id="cnt_cand">0</span> (<span id="cnt_perc">0</span>%)
51 </div>
52 </div>
53
54 <p>
55 Quadtree 1.2 now stores objects exclusively on leaf nodes. Objects, that overlap into multiple subnodes are now referenced in each matching subnode instead of their parent node. This drastically reduces the collision candidates. Prior to 1.2, overlapping objects were stored in parent nodes (<a href="test-10000-1.1.3.html">1.1.3 Demo</a>).
56 </p>
57 <p>
58 Because objects may now be present in multiple nodes, nodes will split rather soon (depending on the max_objects value, default&nbsp;=&nbsp;10&nbsp;objects per node).
59 </p>
60
61 <p>Heart of the test code:</p>
62
63 <pre><code class="language-javascript">var amount = 10000;
64var myObjects = [];
65for(var i=0; i&lt;amount;i++) {
66 myObjects.push({
67 x: randMinMax(0, 800-maxObjectSize),
68 y: randMinMax(0, 600-maxObjectSize),
69 width: randMinMax(4, maxObjectSize),
70 height: randMinMax(4, maxObjectSize)
71 });
72}
73
74//time measure starts here
75var start = window.performance.now();
76
77var myTree = new Quadtree({
78 x: 0,
79 y: 0,
80 width: 800,
81 height: 600
82}, 10, 4);
83
84for(var i=0; i&lt;amount;i++) {
85 myOldTree.insert(myObjects[i]);
86}
87var candidates = myOldTree.retrieve(myCursor);
88
89//time measure ends here
90var end = window.performance.now();
91var time = end - start;</code></pre>
92
93 <p>
94 To see the full example code please check the page source or
95 <a href="https://github.com/timohausmann/quadtree-js/tree/master/docs" target="_blank" rel="noopener noreferrer">visit GitHub</a>.
96 </p>
97 </div>
98
99 <!-- github corner (https://github.com/tholman/github-corners) -->
100 <a href="https://github.com/timohausmann/quadtree-js" class="github-corner" aria-label="View source on GitHub"
101 target="_blank" rel="noopener noreferrer">
102 <svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true">
103 <path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path>
104 </svg>
105 </a>
106
107 <!-- prism syntax highlighting -->
108 <script src="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/prism.min.js" integrity="sha512-WkVkkoB31AoI9DAk6SEEEyacH9etQXKUov4JRRuM1Y681VsTq7jYgrRw06cbP6Io7kPsKx+tLFpH/HXZSZ2YEQ==" crossorigin="anonymous"></script>
109
110 <!-- quadtree lib and script -->
111 <script src="./quadtree.min.js"></script>
112 <!-- CDN alternative: -->
113 <!-- <script src="https://cdn.jsdelivr.net/npm/@timohausmann/quadtree-js/quadtree.min.js"></script> -->
114 <script>
115
116 //---- SETUP
117 var amount = 10000;
118 var max_objects = 10;
119 var max_levels = 4;
120 var width = 800;
121 var height = 600;
122 var maxObjectSize = 64;
123
124 var randMinMax = function(min, max, round) {
125 var val = min + (Math.random() * (max - min));
126 if(round) val = Math.round(val);
127 return val;
128 };
129
130 var myCursor = {
131 x : randMinMax(120,width-120),
132 y : randMinMax(120,height-120),
133 width : 32,
134 height : 32
135 };
136
137 var myObjects = [];
138 for(var i=0; i<amount;i++) {
139 myObjects.push({
140 x: randMinMax(0, width-maxObjectSize),
141 y: randMinMax(0, height-maxObjectSize),
142 width: randMinMax(4, maxObjectSize),
143 height: randMinMax(4, maxObjectSize)
144 });
145 }
146
147 console.log('Quadtree 1.2 with', amount, 'objects on leaf nodes only');
148
149
150 //---- TEST
151 var start = window.performance.now();
152
153 var myTree = new Quadtree({
154 x: 0,
155 y: 0,
156 width: width,
157 height: height
158 }, max_objects, max_levels);
159
160 for(var i=0; i<amount;i++) {
161 myTree.insert(myObjects[i]);
162 }
163
164 var candidates = myTree.retrieve(myCursor);
165
166 var end = window.performance.now();
167 var time = end - start;
168
169 console.log('Found', candidates.length, 'candidates in', time, 'ms');
170
171
172 //---- DRAW RESULT
173 var ctx = document.getElementById('canvas').getContext('2d');
174
175 //updateTotal
176 document.querySelector('#cnt_total').innerHTML = myObjects.length;
177 document.querySelector('#cnt_total2').innerHTML = myObjects.length;
178 document.querySelector('#cnt_cand').innerHTML = candidates.length;
179 document.querySelector('#cnt_perc').innerHTML = Math.round((candidates.length/myObjects.length)*100);
180 document.querySelector('#cnt_time').innerHTML = Math.round(time) + 'ms';
181
182 //flag retrieved objects
183 for(i=0;i<candidates.length;i=i+1) {
184 candidates[ i ].check = true;
185 }
186
187 /*
188 * draw Quadtree nodes
189 */
190 var drawQuadtree = function(node) {
191
192 var bounds = node.bounds;
193
194 //no subnodes? draw the current node
195 if(node.nodes.length === 0) {
196 ctx.strokeStyle = 'rgba(255,0,0,0.5)';
197 ctx.strokeRect(bounds.x, bounds.y, bounds.width, bounds.height);
198
199 //has subnodes? drawQuadtree them!
200 } else {
201 for(var i=0;i<node.nodes.length;i=i+1) {
202 drawQuadtree(node.nodes[ i ]);
203 }
204 }
205 };
206
207 /*
208 * draw all objects
209 */
210 var drawObjects = function() {
211
212 var obj;
213
214 for(var i=0;i<myObjects.length;i=i+1) {
215
216 obj = myObjects[ i ];
217
218 if(obj.check) {
219 ctx.fillStyle = 'rgba(48,255,48,0.5)';
220 ctx.fillRect(obj.x, obj.y, obj.width, obj.height);
221 } else {
222 ctx.strokeStyle = 'rgba(255,255,255,0.5)';
223 ctx.strokeRect(obj.x, obj.y, obj.width, obj.height);
224 }
225 }
226 };
227
228 drawObjects();
229 drawQuadtree(myTree);
230
231 //draw retrieve area
232 ctx.strokeStyle = 'blue';
233 ctx.lineWidth = 2;
234 ctx.fillStyle = 'rgba(255,255,255,0.5)';
235 ctx.fillRect(myCursor.x, myCursor.y, myCursor.width, myCursor.height);
236 ctx.strokeRect(myCursor.x, myCursor.y, myCursor.width, myCursor.height);
237
238 </script>
239
240 </body>
241</html>