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