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 Type from "../utils/type";
 37 
 38 /**
 39  * Instantiate a new quad tree.
 40  *
 41  * @name JXG.Math.Quadtree
 42  * @exports Mat.Quadtree as JXG.Math.Quadtree
 43  * @param {Array} bbox Bounding box of the new quad (sub)tree.
 44  * @constructor
 45  */
 46 Mat.Quadtree = function (bbox) {
 47     /**
 48      * The maximum number of points stored in a quad tree node
 49      * before it is subdivided.
 50      * @type Number
 51      * @default 10
 52      */
 53     this.capacity = 10;
 54 
 55     /**
 56      * Point storage.
 57      * @name JXG.Math.Quadtree#points
 58      * @type Array
 59      */
 60     this.points = [];
 61     this.xlb = bbox[0];
 62     this.xub = bbox[2];
 63     this.ylb = bbox[3];
 64     this.yub = bbox[1];
 65 
 66     /**
 67      * In a subdivided quad tree this represents the top left subtree.
 68      * @name JXG.Math.Quadtree#northWest
 69      * @type JXG.Math.Quadtree
 70      */
 71     this.northWest = null;
 72 
 73     /**
 74      * In a subdivided quad tree this represents the top right subtree.
 75      * @name JXG.Math.Quadtree#northEast
 76      * @type JXG.Math.Quadtree
 77      */
 78     this.northEast = null;
 79 
 80     /**
 81      * In a subdivided quad tree this represents the bottom right subtree.
 82      * @name JXG.Math.Quadtree#southEast
 83      * @type JXG.Math.Quadtree
 84      */
 85     this.southEast = null;
 86 
 87     /**
 88      * In a subdivided quad tree this represents the bottom left subtree.
 89      * @name JXG.Math.Quadtree#southWest
 90      * @type JXG.Math.Quadtree
 91      */
 92     this.southWest = null;
 93 };
 94 
 95 Type.extend(
 96     Mat.Quadtree.prototype,
 97     /** @lends JXG.Math.Quadtree.prototype */ {
 98         /**
 99          * Checks if the given coordinates are inside the quad tree.
100          * @param {Number} x
101          * @param {Number} y
102          * @returns {Boolean}
103          */
104         contains: function (x, y) {
105             return this.xlb < x && x <= this.xub && this.ylb < y && y <= this.yub;
106         },
107 
108         /**
109          * Insert a new point into this quad tree.
110          * @param {JXG.Coords} p
111          * @returns {Boolean}
112          */
113         insert: function (p) {
114             if (!this.contains(p.usrCoords[1], p.usrCoords[2])) {
115                 return false;
116             }
117 
118             if (this.points.length < this.capacity) {
119                 this.points.push(p);
120                 return true;
121             }
122 
123             if (this.northWest === null) {
124                 this.subdivide();
125             }
126 
127             if (this.northWest.insert(p)) {
128                 return true;
129             }
130 
131             if (this.northEast.insert(p)) {
132                 return true;
133             }
134 
135             if (this.southEast.insert(p)) {
136                 return true;
137             }
138 
139             return !!this.southWest.insert(p);
140         },
141 
142         /**
143          * Subdivide the quad tree.
144          */
145         subdivide: function () {
146             var i,
147                 l = this.points.length,
148                 mx = this.xlb + (this.xub - this.xlb) / 2,
149                 my = this.ylb + (this.yub - this.ylb) / 2;
150 
151             this.northWest = new Mat.Quadtree([this.xlb, this.yub, mx, my]);
152             this.northEast = new Mat.Quadtree([mx, this.yub, this.xub, my]);
153             this.southEast = new Mat.Quadtree([this.xlb, my, mx, this.ylb]);
154             this.southWest = new Mat.Quadtree([mx, my, this.xub, this.ylb]);
155 
156             for (i = 0; i < l; i += 1) {
157                 this.northWest.insert(this.points[i]);
158                 this.northEast.insert(this.points[i]);
159                 this.southEast.insert(this.points[i]);
160                 this.southWest.insert(this.points[i]);
161             }
162         },
163 
164         /**
165          * Internal _query method that lacks adjustment of the parameter.
166          * @name JXG.Math.Quadtree#_query
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          * @name JXG.Math.Quadtree#_query
209          * @param {JXG.Coords|Number} xp
210          * @param {Number} y
211          * @returns {Boolean|JXG.Quadtree} The quad tree if the point is found, false
212          * if none of the quad trees contains the point (i.e. the point is not inside
213          * the root tree's AABB).
214          * @private
215          */
216         query: function (xp, y) {
217             var _x, _y;
218 
219             if (Type.exists(y)) {
220                 _x = xp;
221                 _y = y;
222             } else {
223                 _x = xp.usrCoords[1];
224                 _y = xp.usrCoords[2];
225             }
226 
227             return this._query(_x, _y);
228         }
229     }
230 );
231 
232 export default Mat.Quadtree;
233