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