1 /* 2 Copyright 2008-2023 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"; 36 import Geometry from "./geometry"; 37 import Type from "../utils/type"; 38 39 /** 40 * Instantiate a new quad tree. 41 * 42 * @name JXG.Math.Quadtree 43 * @exports Mat.Quadtree as JXG.Math.Quadtree 44 * @param {Array} bbox Bounding box of the new quad (sub)tree. 45 * @param {Object} config Configuration object. Default value: to {capacity: 10} 46 * 47 * @constructor 48 */ 49 Mat.Quadtree = function (bbox, config, parent) { 50 config = config || { 51 capacity: 10, 52 pointType: 'coords' 53 }; 54 55 this.config = {}; 56 /** 57 * The maximum number of points stored in a quad tree node 58 * before it is subdivided. 59 * @type Number 60 * @default 10 61 */ 62 this.config.capacity = config.capacity || 10; 63 64 /** 65 * Type of a point object. Possible values are: 66 * 'coords', 'object'. 67 * @type String 68 * @default 'coords' 69 */ 70 this.config.pointType = config.pointType || 'coords'; 71 72 /** 73 * Point storage. 74 * @name JXG.Math.Quadtree#points 75 * @type Array 76 */ 77 this.points = []; 78 this.xlb = bbox[0]; 79 this.xub = bbox[2]; 80 this.ylb = bbox[3]; 81 this.yub = bbox[1]; 82 83 /** 84 * Parent quad tree or null if there is not parent. 85 * 86 * @name JXG.Math.Quadtree#northWest 87 * @type JXG.Math.Quadtree 88 * 89 */ 90 this.parent = parent || null; 91 92 /** 93 * In a subdivided quad tree this represents the top left subtree. 94 * @name JXG.Math.Quadtree#northWest 95 * @type JXG.Math.Quadtree 96 */ 97 this.northWest = null; 98 99 /** 100 * In a subdivided quad tree this represents the top right subtree. 101 * @name JXG.Math.Quadtree#northEast 102 * @type JXG.Math.Quadtree 103 */ 104 this.northEast = null; 105 106 /** 107 * In a subdivided quad tree this represents the bottom right subtree. 108 * @name JXG.Math.Quadtree#southEast 109 * @type JXG.Math.Quadtree 110 */ 111 this.southEast = null; 112 113 /** 114 * In a subdivided quad tree this represents the bottom left subtree. 115 * @name JXG.Math.Quadtree#southWest 116 * @type JXG.Math.Quadtree 117 */ 118 this.southWest = null; 119 120 }; 121 122 Type.extend( 123 Mat.Quadtree.prototype, 124 /** @lends JXG.Math.Quadtree.prototype */ { 125 /** 126 * Checks if the given coordinates are inside the quad tree. 127 * @param {Number} x 128 * @param {Number} y 129 * @returns {Boolean} 130 */ 131 contains: function (x, y) { 132 return this.xlb < x && x <= this.xub && this.ylb < y && y <= this.yub; 133 }, 134 135 /** 136 * Insert a new point into this quad tree. Do this only, 137 * if the point is not yet in the quadtree (test exactly). 138 * 139 * @param {JXG.Coords} p 140 * @returns {Boolean} 141 */ 142 insert: function (p) { 143 switch (this.config.pointType) { 144 case 'coords': 145 if (!this.contains(p.usrCoords[1], p.usrCoords[2])) { 146 return false; 147 } 148 break; 149 case 'object': 150 if (!this.contains(p.x, p.y)) { 151 return false; 152 } 153 break; 154 } 155 156 if (this.points.length < this.config.capacity) { 157 this.points.push(p); 158 return true; 159 } 160 161 if (this.northWest === null) { 162 this.subdivide(); 163 } 164 165 if (this.northWest.insert(p)) { 166 return true; 167 } 168 169 if (this.northEast.insert(p)) { 170 return true; 171 } 172 173 if (this.southEast.insert(p)) { 174 return true; 175 } 176 177 return !!this.southWest.insert(p); 178 }, 179 180 /** 181 * Subdivide the quad tree. 182 */ 183 subdivide: function () { 184 var i, 185 le = this.points.length, 186 mx = this.xlb + (this.xub - this.xlb) / 2, 187 my = this.ylb + (this.yub - this.ylb) / 2; 188 189 this.northWest = new Mat.Quadtree([this.xlb, this.yub, mx, my], this.config, this); 190 this.northEast = new Mat.Quadtree([mx, this.yub, this.xub, my], this.config, this); 191 this.southEast = new Mat.Quadtree([this.xlb, my, mx, this.ylb], this.config, this); 192 this.southWest = new Mat.Quadtree([mx, my, this.xub, this.ylb], this.config, this); 193 194 for (i = 0; i < le; i += 1) { 195 this.insert(this.points[i]); 196 } 197 198 // We empty this node points 199 this.points.length = 0; 200 this.points = []; 201 }, 202 203 /** 204 * Internal _query method that lacks adjustment of the parameter. 205 * @name JXG.Math.Quadtree#_query 206 * @param {Number} x 207 * @param {Number} y 208 * @returns {Boolean|JXG.Quadtree} The quad tree if the point is found, false 209 * if none of the quad trees contains the point (i.e. the point is not inside 210 * the root tree's AABB). 211 * @private 212 */ 213 _query: function (x, y) { 214 var r; 215 216 if (this.contains(x, y)) { 217 if (this.northWest === null) { 218 return this; 219 } 220 221 r = this.northWest._query(x, y); 222 if (r) { 223 return r; 224 } 225 226 r = this.northEast._query(x, y); 227 if (r) { 228 return r; 229 } 230 231 r = this.southEast._query(x, y); 232 if (r) { 233 return r; 234 } 235 236 r = this.southWest._query(x, y); 237 if (r) { 238 return r; 239 } 240 } 241 242 return false; 243 }, 244 245 /** 246 * Retrieve the smallest quad tree that contains the given coordinate pair. 247 * @name JXG.Math.Quadtree#_query 248 * @param {JXG.Coords|Number} xp 249 * @param {Number} y 250 * @returns {Boolean|JXG.Quadtree} The quad tree if the point is found, false 251 * if none of the quad trees contains the point (i.e. the point is not inside 252 * the root tree's AABB). 253 */ 254 query: function (xp, y) { 255 var _x, _y; 256 257 if (Type.exists(y)) { 258 _x = xp; 259 _y = y; 260 } else { 261 _x = xp.usrCoords[1]; 262 _y = xp.usrCoords[2]; 263 } 264 265 return this._query(_x, _y); 266 }, 267 268 /** 269 * 270 * @param {*} x 271 * @param {*} y 272 * @param {*} tol 273 * @returns {Boolean} 274 */ 275 isIn: function (x, y, tol) { 276 var r, i, le; 277 278 if (this.contains(x, y)) { 279 le = this.points.length; 280 281 switch (this.config.pointType) { 282 case 'coords': 283 for (i = 0; i < le; i++) { 284 if (Geometry.distance([x, y], this.points[i].usrCoords.slice(1), 2) < tol) { 285 return true; 286 } 287 } 288 break; 289 case 'object': 290 for (i = 0; i < le; i++) { 291 if (Geometry.distance([x, y], [this.points[i].x, this.points[i].y], 2) < tol) { 292 return true; 293 } 294 } 295 break; 296 } 297 298 299 if (this.northWest === null) { 300 return false; 301 } 302 303 r = this.northWest.isIn(x, y, tol); 304 if (r) { 305 return r; 306 } 307 308 r = this.northEast.isIn(x, y, tol); 309 if (r) { 310 return r; 311 } 312 313 r = this.southEast.isIn(x, y, tol); 314 if (r) { 315 return r; 316 } 317 318 r = this.southWest.isIn(x, y, tol); 319 if (r) { 320 return r; 321 } 322 } 323 324 return false; 325 }, 326 327 /** 328 * 329 * @returns {Array} 330 */ 331 getAllPoints: function() { 332 var pointsList = []; 333 this.getAllPointsRecursive(pointsList); 334 return pointsList; 335 }, 336 337 /** 338 * 339 * @param {Array} pointsList 340 * @private 341 */ 342 getAllPointsRecursive(pointsList) { 343 if (this.northWest === null) { 344 Array.prototype.push.apply(pointsList, this.points.slice()); 345 return; 346 } 347 348 this.northWest.getAllPointsRecursive(pointsList); 349 this.northEast.getAllPointsRecursive(pointsList); 350 this.southEast.getAllPointsRecursive(pointsList); 351 this.southWest.getAllPointsRecursive(pointsList); 352 } 353 354 } 355 ); 356 357 export default Mat.Quadtree; 358