Advertisement
lucasgautheron

quad tree generation

Jul 13th, 2012
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Constructs a new quadtree for the specified array of particles.
  3.  *
  4.  * @class Represents a quadtree: a two-dimensional recursive spatial
  5.  * subdivision. This particular implementation uses square partitions, dividing
  6.  * each square into four equally-sized squares. Each particle exists in a unique
  7.  * node; if multiple particles are in the same position, some particles may be
  8.  * stored on internal nodes rather than leaf nodes.
  9.  *
  10.  * <p>This quadtree can be used to accelerate various spatial operations, such
  11.  * as the Barnes-Hut approximation for computing n-body forces, or collision
  12.  * detection.
  13.  *
  14.  * @see pv.Force.charge
  15.  * @see pv.Constraint.collision
  16.  * @param {pv.Particle} particles the linked list of particles.
  17.  */
  18. pv.Quadtree = function(particles) {
  19.   var p;
  20.  
  21.   /* Compute bounds. */
  22.   var x1 = Number.POSITIVE_INFINITY, y1 = x1,
  23.       x2 = Number.NEGATIVE_INFINITY, y2 = x2;
  24.   for (p = particles; p; p = p.next) {
  25.     if (p.x < x1) x1 = p.x;
  26.     if (p.y < y1) y1 = p.y;
  27.     if (p.x > x2) x2 = p.x;
  28.     if (p.y > y2) y2 = p.y;
  29.   }
  30.  
  31.   /* Squarify the bounds. */
  32.   var dx = x2 - x1, dy = y2 - y1;
  33.   if (dx > dy) y2 = y1 + dx;
  34.   else x2 = x1 + dy;
  35.   this.xMin = x1;
  36.   this.yMin = y1;
  37.   this.xMax = x2;
  38.   this.yMax = y2;
  39.  
  40.   /**
  41.    * @ignore Recursively inserts the specified particle <i>p</i> at the node
  42.    * <i>n</i> or one of its descendants. The bounds are defined by [<i>x1</i>,
  43.    * <i>x2</i>] and [<i>y1</i>, <i>y2</i>].
  44.    */
  45.   function insert(n, p, x1, y1, x2, y2) {
  46.     if (isNaN(p.x) || isNaN(p.y)) return; // ignore invalid particles
  47.     if (n.leaf) {
  48.       if (n.p) {
  49.         /*
  50.          * If the particle at this leaf node is at the same position as the new
  51.          * particle we are adding, we leave the particle associated with the
  52.          * internal node while adding the new particle to a child node. This
  53.          * avoids infinite recursion.
  54.          */
  55.         if ((Math.abs(n.p.x - p.x) + Math.abs(n.p.y - p.y)) < .01) {
  56.           insertChild(n, p, x1, y1, x2, y2);
  57.         } else {
  58.           var v = n.p;
  59.           n.p = null;
  60.           insertChild(n, v, x1, y1, x2, y2);
  61.           insertChild(n, p, x1, y1, x2, y2);
  62.         }
  63.       } else {
  64.         n.p = p;
  65.       }
  66.     } else {
  67.       insertChild(n, p, x1, y1, x2, y2);
  68.     }
  69.   }
  70.  
  71.   /**
  72.    * @ignore Recursively inserts the specified particle <i>p</i> into a
  73.    * descendant of node <i>n</i>. The bounds are defined by [<i>x1</i>,
  74.    * <i>x2</i>] and [<i>y1</i>, <i>y2</i>].
  75.    */
  76.   function insertChild(n, p, x1, y1, x2, y2) {
  77.     /* Compute the split point, and the quadrant in which to insert p. */
  78.     var sx = (x1 + x2) * .5,
  79.         sy = (y1 + y2) * .5,
  80.         right = p.x >= sx,
  81.         bottom = p.y >= sy;
  82.  
  83.     /* Recursively insert into the child node. */
  84.     n.leaf = false;
  85.     switch ((bottom << 1) + right) {
  86.       case 0: n = n.c1 || (n.c1 = new pv.Quadtree.Node()); break;
  87.       case 1: n = n.c2 || (n.c2 = new pv.Quadtree.Node()); break;
  88.       case 2: n = n.c3 || (n.c3 = new pv.Quadtree.Node()); break;
  89.       case 3: n = n.c4 || (n.c4 = new pv.Quadtree.Node()); break;
  90.     }
  91.  
  92.     /* Update the bounds as we recurse. */
  93.     if (right) x1 = sx; else x2 = sx;
  94.     if (bottom) y1 = sy; else y2 = sy;
  95.     insert(n, p, x1, y1, x2, y2);
  96.   }
  97.  
  98.   /* Insert all particles. */
  99.   this.root = new pv.Quadtree.Node();
  100.   for (p = particles; p; p = p.next) insert(this.root, p, x1, y1, x2, y2);
  101. };
  102.  
  103. /**
  104.  * The root node of the quadtree.
  105.  *
  106.  * @type pv.Quadtree.Node
  107.  * @name pv.Quadtree.prototype.root
  108.  */
  109.  
  110. /**
  111.  * The minimum x-coordinate value of all contained particles.
  112.  *
  113.  * @type number
  114.  * @name pv.Quadtree.prototype.xMin
  115.  */
  116.  
  117. /**
  118.  * The maximum x-coordinate value of all contained particles.
  119.  *
  120.  * @type number
  121.  * @name pv.Quadtree.prototype.xMax
  122.  */
  123.  
  124. /**
  125.  * The minimum y-coordinate value of all contained particles.
  126.  *
  127.  * @type number
  128.  * @name pv.Quadtree.prototype.yMin
  129.  */
  130.  
  131. /**
  132.  * The maximum y-coordinate value of all contained particles.
  133.  *
  134.  * @type number
  135.  * @name pv.Quadtree.prototype.yMax
  136.  */
  137.  
  138. /**
  139.  * Constructs a new node.
  140.  *
  141.  * @class A node in a quadtree.
  142.  *
  143.  * @see pv.Quadtree
  144.  */
  145. pv.Quadtree.Node = function() {
  146.   /*
  147.    * Prepopulating all attributes significantly increases performance! Also,
  148.    * letting the language interpreter manage garbage collection was moderately
  149.    * faster than creating a cache pool.
  150.    */
  151.   this.leaf = true;
  152.   this.c1 = null;
  153.   this.c2 = null;
  154.   this.c3 = null;
  155.   this.c4 = null;
  156.   this.p = null;
  157. };
  158.  
  159. /**
  160.  * True if this node is a leaf node; i.e., it has no children. Note that both
  161.  * leaf nodes and non-leaf (internal) nodes may have associated particles. If
  162.  * this is a non-leaf node, then at least one of {@link #c1}, {@link #c2},
  163.  * {@link #c3} or {@link #c4} is guaranteed to be non-null.
  164.  *
  165.  * @type boolean
  166.  * @name pv.Quadtree.Node.prototype.leaf
  167.  */
  168.  
  169. /**
  170.  * The particle associated with this node, if any.
  171.  *
  172.  * @type pv.Particle
  173.  * @name pv.Quadtree.Node.prototype.p
  174.  */
  175.  
  176. /**
  177.  * The child node for the second quadrant, if any.
  178.  *
  179.  * @type pv.Quadtree.Node
  180.  * @name pv.Quadtree.Node.prototype.c2
  181.  */
  182.  
  183. /**
  184.  * The child node for the third quadrant, if any.
  185.  *
  186.  * @type pv.Quadtree.Node
  187.  * @name pv.Quadtree.Node.prototype.c3
  188.  */
  189.  
  190. /**
  191.  * The child node for the fourth quadrant, if any.
  192.  *
  193.  * @type pv.Quadtree.Node
  194.  * @name pv.Quadtree.Node.prototype.c4
  195.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement