display_Quadtree.js.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="utf-8">
    <title>JSDoc: Source: display/Quadtree.js</title>

    <script src="scripts/prettify/prettify.js"> </script>
    <script src="scripts/prettify/lang-css.js"> </script>
    <!--[if lt IE 9]>
      <script src="//html5shiv.googlecode.com/svn/trunk/html5.js"></script>
    <![endif]-->
    <link type="text/css" rel="stylesheet" href="styles/prettify-tomorrow.css">
    <link type="text/css" rel="stylesheet" href="styles/jsdoc-default.css">
</head>

<body>

<div id="main">

    <h1 class="page-title">Source: display/Quadtree.js</h1>

    
    <section>
        <article>
            <pre class="prettyprint source linenums"><code>//------------------------------------------------------------------------------
// Constructor scope
//------------------------------------------------------------------------------

/** 
 * Creates a new Quadtree object.
 * 
 * @constructor
 * @extends rune.geom.Rectangle
 * @see https://en.wikipedia.org/wiki/Quadtree
 *
 * @param {rune.geom.Rectangle} [bounds] Represents the rectangular size of the quad tree.
 * @param {number} [threshold=8] Threshold for subdivision, ie objects per node.
 * @param {number} [maxDepth=4] Maximum node depth.
 * @param {number} [depth=0] Standard depth.
 *
 * @class
 * @classdesc
 * 
 * The Quadtree class represents a tree data structure that divides objects 
 * within a rectangular two-dimensional surface into nodes of four. When a node 
 * has been populated with a number of objects that exceed a specified 
 * threshold value, the current node is divided into four new nodes and so on. 
 * The data structure makes it easy to find objects that are in the geometric 
 * proximity of another object.
 */
rune.display.Quadtree = function(bounds, threshold, maxDepth, depth) {

    //--------------------------------------------------------------------------
    // Default arguments
    //--------------------------------------------------------------------------

    /**
     * @ignore
     */
    bounds = bounds || new rune.geom.Rectangle();

    //--------------------------------------------------------------------------
    // Private properties
    //--------------------------------------------------------------------------

    /**
     * This object's nodes.
     *
     * @type {Array}
     * @private
     */
    this.m_nodes = [];

    /**
     * Objects that are part of this object's tree structure.
     *
     * @type {Array.&lt;rune.geom.Rectangle>}
     * @private
     */
    this.m_objects = [];

    /**
     * Threshold for subdivision, ie objects per node.
     *
     * @type {number}
     * @private
     */
    this.m_threshold = threshold || 8;

    /**
     * Maximum node depth.
     *
     * @type {number}
     * @private
     */
    this.m_maxDepth = maxDepth || 4;

    /**
     * Standard depth.
     *
     * @type {number}
     * @private
     */
    this.m_depth = depth || 0;
    
    //--------------------------------------------------------------------------
    // Super call
    //--------------------------------------------------------------------------
    
    /**
     * Extend rune.geom.Rectangle.
     */
    rune.geom.Rectangle.call(this, bounds.x, bounds.y, bounds.width, bounds.height);
};

//------------------------------------------------------------------------------
// Inheritance
//------------------------------------------------------------------------------

rune.display.Quadtree.prototype = Object.create(rune.geom.Rectangle.prototype);
rune.display.Quadtree.prototype.constructor = rune.display.Quadtree;

//------------------------------------------------------------------------------
// Private static constants
//------------------------------------------------------------------------------

/**
 * Refers to the upper left node.
 *
 * @const {number}
 * @private
 */
rune.display.Quadtree.TOP_LEFT = 0;

/**
 * Refers to the upper right node.
 *
 * @const {number}
 * @private
 */
rune.display.Quadtree.TOP_RIGHT = 1;

/**
 * Refers to the lower left node.
 *
 * @const {number}
 * @private
 */
rune.display.Quadtree.BOTTOM_LEFT = 2;

/**
 * Refers to the lower right node.
 *
 * @const {number}
 * @private
 */
rune.display.Quadtree.BOTTOM_RIGHT = 3;

