d3碰撞源码分析

技术

d3、 d3.force、d3.geom.quadtree。

d3.geom.quadtree

四叉树的应用：图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等，游戏编程。

上图中的数据就是普通的点，点与点之间没有关系。此函数在构建四叉树的时候（原数据要么是树型的数据要么是包含位置信息的点，此例子是包含位置信息的普通的点），整个rect是一个根节点，当这个节点内部的有大于一个数据点的时候，会对这个节点进行四等分，持续下去直到每个叶子节点至多包含一个数据点。引用： https://www.sypopo.com/post/dJQbeP8Zoj/

四叉树碰撞应用（圆）

d3官方example:

 1 <!DOCTYPE html>
 2 <meta charset="utf-8">
 3 <body>
 4 <script src="//d3js.org/d3.v3.min.js"></script>
 5 <script>
 6 
 7     var width = 960,
 8         height = 500;
 9 
10     var nodes = d3.range(200).map(function() { return {radius: Math.random() * 12 + 4}; }),
11         root = nodes[0],
12         color = d3.scale.category10();
13 
14     root.radius = 0;
15     root.fixed = true;
16 
17     var force = d3.layout.force()
18         .gravity(0.05)
19         .charge(function(d, i) { return i ? 0 : -2000; })
20         .nodes(nodes)
21         .size([width, height]);
22 
23     force.start();
24 
25     var svg = d3.select("body").append("svg")
26         .attr("width", width)
27         .attr("height", height);
28 
29     svg.selectAll("circle")
30         .data(nodes.slice(1))
31         .enter().append("circle")
32         .attr("r", function(d) { return d.radius; })
33         .style("fill", function(d, i) { return color(i % 3); });
34 
35     force.on("tick", function(e) {
36         var q = d3.geom.quadtree(nodes),
37             i = 0,
38             n = nodes.length;
39 
40         while (++i < n) q.visit(collide(nodes[i]));  //n^2的复杂度
41 
42         svg.selectAll("circle")
43             .attr("cx", function(d) { return d.x; })
44             .attr("cy", function(d) { return d.y; });
45     });
46 
47     svg.on("mousemove", function() {
48         var p1 = d3.mouse(this);
49         root.px = p1[0];
50         root.py = p1[1];
51         force.resume();
52     });
53 
54     function collide(node) {
55         var r = node.radius + 16,
56             nx1 = node.x - r,
57             nx2 = node.x + r,
58             ny1 = node.y - r,
59             ny2 = node.y + r;
60         return function(quad, x1, y1, x2, y2) {
61             if (quad.point && (quad.point !== node)) {//是叶子节点且不是当前节点
62                 var x = node.x - quad.point.x,
63                     y = node.y - quad.point.y,
64                     l = Math.sqrt(x * x + y * y),
65                     r = node.radius + quad.point.radius;
66                 if (l < r) {
67                     l = (l - r) / l * .5;
68                     node.x -= x *= l;
69                     node.y -= y *= l;
70                     quad.point.x += x;
71                     quad.point.y += y;
72                 }
73             }
74             return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1;
75         };
76     }
77 
78 </script>

核心代码在： L60-L71行。解释如下：

另平移因子S=(r-l)/(2l) ;利用勾股证明得：

因此，程序中偏移实际上是偏大了一点！不过绘制的结果还是挺好的。

经试验，对L36-L44行进行单独迭代，把上述代码中的力去掉。迭代大约30次左右，才能避免碰撞现象。其中迭代step,可以对L67行中的"l"进行适当缩放。注意避免震荡情况（l较大的时候）。

collide函数的分析

测试下面的函数：

 1 <script>
 2     function a(x){
 3         return x(1,2);
 4     }
 5     function b(x,y){
 6         console.log(x+":b:"+y);
 7     }
 8     function  c(x) {
 9         return function(a,b){
10             console.log(x+":"+a+":c:"+b);
11         }
12     }
13 
14 </script>

结果：

可见，b 、c两种写法都是ok的，c更骚一点。

quadtree().visit()

前序遍历，关于回调函数返回值：

If the callback returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited.

返回值： return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1;

意思就是内部的node超出了quad的话，对当前quad的子节点标记为未访问（需要继续对其子节点进行调整）。