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 box quadtree.
 40  * A box quadtree stores AABBs, i.e. axis-aligned bounding boxes.
 41  * The box quadtree has four sub-quadtress which maybe null if not needed.
 42  *
 43  * @name JXG.Math.BoxQuadtree
 44  * @exports Mat.BoxQuadtree as JXG.Math.BoxQuadtree
 45  *
 46  * @param {Number} depth Maximum recursion depth.
 47  * @param {Number} capacity Maximum number of items stored in this node.
 48  * @param {Array} [bbox] Optional bounding box of the box quadtree. If not given, the bounding box is
 49  * determined by the items in the insert method. This will only work correctly if the first
 50  * call of insert contains the maximum bounding box.
 51  *
 52  * @constructor
 53  */
 54 Mat.BoxQuadtree = function (depth, capacity, bbox) {
 55     var l, t, r, b;
 56 
 57     // console.log("---------------------------------------")
 58     depth--;
 59 
 60     /**
 61      * Maximum depth of the box quadtree node
 62      * @name JXG.Math.BoxQuadtree#depth
 63      * @type Number
 64      * @private
 65      */
 66     this.depth = depth;
 67 
 68     /**
 69      * Capacity of the box quadtree node
 70      * @name JXG.Math.BoxQuadtree#capacity
 71      * @type Number
 72      * @private
 73      */
 74     this.capacity = capacity;
 75 
 76     /**
 77      * Item storage.
 78      *
 79      * @name JXG.Math.BoxQuadtree#items
 80      * @type Array
 81      * @private
 82      */
 83     this.items = [];
 84 
 85     /**
 86      * In a subdivided quadtree this represents the top left subtree.
 87      * @name JXG.Math.BoxQuadtree#northWest
 88      * @type JXG.Math.BoxQuadtree
 89      * @private
 90      */
 91     this.northWest = null;
 92 
 93     /**
 94      * In a subdivided quadtree this represents the top right subtree.
 95      * @name JXG.Math.BoxQuadtree#northEast
 96      * @type JXG.Math.BoxQuadtree
 97      * @private
 98      */
 99     this.northEast = null;
100 
101     /**
102      * In a subdivided quadtree this represents the bottom right subtree.
103      * @name JXG.Math.BoxQuadtree#southEast
104      * @type JXG.Math.BoxQuadtree
105      * @private
106      */
107     this.southEast = null;
108 
109     /**
110      * In a subdivided quadtree this represents the bottom left subtree.
111      * @name JXG.Math.BoxQuadtree#southWest
112      * @type JXG.Math.BoxQuadtree
113      * @private
114      */
115     this.southWest = null;
116 
117     /**
118      * Bounding box [left, top, right, bottom].
119      *
120      * @name JXG.Math.BoxQuadtree#bbox
121      * @type Array
122      * @private
123      */
124     this.bbox = null;
125 
126     /**
127      * x-coordinate of bounding box center.
128      *
129      * @name JXG.Math.BoxQuadtree#cx
130      * @type Number
131      * @private
132      */
133     this.cx = null;
134 
135     /**
136      * y-coordinate of bounding box center.
137      *
138      * @name JXG.Math.BoxQuadtree#cy
139      * @type Number
140      * @private
141      */
142     this.cy = null;
143 
144     if (bbox) {
145         // Take supplied bounding box
146         l = bbox[0];
147         t = bbox[1];
148         r = bbox[2];
149         b = bbox[3];
150         this.cx = (l + r) * 0.5;
151         this.cy = (t + b) * 0.5;
152         this.bbox = [l, t, r, b];
153     }
154 };
155 
156 Type.extend(
157     Mat.BoxQuadtree.prototype,
158     /** @lends JXG.Math.BoxQuadtree.prototype */ {
159 
160         /**
161          * Insert an array of items into the box quadtree. An item is an object
162          * containing at least the properties
163          * <ul>
164          *  <li> xlb: lower bound on x
165          *  <li> xub: upper bound on x
166          *  <li> ylb: lower bound on y
167          *  <li> yub: upper bound on y
168          * </ul>
169          * which define the axis-aligned bounding box (AABB) of that item. Additionally,
170          * more properties can be given.
171          *
172          * @param {Array} items to be inserted
173          * @returns {Object} reference to the box quadtree
174          */
175         insert: function(items) {
176             var i, le,
177                 l, t, r, b,
178                 it,
179                 nw_it = [],
180                 ne_it = [],
181                 sw_it = [],
182                 se_it = [],
183                 in_nw, in_ne, in_sw, in_se;
184 
185 
186             if (this.bbox === null) {
187                 // Use bounding box of the supplied items
188                 le  = items.length;
189                 l = b = Infinity;
190                 r = t = -Infinity;
191                 for (i = 0; i < items.length; i++) {
192                     it = items[i];
193                     l = (it.xlb < l) ? it.xlb : l;
194                     t = (it.yub > t) ? it.yub : t;
195                     r = (it.xub > r) ? it.xub : r;
196                     b = (it.ylb < b) ? it.ylb : b;
197                 }
198                 this.cx = (l + r) * 0.5;
199                 this.cy = (t + b) * 0.5;
200                 this.bbox = [l, t, r, b];
201             } else {
202                 l = this.bbox[0];
203                 t = this.bbox[1];
204                 r = this.bbox[2];
205                 b = this.bbox[3];
206             }
207 
208             if (this.depth === 0 || this.items.length + items.length < this.capacity) {
209                 // if (items.length + items.length < this.capacity) {
210                 //     console.log("Capacity sufficient, D=", this.depth, this.items.length, items.length);
211                 // }
212                 // if (depth === 0) {console.log("Max depth reached", items.length, this.capacity); }
213 
214                 this.items = this.items.concat(items);
215                 return this;
216             }
217 
218             le  = items.length;
219             for (i = 0; i < le; i++) {
220                 it = items[i];
221                 in_nw = it.xlb <= this.cx && it.yub > this.cy;
222                 in_sw = it.xlb <= this.cx && it.ylb <= this.cy;
223                 in_ne = it.xub > this.cx && it.yub > this.cy;
224                 in_se = it.xub > this.cx && it.ylb <= this.cy;
225 
226                 // If it overlaps all 4 quadrants then insert it at the current
227                 // depth, otherwise append it to a list to be inserted under every
228                 // quadrant that it overlaps.
229                 if (in_nw && in_ne && in_se && in_sw) {
230                     this.items.push(it);
231                 } else {
232                     if (in_nw) { nw_it.push(it); }
233                     if (in_sw) { sw_it.push(it); }
234                     if (in_ne) { ne_it.push(it); }
235                     if (in_se) { se_it.push(it); }
236                 }
237             }
238 
239             // Create the sub-quadrants, recursively.
240             this.subdivide(nw_it, sw_it, ne_it, se_it, l, t, r, b);
241 
242             return this;
243         },
244 
245         /**
246          * Insert an item into the box quadtree, where an item is an object
247          * containing at least the properties
248          *
249          * <ul>
250          *  <li> xlb: lower bound on x
251          *  <li> xub: upper bound on x
252          *  <li> ylb: lower bound on y
253          *  <li> yub: upper bound on y
254          * </ul>
255          * which define the axis-aligned bounding box (AABB) of that item. Additionally,
256          * more properties can be given.
257          *
258          * @param {Object} it Item to be inserted
259          * @returns {Object} reference to the box quadtree
260          */
261         insertItem: function(it) {
262             var l, t, r, b,
263                 nw_it = [],
264                 ne_it = [],
265                 sw_it = [],
266                 se_it = [],
267                 in_nw, in_ne, in_sw, in_se;
268 
269 
270             if (this.bbox === null) {
271                 // Use bounding box of the supplied items
272                 l = b = Infinity;
273                 r = t = -Infinity;
274 
275                 l = (it.xlb < l) ? it.xlb : l;
276                 t = (it.yub > t) ? it.yub : t;
277                 r = (it.xub > r) ? it.xub : r;
278                 b = (it.ylb < b) ? it.ylb : b;
279 
280                 this.cx = (l + r) * 0.5;
281                 this.cy = (t + b) * 0.5;
282                 this.bbox = [l, t, r, b];
283             } else {
284                 l = this.bbox[0];
285                 t = this.bbox[1];
286                 r = this.bbox[2];
287                 b = this.bbox[3];
288             }
289 
290             if (this.depth === 0 || this.items.length + 1 < this.capacity) {
291                 this.items.push(it);
292                 return this;
293             }
294 
295             in_nw = it.xlb <= this.cx && it.yub > this.cy;
296             in_sw = it.xlb <= this.cx && it.ylb <= this.cy;
297             in_ne = it.xub > this.cx && it.yub > this.cy;
298             in_se = it.xub > this.cx && it.ylb <= this.cy;
299 
300             // If it overlaps all 4 quadrants then insert it at the current
301             // depth, otherwise append it to a list to be inserted under every
302             // quadrant that it overlaps.
303             if (in_nw && in_ne && in_se && in_sw) {
304                 this.items.push(it);
305             } else {
306                 if (in_nw) { nw_it.push(it); }
307                 if (in_sw) { sw_it.push(it); }
308                 if (in_ne) { ne_it.push(it); }
309                 if (in_se) { se_it.push(it); }
310             }
311 
312             // Create the sub-quadrants, recursively.
313             this.subdivide(nw_it, sw_it, ne_it, se_it, l, t, r, b);
314 
315             return this;
316         },
317 
318         /**
319          * Create the sub-quadrants if necessary, recursively
320          * @param {Array} nw_it list of items for northWest subtree
321          * @param {Array} sw_it list of items for southWest subtree
322          * @param {Array} ne_it list of items for northEast subtree
323          * @param {Array} se_it list of items for southEast subtree
324          * @param {Number} l bounding box left
325          * @param {Number} t bounding box top
326          * @param {Number} r bounding box right
327          * @param {Number} b bounding box bottom
328          * @returns {Object} reference to the box quadtree
329          * @private
330          */
331         subdivide: function(nw_it, sw_it, ne_it, se_it, l, t, r, b) {
332             if (nw_it.length > 0) {
333                 if (this.northWest === null) {
334                     this.northWest = new JXG.Math.BoxQuadtree(this.depth, this.capacity, [l, t, this.cx, this.cy]);
335                 }
336                 this.northWest.insert(nw_it);
337             }
338             if (sw_it.length > 0) {
339                 if (this.southWest === null) {
340                     this.southWest = new JXG.Math.BoxQuadtree(this.depth, this.capacity, [l, this.cy, this.cx, b]);
341                 }
342                 this.southWest.insert(sw_it);
343             }
344             if (ne_it.length > 0) {
345                 if (this.northEast === null) {
346                     this.northEast = new JXG.Math.BoxQuadtree(this.depth, this.capacity, [this.cx, t, r, this.cy]);
347                 }
348                 this.northEast.insert(ne_it);
349             }
350             if (se_it.length > 0) {
351                 if (this.southEast === null) {
352                     this.southEast = new JXG.Math.BoxQuadtree(this.depth, this.capacity, [this.cx, this.cy, r, b]);
353                 }
354                 this.southEast.insert(se_it);
355             }
356 
357             return this;
358         },
359 
360         /**
361          * Find all entries of the box quadtree which have an overlap
362          * with the given rectangle (AABB). Items may appear multiple times.
363          *
364          * @param {Array} box AABB of the form [l, t, r, b]
365          * @returns {Array} list of items overlapping with box
366          */
367         find: function(box) {
368             var overlaps = function(item) {
369                     return box[2] >= item.xlb && box[0] <= item.xub &&
370                         box[3] <= item.yub && box[1] >= item.ylb;
371                 },
372                 hits = [],
373                 i, le;
374 
375             le = this.items.length;
376             for (i = 0; i < le; i++) {
377                 if (overlaps(this.items[i])) {
378                     hits.push(this.items[i]);
379                 }
380             }
381 
382             if (this.northWest !== null && box[0] <= this.cx & box[1] >= this.cy) {
383                 hits = hits.concat(this.northWest.find(box));
384             }
385             if (this.southWest !== null && box[0] <= this.cx & box[3] <= this.cy) {
386                 hits = hits.concat(this.southWest.find(box));
387             }
388             if (this.northEast !== null && box[2] >= this.cx & box[1] >= this.cy) {
389                 hits = hits.concat(this.northEast.find(box));
390             }
391             if (this.southEast !== null && box[2] >= this.cx & box[3] <= this.cy) {
392                 hits = hits.concat(this.southEast.find(box));
393             }
394 
395             return hits;
396         },
397 
398         /**
399          * Analyze the box quadtree.
400          *
401          * @returns {Object} data about the box quadtree
402          */
403         analyzeTree: function() {
404             var stats = {
405                     number_items: this.items.length,
406                     depth: 1
407                 }, tmp;
408 
409             if (this.northWest !== null) {
410                 tmp = this.northWest.analyzeTree();
411                 stats.number_items += tmp.number_items;
412                 stats.depth = Math.max(stats.depth, 1 + tmp.depth);
413             }
414             if (this.southWest !== null) {
415                 tmp = this.southWest.analyzeTree();
416                 stats.number_items += tmp.number_items;
417                 stats.depth = Math.max(stats.depth, 1 + tmp.depth);
418             }
419             if (this.northEast !== null) {
420                 tmp = this.northEast.analyzeTree();
421                 stats.number_items += tmp.number_items;
422                 stats.depth = Math.max(stats.depth, 1 + tmp.depth);
423             }
424             if (this.southEast !== null) {
425                 tmp = this.southEast.analyzeTree();
426                 stats.number_items += tmp.number_items;
427                 stats.depth = Math.max(stats.depth, 1 + tmp.depth);
428             }
429 
430             return stats;
431         },
432 
433         /**
434          * Generate data to plot the box quadtree as curve using updateDataArray.
435          *
436          * @returns {Array} containing arrays dataX and dataY
437          *
438          * @example
439          *
440          * // qdt contains a BoxQuadtree
441          *
442          * var qdtcurve = board.create('curve', [[], []], { strokeWidth: 1, strokeColor: '#0000ff', strokeOpacity: 0.3 });
443          * qdtcurve.updateDataArray = function () {
444          *    var ret = qdt.plot();
445          *
446          *    this.dataX = ret[0];
447          *    this.dataY = ret[1];
448          *    console.log(qdt.analyzeTree());
449          * };
450          * board.update();
451          */
452         plot: function () {
453             var dataX = [],
454                 dataY = [],
455                 ret;
456 
457             dataX.push(this.bbox[0]); dataY.push(this.bbox[3]);
458             dataX.push(this.bbox[2]); dataY.push(this.bbox[3]);
459             dataX.push(this.bbox[2]); dataY.push(this.bbox[1]);
460             dataX.push(this.bbox[0]); dataY.push(this.bbox[1]);
461             dataX.push(this.bbox[0]); dataY.push(this.bbox[3]);
462             dataX.push(NaN); dataY.push(NaN);
463 
464             if (this.northWest !== null) {
465                 ret = this.northWest.plot();
466                 dataX = dataX.concat(ret[0]);
467                 dataY = dataY.concat(ret[1]);
468             }
469 
470             if (this.northEast !== null) {
471                 ret = this.northEast.plot();
472                 dataX = dataX.concat(ret[0]);
473                 dataY = dataY.concat(ret[1]);
474             }
475 
476             if (this.southEast !== null) {
477                 ret = this.southEast.plot();
478                 dataX = dataX.concat(ret[0]);
479                 dataY = dataY.concat(ret[1]);
480             }
481 
482             if (this.southWest !== null) {
483                 ret = this.southWest.plot();
484                 dataX = dataX.concat(ret[0]);
485                 dataY = dataY.concat(ret[1]);
486             }
487 
488             return [dataX, dataY];
489         }
490     }
491 );
492 
493 export default Mat.BoxQuadtree;
494