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     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             return !!this.southWest.insert(p);
139 
140 
141         },
142 
143         /**
144          * Subdivide the quad tree.
145          */
146         subdivide: function () {
147             var i,
148                 l = this.points.length,
149                 mx = this.xlb + (this.xub - this.xlb) / 2,
150                 my = this.ylb + (this.yub - this.ylb) / 2;
151 
152             this.northWest = new Quadtree([this.xlb, this.yub, mx, my]);
153             this.northEast = new Quadtree([mx, this.yub, this.xub, my]);
154             this.southEast = new Quadtree([this.xlb, my, mx, this.ylb]);
155             this.southWest = new Quadtree([mx, my, this.xub, this.ylb]);
156 
157             for (i = 0; i < l; i += 1) {
158                 this.northWest.insert(this.points[i]);
159                 this.northEast.insert(this.points[i]);
160                 this.southEast.insert(this.points[i]);
161                 this.southWest.insert(this.points[i]);
162             }
163         },
164 
165         /**
166          * Internal _query method that lacks adjustment of the parameter.
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          * @param {JXG.Coords|Number} xp
209          * @param {Number} y
210          * @returns {Boolean|JXG.Quadtree} The quad tree if the point is found, false
211          * if none of the quad trees contains the point (i.e. the point is not inside
212          * the root tree's AABB).
213          * @private
214          */
215         query: function (xp, y) {
216             var _x, _y;
217 
218             if (Type.exists(y)) {
219                 _x = xp;
220                 _y = y;
221             } else {
222                 _x = xp.usrCoords[1];
223                 _y = xp.usrCoords[2];
224             }
225 
226             return this._query(_x, _y);
227         }
228     });
229 
230     Mat.Quadtree = Quadtree;
231 
232     return Quadtree;
233 });
234