1 /*
  2     Copyright 2008-2024
  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 <https://www.gnu.org/licenses/>
 29     and <https://opensource.org/licenses/MIT/>.
 30  */
 31 
 32 /*global JXG:true, define: true*/
 33 /*jslint nomen: true, plusplus: true*/
 34 
 35 import Mat from "./math.js";
 36 import Geometry from "./geometry.js";
 37 import Type from "../utils/type.js";
 38 
 39 /**
 40  * Instantiate a new quadtree.
 41  *
 42  * @name JXG.Math.Quadtree
 43  * @exports Mat.Quadtree as JXG.Math.Quadtree
 44  * @param {Array} bbox Bounding box of the new quad (sub)tree.
 45  * @param {Object} config Configuration object. Default value: to {capacity: 10}
 46  * @param {Object} [parent] Parent object or null if root.
 47  *
 48  * @constructor
 49  */
 50 Mat.Quadtree = function (bbox, config, parent) {
 51     config = config || {
 52         capacity: 10,
 53         pointType: 'coords'
 54     };
 55 
 56     /**
 57      * Configuration object for quadtree.
 58      *
 59      * @name JXG.Math.Quadtree.config
 60      * @type Object
 61      */
 62     this.config = {};
 63     /**
 64      * The maximum number of points stored in a quadtree node
 65      * before it is subdivided.
 66      * @name JXG.Math.Quadtree.config#capacity
 67      * @type Number
 68      * @default 10
 69      */
 70     this.config.capacity = config.capacity || 10;
 71 
 72     /**
 73      * Type of a point object. Possible values are:
 74      * 'coords', 'object'.
 75      * @name JXG.Math.Quadtree.config#pointType
 76      * @type String
 77      * @default 'coords'
 78      */
 79     this.config.pointType = config.pointType || 'coords';
 80 
 81     /**
 82      * Point storage.
 83      * @name JXG.Math.Quadtree#points
 84      * @type Array
 85      */
 86     this.points = [];
 87 
 88     this.xlb = bbox[0];
 89     this.xub = bbox[2];
 90     this.ylb = bbox[3];
 91     this.yub = bbox[1];
 92 
 93     /**
 94      * Parent quadtree or null if there is not parent.
 95      *
 96      * @name JXG.Math.Quadtree#parent
 97      * @type JXG.Math.Quadtree
 98      *
 99      */
100     this.parent = parent || null;
101 
102     /**
103      * In a subdivided quadtree this represents the top left subtree.
104      * @name JXG.Math.Quadtree#northWest
105      * @type JXG.Math.Quadtree
106      */
107     this.northWest = null;
108 
109     /**
110      * In a subdivided quadtree this represents the top right subtree.
111      * @name JXG.Math.Quadtree#northEast
112      * @type JXG.Math.Quadtree
113      */
114     this.northEast = null;
115 
116     /**
117      * In a subdivided quadtree this represents the bottom right subtree.
118      * @name JXG.Math.Quadtree#southEast
119      * @type JXG.Math.Quadtree
120      */
121     this.southEast = null;
122 
123     /**
124      * In a subdivided quadtree this represents the bottom left subtree.
125      * @name JXG.Math.Quadtree#southWest
126      * @type JXG.Math.Quadtree
127      */
128     this.southWest = null;
129 
130 };
131 
132 Type.extend(
133     Mat.Quadtree.prototype,
134     /** @lends JXG.Math.Quadtree.prototype */ {
135         /**
136          * Checks if the given coordinates are inside of the boundaries of the quadtree.
137          * The quadtree is open to the left and botton and closed to
138          * right and top.
139          *
140          * @param {Number} x
141          * @param {Number} y
142          * @returns {Boolean}
143          */
144         contains: function (x, y) {
145             return this.xlb < x && x <= this.xub && this.ylb < y && y <= this.yub;
146         },
147 
148         /**
149          * Insert a new point into this quadtree if it is inside of
150          * the quadtree's boundaries.
151          *
152          * @param {JXG.Coords} p
153          * @returns {Boolean} true if insert succeeded, false otherwise.
154          */
155         insert: function (p) {
156             switch (this.config.pointType) {
157                 case 'coords':
158                     if (!this.contains(p.usrCoords[1], p.usrCoords[2])) {
159                         return false;
160                     }
161                     break;
162                 case 'object':
163                     if (!this.contains(p.x, p.y)) {
164                         return false;
165                     }
166                     break;
167             }
168 
169             if (this.points.length < this.config.capacity && this.northWest === null) {
170                 this.points.push(p);
171                 return true;
172             }
173 
174             // At this point the point has to be inserted into a subtree.
175             if (this.northWest === null) {
176                 this.subdivide();
177             }
178 
179             if (this.northWest.insert(p)) {
180                 return true;
181             }
182 
183             if (this.northEast.insert(p)) {
184                 return true;
185             }
186 
187             if (this.southEast.insert(p)) {
188                 return true;
189             }
190 
191             return !!this.southWest.insert(p);
192         },
193 
194         /**
195          * Subdivide the quadtree.
196          */
197         subdivide: function () {
198             var // i, le,
199                 cx = this.xlb + (this.xub - this.xlb) * 0.5,
200                 cy = this.ylb + (this.yub - this.ylb) * 0.5;
201 
202             this.northWest = new Mat.Quadtree([this.xlb, this.yub, cx, cy], this.config, this);
203             this.northEast = new Mat.Quadtree([cx, this.yub, this.xub, cy], this.config, this);
204             this.southEast = new Mat.Quadtree([this.xlb, cy, cx, this.ylb], this.config, this);
205             this.southWest = new Mat.Quadtree([cx, cy, this.xub, this.ylb], this.config, this);
206 
207             // for (i = 0; i < le; i++) {
208             //     if (this.northWest.insert(this.points[i])) { continue; }
209             //     if (this.northEast.insert(this.points[i])) { continue; }
210             //     if (this.southEast.insert(this.points[i])) { continue; }
211             //     this.southWest.insert(this.points[i]);
212             // }
213         },
214 
215         /**
216          * Internal _query method that lacks adjustment of the parameter.
217          * @name JXG.Math.Quadtree#_query
218          * @param {Number} x
219          * @param {Number} y
220          * @returns {Boolean|JXG.Quadtree} The quadtree if the point is found, false
221          * if none of the quadtrees contains the point (i.e. the point is not inside
222          * the root tree's AABB,i.e. axis-aligned bounding box).
223          * @private
224          */
225         _query: function (x, y) {
226             var r;
227 
228             if (this.contains(x, y)) {
229                 if (this.northWest === null) {
230                     return this;
231                 }
232 
233                 r = this.northWest._query(x, y);
234                 if (r) {
235                     return r;
236                 }
237 
238                 r = this.northEast._query(x, y);
239                 if (r) {
240                     return r;
241                 }
242 
243                 r = this.southEast._query(x, y);
244                 if (r) {
245                     return r;
246                 }
247 
248                 r = this.southWest._query(x, y);
249                 if (r) {
250                     return r;
251                 }
252             }
253 
254             return false;
255         },
256 
257         /**
258          * Retrieve the smallest quad tree that contains the given coordinate pair.
259          * @name JXG.Math.Quadtree#query
260          * @param {JXG.Coords|Number} xp
261          * @param {Number} y
262          * @returns {Boolean|JXG.Quadtree} The quadtree if the point is found, false
263          * if none of the quadtrees contains the point (i.e. the point is not inside
264          * the root tree's AABB (Axis-Aligned Bounding Box)).
265          */
266         query: function (xp, y) {
267             var _x, _y;
268 
269             if (Type.exists(y)) {
270                 _x = xp;
271                 _y = y;
272             } else {
273                 _x = xp.usrCoords[1];
274                 _y = xp.usrCoords[2];
275             }
276 
277             return this._query(_x, _y);
278         },
279 
280         /**
281          * Check if the quadtree has a point which is inside of a sphere of
282          * radius tol around [x, y].
283          * @param {Number} x
284          * @param {Number} y
285          * @param {Number} tol
286          * @returns {Boolean}
287          */
288         hasPoint: function (x, y, tol) {
289             var r, i, le;
290 
291             if (this.contains(x, y)) {
292                 le = this.points.length;
293 
294                 switch (this.config.pointType) {
295                     case 'coords':
296                         for (i = 0; i < le; i++) {
297                             if (Geometry.distance([x, y], this.points[i].usrCoords.slice(1), 2) < tol) {
298                                 return true;
299                             }
300                         }
301                         break;
302                     case 'object':
303                         for (i = 0; i < le; i++) {
304                             if (Geometry.distance([x, y], [this.points[i].x, this.points[i].y], 2) < tol) {
305                                 return true;
306                             }
307                         }
308                         break;
309                }
310 
311 
312                 if (this.northWest === null) {
313                     return false;
314                 }
315 
316                 r = this.northWest.hasPoint(x, y, tol);
317                 if (r) {
318                     return r;
319                 }
320 
321                 r = this.northEast.hasPoint(x, y, tol);
322                 if (r) {
323                     return r;
324                 }
325 
326                 r = this.southEast.hasPoint(x, y, tol);
327                 if (r) {
328                     return r;
329                 }
330 
331                 r = this.southWest.hasPoint(x, y, tol);
332                 if (r) {
333                     return r;
334                 }
335             }
336 
337             return false;
338         },
339 
340         /**
341          *
342          * @returns {Array}
343          */
344         getAllPoints: function() {
345             var pointsList = [];
346             this.getAllPointsRecursive(pointsList);
347             return pointsList;
348         },
349 
350         /**
351          *
352          * @param {Array} pointsList
353          * @private
354          */
355         getAllPointsRecursive(pointsList) {
356             Array.prototype.push.apply(pointsList, this.points.slice());
357 
358             if (this.northWest === null) {
359                 return;
360             }
361 
362             this.northWest.getAllPointsRecursive(pointsList);
363             this.northEast.getAllPointsRecursive(pointsList);
364             this.southEast.getAllPointsRecursive(pointsList);
365             this.southWest.getAllPointsRecursive(pointsList);
366         }
367 
368     }
369 );
370 
371 export default Mat.Quadtree;
372