D3js 地图标记碰撞检测

Question

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

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

带有内联 D3js 的我的地图的 JSBin（JavaScript 选项卡仅包含一个 600kb 的 GeoJSON 数据集）：http://jsbin.com/tapuhefamu/1/edit?html,output

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

Answer 1

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

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

查看

有趣的部分是：

添加一个 radiusStep 参数 - 使用它来平衡迭代次数和节点之间的潜在重叠量之间的权衡。
```
radiusStep = 0.01,
```

从缩放处理程序中删除半径缩放：

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));
}),

创建一个新结构来跟踪一个节点是否与另一个节点发生碰撞，半径以及 x 和 y 位置（用你的投影预先计算）

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

两个新函数用于检测碰撞和扩展半径直到检测到碰撞。
```
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函数首先在每个节点上调用碰撞以确定它是否与任何其他节点发生碰撞。然后它将任何未碰撞的节点的半径增加 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 位置的差异，然后使用毕达哥拉斯计算它们之间的距离。如果该距离小于两个节点加在一起的半径，则会发生碰撞。
更新了 drawMap 函数以在绘制节点之前计算半径。
```
while (nodes.filter(function(n) { return n.collided; }).length < nodes.length) {
    tick();
}
```
这基本上只会调用 tick 函数，直到所有节点都被标记为碰撞。

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)。

D3js 地图标记碰撞检测

D3js map marker collision detection

javascript

svg

d3.js