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