      1 /*
      2     Copyright 2008-2013
      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