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 |
|
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 = 10 objects per node).
|
59 | </p>
|
60 |
|
61 | <p>Heart of the test code:</p>
|
62 |
|
63 | <pre><code class="language-javascript">var amount = 10000;
|
64 | var myObjects = [];
|
65 | for(var i=0; i<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
|
75 | var start = window.performance.now();
|
76 |
|
77 | var myTree = new Quadtree({
|
78 | x: 0,
|
79 | y: 0,
|
80 | width: 800,
|
81 | height: 600
|
82 | }, 10, 4);
|
83 |
|
84 | for(var i=0; i<amount;i++) {
|
85 | myOldTree.insert(myObjects[i]);
|
86 | }
|
87 | var candidates = myOldTree.retrieve(myCursor);
|
88 |
|
89 | //time measure ends here
|
90 | var end = window.performance.now();
|
91 | var 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 |
|
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 |
|
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 |
|
111 | <script src="./quadtree.min.js"></script>
|
112 |
|
113 |
|
114 | <script>
|
115 |
|
116 |
|
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 |
|
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 |
|
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>
|