//------------------------------------------------------------------------------
// Public prototype methods
//------------------------------------------------------------------------------

/**
 * Clears the current tree structure. This includes all nodes.
 *
 * @returns {undefined}
 */
rune.display.Quadtree.prototype.clear = function() {
    this.m_objects = [];
    for (var i = 0; i &lt; this.m_nodes.length; i++) {
        if (typeof this.m_nodes[i] !== "undefined") {
            this.m_nodes[i].clear();
        }
    }

    this.m_nodes = [];
};

/**
 * Returns within which node the passed Point object belongs to. Note that the 
 * method returns the node index and not the actual node.
 *
 * @param {rune.geom.Point} point Current point.
 *
 * @returns {number}
 */
rune.display.Quadtree.prototype.getIndexOfPoint = function(point) {
    var left = (point['x'] > this['centerX']) ? false : true;
    var top  = (point['y'] > this['centerY']) ? false : true;

    if (left) return (top) ? rune.display.Quadtree.TOP_LEFT  : rune.display.Quadtree.BOTTOM_LEFT;
    else      return (top) ? rune.display.Quadtree.TOP_RIGHT : rune.display.Quadtree.BOTTOM_RIGHT;
};

/**
 * Returns within which nodes a Rectangel object is located. The method returns 
 * a list of node indexes. Note that the same node index can only occur once. 
 * For example, if all the corners of the rectangle are within the same node 
 * index, the length of the list will be 1.
 *
 * @param {rune.geom.Rectangle} rectangle Current rectangle.
 *
 * @returns {Array.&lt;number>}
 */
rune.display.Quadtree.prototype.getIndexOfRectangle = function(rectangle) {
    var a = this.getIndexOfPoint(rectangle['topLeft']);
    var b = this.getIndexOfPoint(rectangle['topRight']);
    var c = this.getIndexOfPoint(rectangle['bottomLeft']);
    var d = this.getIndexOfPoint(rectangle['bottomRight']);
    var e = Array.prototype.concat(a, b, c, d);
    
    return e.filter(rune.util.Filter.unique);
};

/**
 * The object to be sorted according to the tree structure.
 *
 * @param {rune.geom.Rectangle} rectangle Object to sort.
 *
 * @returns {undefined}
 */
rune.display.Quadtree.prototype.insert = function(rectangle) {
    var corners;
    var c = 0; // corner index
    var l = 0; // corners length
    var o = 0; // object index

    if (typeof this.m_nodes[0] !== "undefined") {
        var divide = false;
        corners = this.getIndexOfRectangle(rectangle);
        for (c = 0, l = corners.length; c &lt; l; c++) {
            this.m_nodes[corners[c]].insert(rectangle);
            divide = true;
        }
        
        if (divide === true) return;
    }

    this.m_objects.push(rectangle);

    if (this.m_objects.length > this.m_threshold &amp;&amp; this.m_depth &lt; this.m_maxDepth) {
        if (typeof this.m_nodes[0] === "undefined") {
            this.split();
        }
        
        while (o &lt; this.m_objects.length) {
            var removeFromNode = false;
            var numProcessedCorners = 0;
            var currentObject = null;
            
            corners = this.getIndexOfRectangle(this.m_objects[o]);
            for (c = 0, l = corners.length; c &lt; l; c++) {
                currentObject = this.m_objects[o];
                this.m_nodes[corners[c]].insert(currentObject);
                removeFromNode = true;
                numProcessedCorners++;
            }
            
            if (removeFromNode === true &amp;&amp; numProcessedCorners === corners.length) this.m_objects.splice(o, 1);
            else o++;
        }
    }    
};

/**
 * Retrieves objects from the tree structure that are in the same node as the 
 * argument object.
 *
 * @param {rune.geom.Rectangle} rectangle Current object.
 *
 * @returns {Array.&lt;rune.geom.Rectangle>}
 */
