javascript - D3js map 标记碰撞检测

Question

是否有一个 float 碰撞检测示例，通过操纵半径而不是 x,y 坐标来避免碰撞？我知道 Mike Bostock 和其他人整理的示例，但我没有使用力图，而且我的点是地理的，无法操纵它们的坐标。

我的最佳猜测实现是从半径为 0 的圆开始，迭代它们并增加它们各自的半径，只要它们不与另一个圆碰撞。我认为这会产生一种奇妙的可视化效果，但我不确定如何有效地确定一个圆是否与另一个圆碰撞。

<小时/>

带有内联 D3js 的 map 的 JSBin(JavaScript 选项卡仅包含 600kb GeoJSON 数据集):http://jsbin.com/tapuhefamu/1/edit?html,output

请注意缩放时标记如何重叠，这在 fiddle 中似乎没什么大不了的(只需进一步放大，对吧？)但我正在使用的 map 有大约 2,000 个图钉聚集在几个县中单击时需要显示信息丰富的 DIV。有些引脚几乎完全被遮挡，并且由于重叠而无法进行交互。

Answer 1

我已经为你编写了一些代码。检测碰撞很容易，基本上计算两个中心点之间的距离，如果距离小于两个半径的总和，那么它们一定发生了碰撞。

我在 jsbin 方面遇到了一些问题，所以我把它变成了要点，你可以在http://bl.ocks.org/benlyall/6a81499abf7a0e2ad304查看。

有趣的部分是:

1. 添加 radiusStep 参数 - 使用此参数来平衡迭代次数与节点之间潜在重叠量之间的权衡。

   radiusStep = 0.01,
   

2. 从缩放处理程序中删除半径缩放:

   zoom = d3.behavior.zoom().on("zoom",function() {
           g.attr("transform","translate("+ d3.event.translate.join(",")+")scale("+d3.event.scale+")");
           //g.selectAll("circle")
           //.attr("r", nodeRadius / d3.event.scale);
           g.selectAll("path")
               .style('stroke-width', countyBorderWidth / d3.event.scale )
               .attr("d", path.projection(projection));
   }),
   

3. 创建一个新结构来跟踪节点是否与另一个节点发生碰撞、半径以及 x 和 y 位置(根据投影预先计算)

   nodes = nodeGeoData.map(function(n) {
       var pos = projection(n);
       return {
           collided: false,
           x: pos[0],
           y: pos[1],
           r: 0
       };
   });
   

4. 两个新函数用于检测碰撞并扩大半径直至检测到碰撞。

   function tick() {
       nodes.forEach(collided);
   
       nodes.forEach(function(n) {
           if (!n.collided) {
               n.r += radiusStep;
               if (n.r > nodeRadius) {
                   n.r = nodeRadius;
                   n.collided = true;
               }
           }
       });
   }
   

   这个tick函数首先在每个节点上调用collide来确定它是否与任何其他节点发生碰撞。然后，它会将任何未发生碰撞的节点的半径增加 radiusStep。如果半径变得大于 nodeRadius 参数，则它将半径设置为该值并将其标记为碰撞以阻止其增加。

   function collided(node, i) {
       if (node.collided) return;
   
       nodes.forEach(function(n, j) {
           if (n !== node) {
               var dx = node.x - n.x, dy = node.y - n.y,
                   l = Math.sqrt(dx*dx+dy*dy);
   
               if (l < node.r + n.r) {
                   node.collided = true;
                   n.collided = true;
               }
           }
       });
   }
   

   碰撞函数检查每个节点是否与任何其他节点发生碰撞(出于明显的原因，除了自身之外)。如果它检测到碰撞，则比较中的两个节点都被标记为碰撞。为了检测实际碰撞，计算 x 和 y 位置的差异，然后使用毕达哥拉斯计算它们之间的距离。如果该距离小于两个节点的半径之和，则会发生碰撞。

5. drawMap 函数已更新，可在绘制节点之前计算半径。

   while (nodes.filter(function(n) { return n.collided; }).length < nodes.length) {
       tick();
   }
   

   这基本上只会调用 tick 函数，直到所有节点都被标记为碰撞。

6. drawNodes 函数已更新为使用新的 nodes 数据结构:

   function drawNodes(nodes) {
       g.selectAll('circle').data(nodes).enter().append("circle")
           .attr("cx", function (d) { return d.x; })
           .attr("cy", function (d) { return d.y; })
           .attr("r", function(d, i) { return d.r; })
           .attr("class", "map-marker");
   }
   

   此处的更改仅引用之前创建的每个节点对象的 x、y 和 r 属性。

虽然这可行，而且看起来相当有效，但它很幼稚，很快就会陷入困境，因为 tick 和 collided 函数的组合是 O(n^2)。