1 /* 2 Copyright 2008-2024 3 Matthias Ehmann, 4 Michael Gerhaeuser, 5 Carsten Miller, 6 Bianca Valentin, 7 Alfred Wassermann, 8 Peter Wilfahrt 9 10 This file is part of JSXGraph. 11 12 JSXGraph is free software dual licensed under the GNU LGPL or MIT License. 13 14 You can redistribute it and/or modify it under the terms of the 15 16 * GNU Lesser General Public License as published by 17 the Free Software Foundation, either version 3 of the License, or 18 (at your option) any later version 19 OR 20 * MIT License: https://github.com/jsxgraph/jsxgraph/blob/master/LICENSE.MIT 21 22 JSXGraph is distributed in the hope that it will be useful, 23 but WITHOUT ANY WARRANTY; without even the implied warranty of 24 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 25 GNU Lesser General Public License for more details. 26 27 You should have received a copy of the GNU Lesser General Public License and 28 the MIT License along with JSXGraph. If not, see <https://www.gnu.org/licenses/> 29 and <https://opensource.org/licenses/MIT/>. 30 */ 31 32 /*global JXG:true, define: true*/ 33 /*jslint nomen: true, plusplus: true*/ 34 35 import Mat from "./math.js"; 36 import Type from "../utils/type.js"; 37 38 /** 39 * Instantiate a new box quadtree. 40 * A box quadtree stores AABBs, i.e. axis-aligned bounding boxes. 41 * The box quadtree has four sub-quadtress which maybe null if not needed. 42 * 43 * @name JXG.Math.BoxQuadtree 44 * @exports Mat.BoxQuadtree as JXG.Math.BoxQuadtree 45 * 46 * @param {Number} depth Maximum recursion depth. 47 * @param {Number} capacity Maximum number of items stored in this node. 48 * @param {Array} [bbox] Optional bounding box of the box quadtree. If not given, the bounding box is 49 * determined by the items in the insert method. This will only work correctly if the first 50 * call of insert contains the maximum bounding box. 51 * 52 * @constructor 53 */ 54 Mat.BoxQuadtree = function (depth, capacity, bbox) { 55 var l, t, r, b; 56 57 // console.log("---------------------------------------") 58 depth--; 59 60 /** 61 * Maximum depth of the box quadtree node 62 * @name JXG.Math.BoxQuadtree#depth 63 * @type Number 64 * @private 65 */ 66 this.depth = depth; 67 68 /** 69 * Capacity of the box quadtree node 70 * @name JXG.Math.BoxQuadtree#capacity 71 * @type Number 72 * @private 73 */ 74 this.capacity = capacity; 75 76 /** 77 * Item storage. 78 * 79 * @name JXG.Math.BoxQuadtree#items 80 * @type Array 81 * @private 82 */ 83 this.items = []; 84 85 /** 86 * In a subdivided quadtree this represents the top left subtree. 87 * @name JXG.Math.BoxQuadtree#northWest 88 * @type JXG.Math.BoxQuadtree 89 * @private 90 */ 91 this.northWest = null; 92 93 /** 94 * In a subdivided quadtree this represents the top right subtree. 95 * @name JXG.Math.BoxQuadtree#northEast 96 * @type JXG.Math.BoxQuadtree 97 * @private 98 */ 99 this.northEast = null; 100 101 /** 102 * In a subdivided quadtree this represents the bottom right subtree. 103 * @name JXG.Math.BoxQuadtree#southEast 104 * @type JXG.Math.BoxQuadtree 105 * @private 106 */ 107 this.southEast = null; 108 109 /** 110 * In a subdivided quadtree this represents the bottom left subtree. 111 * @name JXG.Math.BoxQuadtree#southWest 112 * @type JXG.Math.BoxQuadtree 113 * @private 114 */ 115 this.southWest = null; 116 117 /** 118 * Bounding box [left, top, right, bottom]. 119 * 120 * @name JXG.Math.BoxQuadtree#bbox 121 * @type Array 122 * @private 123 */ 124 this.bbox = null; 125 126 /** 127 * x-coordinate of bounding box center. 128 * 129 * @name JXG.Math.BoxQuadtree#cx 130 * @type Number 131 * @private 132 */ 133 this.cx = null; 134 135 /** 136 * y-coordinate of bounding box center. 137 * 138 * @name JXG.Math.BoxQuadtree#cy 139 * @type Number 140 * @private 141 */ 142 this.cy = null; 143 144 if (bbox) { 145 // Take supplied bounding box 146 l = bbox[0]; 147 t = bbox[1]; 148 r = bbox[2]; 149 b = bbox[3]; 150 this.cx = (l + r) * 0.5; 151 this.cy = (t + b) * 0.5; 152 this.bbox = [l, t, r, b]; 153 } 154 }; 155 156 Type.extend( 157 Mat.BoxQuadtree.prototype, 158 /** @lends JXG.Math.BoxQuadtree.prototype */ { 159 160 /** 161 * Insert an array of items into the box quadtree. An item is an object 162 * containing at least the properties 163 * <ul> 164 * <li> xlb: lower bound on x 165 * <li> xub: upper bound on x 166 * <li> ylb: lower bound on y 167 * <li> yub: upper bound on y 168 * </ul> 169 * which define the axis-aligned bounding box (AABB) of that item. Additionally, 170 * more properties can be given. 171 * 172 * @param {Array} items to be inserted 173 * @returns {Object} reference to the box quadtree 174 */ 175 insert: function(items) { 176 var i, le, 177 l, t, r, b, 178 it, 179 nw_it = [], 180 ne_it = [], 181 sw_it = [], 182 se_it = [], 183 in_nw, in_ne, in_sw, in_se; 184 185 186 if (this.bbox === null) { 187 // Use bounding box of the supplied items 188 le = items.length; 189 l = b = Infinity; 190 r = t = -Infinity; 191 for (i = 0; i < items.length; i++) { 192 it = items[i]; 193 l = (it.xlb < l) ? it.xlb : l; 194 t = (it.yub > t) ? it.yub : t; 195 r = (it.xub > r) ? it.xub : r; 196 b = (it.ylb < b) ? it.ylb : b; 197 } 198 this.cx = (l + r) * 0.5; 199 this.cy = (t + b) * 0.5; 200 this.bbox = [l, t, r, b]; 201 } else { 202 l = this.bbox[0]; 203 t = this.bbox[1]; 204 r = this.bbox[2]; 205 b = this.bbox[3]; 206 } 207 208 if (this.depth === 0 || this.items.length + items.length < this.capacity) { 209 // if (items.length + items.length < this.capacity) { 210 // console.log("Capacity sufficient, D=", this.depth, this.items.length, items.length); 211 // } 212 // if (depth === 0) {console.log("Max depth reached", items.length, this.capacity); } 213 214 this.items = this.items.concat(items); 215 return this; 216 } 217 218 le = items.length; 219 for (i = 0; i < le; i++) { 220 it = items[i]; 221 in_nw = it.xlb <= this.cx && it.yub > this.cy; 222 in_sw = it.xlb <= this.cx && it.ylb <= this.cy; 223 in_ne = it.xub > this.cx && it.yub > this.cy; 224 in_se = it.xub > this.cx && it.ylb <= this.cy; 225 226 // If it overlaps all 4 quadrants then insert it at the current 227 // depth, otherwise append it to a list to be inserted under every 228 // quadrant that it overlaps. 229 if (in_nw && in_ne && in_se && in_sw) { 230 this.items.push(it); 231 } else { 232 if (in_nw) { nw_it.push(it); } 233 if (in_sw) { sw_it.push(it); } 234 if (in_ne) { ne_it.push(it); } 235 if (in_se) { se_it.push(it); } 236 } 237 } 238 239 // Create the sub-quadrants, recursively. 240 this.subdivide(nw_it, sw_it, ne_it, se_it, l, t, r, b); 241 242 return this; 243 }, 244 245 /** 246 * Insert an item into the box quadtree, where an item is an object 247 * containing at least the properties 248 * 249 * <ul> 250 * <li> xlb: lower bound on x 251 * <li> xub: upper bound on x 252 * <li> ylb: lower bound on y 253 * <li> yub: upper bound on y 254 * </ul> 255 * which define the axis-aligned bounding box (AABB) of that item. Additionally, 256 * more properties can be given. 257 * 258 * @param {Object} it Item to be inserted 259 * @returns {Object} reference to the box quadtree 260 */ 261 insertItem: function(it) { 262 var l, t, r, b, 263 nw_it = [], 264 ne_it = [], 265 sw_it = [], 266 se_it = [], 267 in_nw, in_ne, in_sw, in_se; 268 269 270 if (this.bbox === null) { 271 // Use bounding box of the supplied items 272 l = b = Infinity; 273 r = t = -Infinity; 274 275 l = (it.xlb < l) ? it.xlb : l; 276 t = (it.yub > t) ? it.yub : t; 277 r = (it.xub > r) ? it.xub : r; 278 b = (it.ylb < b) ? it.ylb : b; 279 280 this.cx = (l + r) * 0.5; 281 this.cy = (t + b) * 0.5; 282 this.bbox = [l, t, r, b]; 283 } else { 284 l = this.bbox[0]; 285 t = this.bbox[1]; 286 r = this.bbox[2]; 287 b = this.bbox[3]; 288 } 289 290 if (this.depth === 0 || this.items.length + 1 < this.capacity) { 291 this.items.push(it); 292 return this; 293 } 294 295 in_nw = it.xlb <= this.cx && it.yub > this.cy; 296 in_sw = it.xlb <= this.cx && it.ylb <= this.cy; 297 in_ne = it.xub > this.cx && it.yub > this.cy; 298 in_se = it.xub > this.cx && it.ylb <= this.cy; 299 300 // If it overlaps all 4 quadrants then insert it at the current 301 // depth, otherwise append it to a list to be inserted under every 302 // quadrant that it overlaps. 303 if (in_nw && in_ne && in_se && in_sw) { 304 this.items.push(it); 305 } else { 306 if (in_nw) { nw_it.push(it); } 307 if (in_sw) { sw_it.push(it); } 308 if (in_ne) { ne_it.push(it); } 309 if (in_se) { se_it.push(it); } 310 } 311 312 // Create the sub-quadrants, recursively. 313 this.subdivide(nw_it, sw_it, ne_it, se_it, l, t, r, b); 314 315 return this; 316 }, 317 318 /** 319 * Create the sub-quadrants if necessary, recursively 320 * @param {Array} nw_it list of items for northWest subtree 321 * @param {Array} sw_it list of items for southWest subtree 322 * @param {Array} ne_it list of items for northEast subtree 323 * @param {Array} se_it list of items for southEast subtree 324 * @param {Number} l bounding box left 325 * @param {Number} t bounding box top 326 * @param {Number} r bounding box right 327 * @param {Number} b bounding box bottom 328 * @returns {Object} reference to the box quadtree 329 * @private 330 */ 331 subdivide: function(nw_it, sw_it, ne_it, se_it, l, t, r, b) { 332 if (nw_it.length > 0) { 333 if (this.northWest === null) { 334 this.northWest = new JXG.Math.BoxQuadtree(this.depth, this.capacity, [l, t, this.cx, this.cy]); 335 } 336 this.northWest.insert(nw_it); 337 } 338 if (sw_it.length > 0) { 339 if (this.southWest === null) { 340 this.southWest = new JXG.Math.BoxQuadtree(this.depth, this.capacity, [l, this.cy, this.cx, b]); 341 } 342 this.southWest.insert(sw_it); 343 } 344 if (ne_it.length > 0) { 345 if (this.northEast === null) { 346 this.northEast = new JXG.Math.BoxQuadtree(this.depth, this.capacity, [this.cx, t, r, this.cy]); 347 } 348 this.northEast.insert(ne_it); 349 } 350 if (se_it.length > 0) { 351 if (this.southEast === null) { 352 this.southEast = new JXG.Math.BoxQuadtree(this.depth, this.capacity, [this.cx, this.cy, r, b]); 353 } 354 this.southEast.insert(se_it); 355 } 356 357 return this; 358 }, 359 360 /** 361 * Find all entries of the box quadtree which have an overlap 362 * with the given rectangle (AABB). Items may appear multiple times. 363 * 364 * @param {Array} box AABB of the form [l, t, r, b] 365 * @returns {Array} list of items overlapping with box 366 */ 367 find: function(box) { 368 var overlaps = function(item) { 369 return box[2] >= item.xlb && box[0] <= item.xub && 370 box[3] <= item.yub && box[1] >= item.ylb; 371 }, 372 hits = [], 373 i, le; 374 375 le = this.items.length; 376 for (i = 0; i < le; i++) { 377 if (overlaps(this.items[i])) { 378 hits.push(this.items[i]); 379 } 380 } 381 382 if (this.northWest !== null && box[0] <= this.cx & box[1] >= this.cy) { 383 Type.concat(hits, this.northWest.find(box)); 384 } 385 if (this.southWest !== null && box[0] <= this.cx & box[3] <= this.cy) { 386 Type.concat(hits, this.southWest.find(box)); 387 } 388 if (this.northEast !== null && box[2] >= this.cx & box[1] >= this.cy) { 389 Type.concat(hits, this.northEast.find(box)); 390 } 391 if (this.southEast !== null && box[2] >= this.cx & box[3] <= this.cy) { 392 Type.concat(hits, this.southEast.find(box)); 393 } 394 395 return hits; 396 }, 397 398 /** 399 * Analyze the box quadtree. 400 * 401 * @returns {Object} data about the box quadtree 402 */ 403 analyzeTree: function() { 404 var stats = { 405 number_items: this.items.length, 406 depth: 1 407 }, tmp; 408 409 if (this.northWest !== null) { 410 tmp = this.northWest.analyzeTree(); 411 stats.number_items += tmp.number_items; 412 stats.depth = Math.max(stats.depth, 1 + tmp.depth); 413 } 414 if (this.southWest !== null) { 415 tmp = this.southWest.analyzeTree(); 416 stats.number_items += tmp.number_items; 417 stats.depth = Math.max(stats.depth, 1 + tmp.depth); 418 } 419 if (this.northEast !== null) { 420 tmp = this.northEast.analyzeTree(); 421 stats.number_items += tmp.number_items; 422 stats.depth = Math.max(stats.depth, 1 + tmp.depth); 423 } 424 if (this.southEast !== null) { 425 tmp = this.southEast.analyzeTree(); 426 stats.number_items += tmp.number_items; 427 stats.depth = Math.max(stats.depth, 1 + tmp.depth); 428 } 429 430 return stats; 431 }, 432 433 /** 434 * Generate data to plot the box quadtree as curve using updateDataArray. 435 * 436 * @returns {Array} containing arrays dataX and dataY 437 * 438 * @example 439 * 440 * // qdt contains a BoxQuadtree 441 * 442 * var qdtcurve = board.create('curve', [[], []], { strokeWidth: 1, strokeColor: '#0000ff', strokeOpacity: 0.3 }); 443 * qdtcurve.updateDataArray = function () { 444 * var ret = qdt.plot(); 445 * 446 * this.dataX = ret[0]; 447 * this.dataY = ret[1]; 448 * console.log(qdt.analyzeTree()); 449 * }; 450 * board.update(); 451 */ 452 plot: function () { 453 var dataX = [], 454 dataY = [], 455 ret; 456 457 dataX.push(this.bbox[0]); dataY.push(this.bbox[3]); 458 dataX.push(this.bbox[2]); dataY.push(this.bbox[3]); 459 dataX.push(this.bbox[2]); dataY.push(this.bbox[1]); 460 dataX.push(this.bbox[0]); dataY.push(this.bbox[1]); 461 dataX.push(this.bbox[0]); dataY.push(this.bbox[3]); 462 dataX.push(NaN); dataY.push(NaN); 463 464 if (this.northWest !== null) { 465 ret = this.northWest.plot(); 466 Type.concat(dataX, ret[0]); 467 Type.concat(dataY, ret[1]); 468 } 469 470 if (this.northEast !== null) { 471 ret = this.northEast.plot(); 472 Type.concat(dataX, ret[0]); 473 Type.concat(dataY, ret[1]); 474 } 475 476 if (this.southEast !== null) { 477 ret = this.southEast.plot(); 478 Type.concat(dataX, ret[0]); 479 Type.concat(dataY, ret[1]); 480 } 481 482 if (this.southWest !== null) { 483 ret = this.southWest.plot(); 484 Type.concat(dataX, ret[0]); 485 Type.concat(dataY, ret[1]); 486 } 487 488 return [dataX, dataY]; 489 } 490 } 491 ); 492 493 export default Mat.BoxQuadtree; 494