1 /* 2 Copyright 2008-2021 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 <http://www.gnu.org/licenses/> 29 and <http://opensource.org/licenses/MIT/>. 30 */ 31 32 33 /*global JXG:true, define: true*/ 34 /*jslint nomen: true, plusplus: true*/ 35 36 /* depends: 37 math/math 38 utils/type 39 */ 40 41 define(['math/math', 'utils/type'], function (Mat, Type) { 42 43 "use strict"; 44 45 /** 46 * Instantiate a new quad tree. 47 * 48 * @name JXG.Math.Quadtree 49 * @exports Mat.Quadtree as JXG.Math.Quadtree 50 * @param {Array} bbox Bounding box of the new quad (sub)tree. 51 * @constructor 52 */ 53 Mat.Quadtree = function (bbox) { 54 /** 55 * The maximum number of points stored in a quad tree node 56 * before it is subdivided. 57 * @type Number 58 * @default 10 59 */ 60 this.capacity = 10; 61 62 /** 63 * Point storage. 64 * @name JXG.Math.Quadtree#points 65 * @type Array 66 */ 67 this.points = []; 68 this.xlb = bbox[0]; 69 this.xub = bbox[2]; 70 this.ylb = bbox[3]; 71 this.yub = bbox[1]; 72 73 /** 74 * In a subdivided quad tree this represents the top left subtree. 75 * @name JXG.Math.Quadtree#northWest 76 * @type JXG.Math.Quadtree 77 */ 78 this.northWest = null; 79 80 /** 81 * In a subdivided quad tree this represents the top right subtree. 82 * @name JXG.Math.Quadtree#northEast 83 * @type JXG.Math.Quadtree 84 */ 85 this.northEast = null; 86 87 /** 88 * In a subdivided quad tree this represents the bottom right subtree. 89 * @name JXG.Math.Quadtree#southEast 90 * @type JXG.Math.Quadtree 91 */ 92 this.southEast = null; 93 94 /** 95 * In a subdivided quad tree this represents the bottom left subtree. 96 * @name JXG.Math.Quadtree#southWest 97 * @type JXG.Math.Quadtree 98 */ 99 this.southWest = null; 100 }; 101 102 Type.extend(Mat.Quadtree.prototype, /** @lends JXG.Math.Quadtree.prototype */ { 103 /** 104 * Checks if the given coordinates are inside the quad tree. 105 * @param {Number} x 106 * @param {Number} y 107 * @returns {Boolean} 108 */ 109 contains: function (x, y) { 110 return this.xlb < x && x <= this.xub && this.ylb < y && y <= this.yub; 111 }, 112 113 /** 114 * Insert a new point into this quad tree. 115 * @param {JXG.Coords} p 116 * @returns {Boolean} 117 */ 118 insert: function (p) { 119 if (!this.contains(p.usrCoords[1], p.usrCoords[2])) { 120 return false; 121 } 122 123 if (this.points.length < this.capacity) { 124 this.points.push(p); 125 return true; 126 } 127 128 if (this.northWest === null) { 129 this.subdivide(); 130 } 131 132 if (this.northWest.insert(p)) { 133 return true; 134 } 135 136 if (this.northEast.insert(p)) { 137 return true; 138 } 139 140 if (this.southEast.insert(p)) { 141 return true; 142 } 143 144 return !!this.southWest.insert(p); 145 146 147 }, 148 149 /** 150 * Subdivide the quad tree. 151 */ 152 subdivide: function () { 153 var i, 154 l = this.points.length, 155 mx = this.xlb + (this.xub - this.xlb) / 2, 156 my = this.ylb + (this.yub - this.ylb) / 2; 157 158 this.northWest = new Quadtree([this.xlb, this.yub, mx, my]); 159 this.northEast = new Quadtree([mx, this.yub, this.xub, my]); 160 this.southEast = new Quadtree([this.xlb, my, mx, this.ylb]); 161 this.southWest = new Quadtree([mx, my, this.xub, this.ylb]); 162 163 for (i = 0; i < l; i += 1) { 164 this.northWest.insert(this.points[i]); 165 this.northEast.insert(this.points[i]); 166 this.southEast.insert(this.points[i]); 167 this.southWest.insert(this.points[i]); 168 } 169 }, 170 171 /** 172 * Internal _query method that lacks adjustment of the parameter. 173 * @name JXG.Math.Quadtree#_query 174 * @param {Number} x 175 * @param {Number} y 176 * @returns {Boolean|JXG.Quadtree} The quad tree if the point is found, false 177 * if none of the quad trees contains the point (i.e. the point is not inside 178 * the root tree's AABB). 179 * @private 180 */ 181 _query: function (x, y) { 182 var r; 183 184 if (this.contains(x, y)) { 185 if (this.northWest === null) { 186 return this; 187 } 188 189 r = this.northWest._query(x, y); 190 if (r) { 191 return r; 192 } 193 194 r = this.northEast._query(x, y); 195 if (r) { 196 return r; 197 } 198 199 r = this.southEast._query(x, y); 200 if (r) { 201 return r; 202 } 203 204 r = this.southWest._query(x, y); 205 if (r) { 206 return r; 207 } 208 } 209 210 return false; 211 }, 212 213 /** 214 * Retrieve the smallest quad tree that contains the given point. 215 * @name JXG.Math.Quadtree#_query 216 * @param {JXG.Coords|Number} xp 217 * @param {Number} y 218 * @returns {Boolean|JXG.Quadtree} The quad tree if the point is found, false 219 * if none of the quad trees contains the point (i.e. the point is not inside 220 * the root tree's AABB). 221 * @private 222 */ 223 query: function (xp, y) { 224 var _x, _y; 225 226 if (Type.exists(y)) { 227 _x = xp; 228 _y = y; 229 } else { 230 _x = xp.usrCoords[1]; 231 _y = xp.usrCoords[2]; 232 } 233 234 return this._query(_x, _y); 235 } 236 }); 237 238 return Mat.Quadtree; 239 }); 240