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  */
196