UNPKG

8.08 kBHTMLView Raw
1<!doctype html>
2<html>
3 <head>
4 <title>quadtree-js 1.2.6 "Retrieve" 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.6 <small>retrieve 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 <span>benchmark</span>
29 </div>
30 <div class="nav">
31 <strong>Old Benchmarks:</strong>
32 <a href="test-10000-1.2.0.html">benchmark 1.2</a>
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 to retrieve <span id="cnt_total2">0</span> objects 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.6 now uses the ES6 feature <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set" target="_blank">Set</a> to remove duplicates faster than ever (was O(n^2), now O(n)).
56 </p>
57
58 <p>Heart of the test code:</p>
59
60 <pre><code class="language-javascript">var amount = 1000000;
61var myObjects = [];
62for(var i=0; i&lt;amount;i++) {
63 myObjects.push({
64 x: randMinMax(0, 800-maxObjectSize),
65 y: randMinMax(0, 600-maxObjectSize),
66 width: randMinMax(4, maxObjectSize),
67 height: randMinMax(4, maxObjectSize)
68 });
69}
70
71var myTree = new Quadtree({
72 x: 0,
73 y: 0,
74 width: 800,
75 height: 600
76}, 10, 4);
77
78for(var i=0; i&lt;amount;i++) {
79 myOldTree.insert(myObjects[i]);
80}
81
82//time measure starts here
83var start = window.performance.now();
84
85var candidates = myOldTree.retrieve(myCursor);
86
87//time measure ends here
88var end = window.performance.now();
89var time = end - start;</code></pre>
90
91 <p>
92 To see the full example code please check the page source or
93 <a href="https://github.com/timohausmann/quadtree-js/tree/master/docs" target="_blank" rel="noopener noreferrer">visit GitHub</a>.
94 </p>
95 </div>
96
97 <!-- github corner (https://github.com/tholman/github-corners) -->
98 <a href="https://github.com/timohausmann/quadtree-js" class="github-corner" aria-label="View source on GitHub"
99 target="_blank" rel="noopener noreferrer">
100 <svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true">
101 <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>
102 </svg>
103 </a>
104
105 <!-- prism syntax highlighting -->
106 <script src="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/prism.min.js" integrity="sha512-WkVkkoB31AoI9DAk6SEEEyacH9etQXKUov4JRRuM1Y681VsTq7jYgrRw06cbP6Io7kPsKx+tLFpH/HXZSZ2YEQ==" crossorigin="anonymous"></script>
107
108 <!-- quadtree lib and script -->
109 <script src="./quadtree.min.js"></script>
110 <!-- CDN alternative: -->
111 <!-- <script src="https://cdn.jsdelivr.net/npm/@timohausmann/quadtree-js/quadtree.min.js"></script> -->
112 <!-- compare with 1.1.3, 1.2.5 to see performance benefits: -->
113 <!-- <script src="https://cdn.jsdelivr.net/npm/@timohausmann/quadtree-js@1.2.5/quadtree.min.js"></script> -->
114 <script>
115
116 //---- SETUP
117 var amount = 1000000;
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 with', amount, 'objects on leaf nodes');
148
149
150 //---- TEST
151
152 var myTree = new Quadtree({
153 x: 0,
154 y: 0,
155 width: width,
156 height: height
157 }, max_objects, max_levels);
158
159
160 for(var i=0; i<amount;i++) {
161 myTree.insert(myObjects[i]);
162 }
163
164 var start = window.performance.now();
165 var candidates = myTree.retrieve(myCursor);
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>