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 return !!this.southWest.insert(p); 139 140 141 }, 142 143 /** 144 * Subdivide the quad tree. 145 */ 146 subdivide: function () { 147 var i, 148 l = this.points.length, 149 mx = this.xlb + (this.xub - this.xlb) / 2, 150 my = this.ylb + (this.yub - this.ylb) / 2; 151 152 this.northWest = new Quadtree([this.xlb, this.yub, mx, my]); 153 this.northEast = new Quadtree([mx, this.yub, this.xub, my]); 154 this.southEast = new Quadtree([this.xlb, my, mx, this.ylb]); 155 this.southWest = new Quadtree([mx, my, this.xub, this.ylb]); 156 157 for (i = 0; i < l; i += 1) { 158 this.northWest.insert(this.points[i]); 159 this.northEast.insert(this.points[i]); 160 this.southEast.insert(this.points[i]); 161 this.southWest.insert(this.points[i]); 162 } 163 }, 164 165 /** 166 * Internal _query method that lacks adjustment of the parameter. 167 * @param {Number} x 168 * @param {Number} y 169 * @returns {Boolean|JXG.Quadtree} The quad tree if the point is found, false 170 * if none of the quad trees contains the point (i.e. the point is not inside 171 * the root tree's AABB). 172 * @private 173 */ 174 _query: function (x, y) { 175 var r; 176 177 if (this.contains(x, y)) { 178 if (this.northWest === null) { 179 return this; 180 } 181 182 r = this.northWest._query(x, y); 183 if (r) { 184 return r; 185 } 186 187 r = this.northEast._query(x, y); 188 if (r) { 189 return r; 190 } 191 192 r = this.southEast._query(x, y); 193 if (r) { 194 return r; 195 } 196 197 r = this.southWest._query(x, y); 198 if (r) { 199 return r; 200 } 201 } 202 203 return false; 204 }, 205 206 /** 207 * Retrieve the smallest quad tree that contains the given point. 208 * @param {JXG.Coords|Number} xp 209 * @param {Number} y 210 * @returns {Boolean|JXG.Quadtree} The quad tree if the point is found, false 211 * if none of the quad trees contains the point (i.e. the point is not inside 212 * the root tree's AABB). 213 * @private 214 */ 215 query: function (xp, y) { 216 var _x, _y; 217 218 if (Type.exists(y)) { 219 _x = xp; 220 _y = y; 221 } else { 222 _x = xp.usrCoords[1]; 223 _y = xp.usrCoords[2]; 224 } 225 226 return this._query(_x, _y); 227 } 228 }); 229 230 Mat.Quadtree = Quadtree; 231 232 return Quadtree; 233 }); 234