rune.display.Quadtree.prototype.retrieve = function(rectangle) {
    if (rectangle == null || !this.intersects(rectangle)) {
        return [];
    }
    
    var corners = (rectangle.width != undefined &amp;&amp; rectangle.height != undefined) ? this.getIndexOfRectangle(rectangle) : [this.getIndexOfPoint(rectangle)];
    var objects = this.m_objects;

    if (typeof this.m_nodes[0] !== "undefined") {
        for (var i = 0, l = corners.length; i &lt; l; i++) {
            if (corners[i] !== -1) {
                objects = objects.concat(this.m_nodes[corners[i]].retrieve(rectangle));
            } 
        }
    }
    
    return objects.filter(rune.util.Filter.unique);
};

/**
 * Divides the tree into four new nodes.
 *
 * @returns {undefined}
 */
rune.display.Quadtree.prototype.split = function() {
    var depth = this.m_depth + 1;

    var bx = this.x;
    var by = this.y;

    var bwh = Math.round(this.width  >> 1);
    var bhh = Math.round(this.height >> 1);
    var bcw = bx + bwh; // border center width
    var bch = by + bhh; // border center height

    this.m_nodes[rune.display.Quadtree.TOP_LEFT] = new rune.display.Quadtree(
        new rune.geom.Rectangle(bx, by, bwh, bhh), this.m_threshold, this.m_maxDepth, depth
    );

    this.m_nodes[rune.display.Quadtree.TOP_RIGHT] = new rune.display.Quadtree(
        new rune.geom.Rectangle(bcw, by, bwh, bhh), this.m_threshold, this.m_maxDepth, depth
    );

    this.m_nodes[rune.display.Quadtree.BOTTOM_LEFT] = new rune.display.Quadtree(
        new rune.geom.Rectangle(bx, bch, bwh, bhh), this.m_threshold, this.m_maxDepth, depth
    );

    this.m_nodes[rune.display.Quadtree.BOTTOM_RIGHT] = new rune.display.Quadtree(
        new rune.geom.Rectangle(bcw, bch, bwh, bhh), this.m_threshold, this.m_maxDepth, depth
    );
};</code></pre>
        </article>
    </section>


</div>

