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