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