<nav>
    <h2><a href="index.html">Home</a></h2><h3>Namespaces</h3><ul><li><a href="rune.html">rune</a></li><li><a href="rune.animation.html">animation</a></li><li><a href="rune.camera.html">camera</a></li><li><a href="rune.color.html">color</a></li><li><a href="rune.console.html">console</a></li><li><a href="rune.data.html">data</a></li><li><a href="rune.debug.html">debug</a></li><li><a href="rune.display.html">display</a></li><li><a href="rune.geom.html">geom</a></li><li><a href="rune.input.html">input</a></li><li><a href="rune.media.html">media</a></li><li><a href="rune.net.html">net</a></li><li><a href="rune.particle.html">particle</a></li><li><a href="rune.physics.html">physics</a></li><li><a href="rune.resource.html">resource</a></li><li><a href="rune.scene.html">scene</a></li><li><a href="rune.state.html">state</a></li><li><a href="rune.system.html">system</a></li><li><a href="rune.text.html">text</a></li><li><a href="rune.tilemap.html">tilemap</a></li><li><a href="rune.timer.html">timer</a></li><li><a href="rune.tween.html">tween</a></li><li><a href="rune.ui.html">ui</a></li><li><a href="rune.util.html">util</a></li></ul><h3>Classes</h3><ul><li><a href="rune.animation.Animation.html">Animation</a></li><li><a href="rune.animation.Animations.html">Animations</a></li><li><a href="rune.animation.AnimationScripts.html">AnimationScripts</a></li><li><a href="rune.camera.Camera.html">Camera</a></li><li><a href="rune.camera.CameraFade.html">CameraFade</a></li><li><a href="rune.camera.CameraFlash.html">CameraFlash</a></li><li><a href="rune.camera.Cameras.html">Cameras</a></li><li><a href="rune.camera.CameraShake.html">CameraShake</a></li><li><a href="rune.camera.CameraTargets.html">CameraTargets</a></li><li><a href="rune.camera.CameraTint.html">CameraTint</a></li><li><a href="rune.camera.CameraTintTween.html">CameraTintTween</a></li><li><a href="rune.camera.CameraViewport.html">CameraViewport</a></li><li><a href="rune.color.Color24.html">Color24</a></li><li><a href="rune.color.Color32.html">Color32</a></li><li><a href="rune.color.ColorComponent.html">ColorComponent</a></li><li><a href="rune.console.Console.html">Console</a></li><li><a href="rune.console.ConsoleCommand.html">ConsoleCommand</a></li><li><a href="rune.console.ConsoleCommands.html">ConsoleCommands</a></li><li><a href="rune.console.ConsoleCursor.html">ConsoleCursor</a></li><li><a href="rune.console.ConsoleHistory.html">ConsoleHistory</a></li><li><a href="rune.console.ConsoleInput.html">ConsoleInput</a></li><li><a href="rune.console.ConsoleManager.html">ConsoleManager</a></li><li><a href="rune.console.ConsoleOutput.html">ConsoleOutput</a></li><li><a href="rune.data.Highscores.html">Highscores</a></li><li><a href="rune.data.Loader.html">Loader</a></li><li><a href="rune.data.LoaderDebug.html">LoaderDebug</a></li><li><a href="rune.data.Logo.html">Logo</a></li><li><a href="rune.data.Requests.html">Requests</a></li><li><a href="rune.debug.Debugger.html">Debugger</a></li><li><a href="rune.debug.Framerate.html">Framerate</a></li><li><a href="rune.debug.Histogram.html">Histogram</a></li><li><a href="rune.debug.Master.html">Master</a></li><li><a href="rune.debug.Memory.html">Memory</a></li><li><a href="rune.debug.Music.html">Music</a></li><li><a href="rune.debug.Render.html">Render</a></li><li><a href="rune.debug.Sound.html">Sound</a></li><li><a href="rune.debug.Update.html">Update</a></li><li><a href="rune.display.Artboard.html">Artboard</a></li><li><a href="rune.display.Canvas.html">Canvas</a></li><li><a href="rune.display.DisplayGroup.html">DisplayGroup</a></li><li><a href="rune.display.DisplayGroups.html">DisplayGroups</a></li><li><a href="rune.display.DisplayObject.html">DisplayObject</a></li><li><a href="rune.display.DisplayObjectContainer.html">DisplayObjectContainer</a></li><li><a href="rune.display.Flicker.html">Flicker</a></li><li><a href="rune.display.Frame.html">Frame</a></li><li><a href="rune.display.Graphic.html">Graphic</a></li><li><a href="rune.display.Graphics.html">Graphics</a></li><li><a href="rune.display.Hitbox.html">Hitbox</a></li><li><a href="rune.display.InteractiveObject.html">InteractiveObject</a></li><li><a href="rune.display.Quadtree.html">Quadtree</a></li><li><a href="rune.display.RepeatedGraphic.html">RepeatedGraphic</a></li><li><a href="rune.display.Screen.html">Screen</a></li><li><a href="rune.display.Sprite.html">Sprite</a></li><li><a href="rune.display.Stage.html">Stage</a></li><li><a href="rune.display.Texture.html">Texture</a></li><li><a href="rune.geom.Point.html">Point</a></li><li><a href="rune.geom.Rectangle.html">Rectangle</a></li><li><a href="rune.geom.Vector2D.html">Vector2D</a></li><li><a href="rune.input.Gamepad.html">Gamepad</a></li><li><a href="rune.input.Gamepads.html">Gamepads</a></li><li><a href="rune.input.GamepadsOptions.html">GamepadsOptions</a></li><li><a href="rune.input.Inputs.html">Inputs</a></li><li><a href="rune.input.Keyboard.html">Keyboard</a></li><li><a href="rune.input.KeyboardKey.html">KeyboardKey</a></li><li><a href="rune.input.KeyboardOptions.html">KeyboardOptions</a></li><li><a href="rune.media.Sound.html">Sound</a></li><li><a href="rune.media.SoundChannel.html">SoundChannel</a></li><li><a href="rune.media.Sounds.html">Sounds</a></li><li><a href="rune.net.URLLoader.html">URLLoader</a></li><li><a href="rune.net.URLRequest.html">URLRequest</a></li><li><a href="rune.net.URLResponse.html">URLResponse</a></li><li><a href="rune.particle.Emitter.html">Emitter</a></li><li><a href="rune.particle.EmitterOptions.html">EmitterOptions</a></li><li><a href="rune.particle.Particle.html">Particle</a></li><li><a href="rune.physics.Space.html">Space</a></li><li><a href="rune.physics.Velocity.html">Velocity</a></li><li><a href="rune.resource.Request.html">Request</a></li><li><a href="rune.resource.Requester.html">Requester</a></li><li><a href="rune.resource.RequesterOptions.html">RequesterOptions</a></li><li><a href="rune.resource.Requests.html">Requests</a></li><li><a href="rune.resource.Resource.html">Resource</a></li><li><a href="rune.resource.Resources.html">Resources</a></li><li><a href="rune.scene.Scene.html">Scene</a></li><li><a href="rune.scene.Scenes.html">Scenes</a></li><li><a href="rune.state.State.html">State</a></li><li><a href="rune.state.States.html">States</a></li><li><a href="rune.system.Application.html">Application</a></li><li><a href="rune.system.Config.html">Config</a></li><li><a href="rune.system.Time.html">Time</a></li><li><a href="rune.text.BitmapField.html">BitmapField</a></li><li><a href="rune.text.BitmapFormat.html">BitmapFormat</a></li><li><a href="rune.tilemap.Block.html">Block</a></li><li><a href="rune.tilemap.Tile.html">Tile</a></li><li><a href="rune.tilemap.Tilemap.html">Tilemap</a></li><li><a href="rune.tilemap.TilemapLayer.html">TilemapLayer</a></li><li><a href="rune.timer.Timer.html">Timer</a></li><li><a href="rune.timer.TimerOptions.html">TimerOptions</a></li><li><a href="rune.timer.Timers.html">Timers</a></li><li><a href="rune.tween.Circular.html">Circular</a></li><li><a href="rune.tween.Cubic.html">Cubic</a></li><li><a href="rune.tween.Expo.html">Expo</a></li><li><a href="rune.tween.Linear.html">Linear</a></li><li><a href="rune.tween.Quad.html">Quad</a></li><li><a href="rune.tween.Quart.html">Quart</a></li><li><a href="rune.tween.Quint.html">Quint</a></li><li><a href="rune.tween.Sine.html">Sine</a></li><li><a href="rune.tween.Tween.html">Tween</a></li><li><a href="rune.tween.Tweens.html">Tweens</a></li><li><a href="rune.tween.TweenValue.html">TweenValue</a></li><li><a href="rune.ui.Counter.html">Counter</a></li><li><a href="rune.ui.CounterDigit.html">CounterDigit</a></li><li><a href="rune.ui.Progressbar.html">Progressbar</a></li><li><a href="rune.ui.VTList.html">VTList</a></li><li><a href="rune.ui.VTListElement.html">VTListElement</a></li><li><a href="rune.ui.VTMenu.html">VTMenu</a></li><li><a href="rune.ui.VTMenuPointer.html">VTMenuPointer</a></li><li><a href="rune.util.Executable.html">Executable</a></li><li><a href="rune.util.Filter.html">Filter</a></li><li><a href="rune.util.Math.html">Math</a></li><li><a href="rune.util.Palette.html">Palette</a></li><li><a href="rune.util.Path.html">Path</a></li><li><a href="rune.util.Paths.html">Paths</a></li><li><a href="rune.util.Stack.html">Stack</a></li><li><a href="rune.util.URL.html">URL</a></li></ul>
</nav>

<br class="clear">

<footer>
    Documentation generated by <a href="https://github.com/jsdoc/jsdoc">JSDoc 3.6.11</a> on Tue Apr 01 2025 09:55:09 GMT+0200 (Central European Summer Time)
</footer>

<script> prettyPrint(); </script>
<script src="scripts/linenumber.js"> </script>
</body>
</html>