```  1 /**
2  * Constructs a new collision constraint. The default search radius is 10, and
3  * the default repeat count is 1. A radius function must be specified to compute
4  * the radius of particles.
5  *
6  * @class Constraints circles to avoid overlap. Each particle is treated as a
7  * circle, with the radius of the particle computed using a specified function.
8  * For example, if the particle has an <tt>r</tt> attribute storing the radius,
9  * the radius <tt>function(d) d.r</tt> specifies a collision constraint using
11  * first argument.
12  *
13  * <p>To accelerate collision detection, this implementation uses a quadtree and
15  * particles in the simulation.
16  *
17  * @see pv.Constraint
19  */
21   var n = 1, // number of times to repeat the constraint
22       r1,
23       px1,
24       py1,
25       px2,
26       py2,
27       constraint = {};
28
29   if (!arguments.length) r1 = 10; // default search radius
30
31   /**
32    * Sets or gets the repeat count. If the repeat count is greater than 1, the
33    * constraint will be applied repeatedly; this is a form of the Gauss-Seidel
34    * method for constraints relaxation. Repeating the collision constraint makes
35    * the constraint have more of an effect when there is a potential for many
36    * co-occurring collisions.
37    *
38    * @function
39    * @name pv.Constraint.collision.prototype.repeat
40    * @param {number} x the number of times to repeat this constraint.
41    * @returns {pv.Constraint.collision} this.
42    */
43   constraint.repeat = function(x) {
44     if (arguments.length) {
45       n = Number(x);
46       return constraint;
47     }
48     return n;
49   };
50
51   /** @private */
52   function constrain(n, p, x1, y1, x2, y2) {
53     if (!n.leaf) {
54       var sx = (x1 + x2) * .5,
55           sy = (y1 + y2) * .5,
56           top = sy > py1,
57           bottom = sy < py2,
58           left = sx > px1,
59           right = sx < px2;
60       if (top) {
61         if (n.c1 && left) constrain(n.c1, p, x1, y1, sx, sy);
62         if (n.c2 && right) constrain(n.c2, p, sx, y1, x2, sy);
63       }
64       if (bottom) {
65         if (n.c3 && left) constrain(n.c3, p, x1, sy, sx, y2);
66         if (n.c4 && right) constrain(n.c4, p, sx, sy, x2, y2);
67       }
68     }
69     if (n.p && (n.p != p)) {
70       var dx = p.x - n.p.x,
71           dy = p.y - n.p.y,
72           l = Math.sqrt(dx * dx + dy * dy),
73           d = r1 + radius(n.p);
74       if (l < d) {
75         var k = (l - d) / l * .5;
76         dx *= k;
77         dy *= k;
78         p.x -= dx;
79         p.y -= dy;
80         n.p.x += dx;
81         n.p.y += dy;
82       }
83     }
84   }
85
86   /**
87    * Applies this constraint to the specified particles.
88    *
89    * @function
90    * @name pv.Constraint.collision.prototype.apply
91    * @param {pv.Particle} particles particles to which to apply this constraint.
93    */
94   constraint.apply = function(particles, q) {
95     var p, r, max = -Infinity;
96     for (p = particles; p; p = p.next) {
98       if (r > max) max = r;
99     }
100     for (var i = 0; i < n; i++) {
101       for (p = particles; p; p = p.next) {
102         r = (r1 = radius(p)) + max;
103         px1 = p.x - r;
104         px2 = p.x + r;
105         py1 = p.y - r;
106         py2 = p.y + r;
107         constrain(q.root, p, q.xMin, q.yMin, q.xMax, q.yMax);
108       }
109     }
110   };
111
112   return constraint;
113 };
114 ```