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