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 |
|
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;
|
61 | var myObjects = [];
|
62 | for(var i=0; i<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 |
|
71 | var myTree = new Quadtree({
|
72 | x: 0,
|
73 | y: 0,
|
74 | width: 800,
|
75 | height: 600
|
76 | }, 10, 4);
|
77 |
|
78 | for(var i=0; i<amount;i++) {
|
79 | myOldTree.insert(myObjects[i]);
|
80 | }
|
81 |
|
82 | //time measure starts here
|
83 | var start = window.performance.now();
|
84 |
|
85 | var candidates = myOldTree.retrieve(myCursor);
|
86 |
|
87 | //time measure ends here
|
88 | var end = window.performance.now();
|
89 | var 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 |
|
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 |
|
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 |
|
109 | <script src="./quadtree.min.js"></script>
|
110 |
|
111 |
|
112 |
|
113 |
|
114 | <script>
|
115 |
|
116 |
|
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 |
|
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 |
|
173 | var ctx = document.getElementById('canvas').getContext('2d');
|
174 |
|
175 |
|
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 |
|
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 |
|
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 |
|
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 |
|
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>
|