```  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  */
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. */
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  *
108  */
109
110 /**
111  * The minimum x-coordinate value of all contained particles.
112  *
113  * @type number
115  */
116
117 /**
118  * The maximum x-coordinate value of all contained particles.
119  *
120  * @type number
122  */
123
124 /**
125  * The minimum y-coordinate value of all contained particles.
126  *
127  * @type number
129  */
130
131 /**
132  * The maximum y-coordinate value of all contained particles.
133  *
134  * @type number
136  */
137
138 /**
139  * Constructs a new node.
140  *
141  * @class A node in a quadtree.
142  *
144  */
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
167  */
168
169 /**
170  * The particle associated with this node, if any.
171  *
172  * @type pv.Particle
174  */
175
176 /**
177  * The child node for the second quadrant, if any.
178  *
181  */
182
183 /**
184  * The child node for the third quadrant, if any.
185  *