在D3力导向图中高效计算凸包

Question

在D3力导向图中高效计算凸包

javascriptperformanced3.jsforce-layoutconvex-hull

3

我有一个类似于力导向图的例子。主要的区别在于没有力量，除了用户拖拽交互之外，布局是静态的。我添加了绘制凸包（作为svg:path元素）围绕用户定义的节点组的代码。当节点移动时（即.on("drag")），计算凸包的代码就会被触发。这意味着当节点被拖动时，它会不断地触发。通常会有10到30个凸包；一个节点可能在一个或多个凸包中。请见下面的内容：

Example of hull graph

我试图弄清楚是否有更有效率（更高性能）的方法来完成我正在做的事情。现在先保持高层次：

在拖动时，更新所有凸包图形：

对于每个凸包，创建一个由组成节点坐标的数组。
用距离原始点一定距离r的8个点替换上述数组中的每个坐标对。这是为了填充/膨胀凸包，使其实际上不接触任何节点。
将计算出的坐标提供给d3.geom.hull。

在Chrome中，我得到了约50 fps，这并不算太差，但它似乎是一种可怕的低效设置。

我的唯一明确想法是在节点数组中存储凸包所包含的节点的ID，并仅更新该/那些凸包，而不是所有凸包。我还在思考更有效的数据结构来存储凸包数据（而不是路径本身）。目前，数据结构看起来像这样：

hulls = {1:{nodeIDs:[1,2,3,4,5], name:"hull1"}, 2:{...}, ...};

抱歉这个问题有点开放性，但是我希望能找到一些编程技术，使得这里的工作更有效率。

- ZachB

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cheeken · Accepted Answer

最高效的方法是仅重新计算拖动节点周围8元组坐标的位置，然后将该信息传播到父包络中以进行重绘。

您可以通过进行一些更改来实现这一点。

向每个节点的数据结构添加以下元素。
- 所有父包络的引用（如您所建议）
- “填充”该节点轨道的8元组坐标（将其缓存）
在拖动时，仅考虑被拖动的节点。
更新该节点的8元组。
收集该节点的父包络的子节点并将它们的8元组合并在一起，然后将它们提供给hull（必要时销毁先前的包络）。

我不熟悉d3.js的API，但我相信您可以填补我留下的任何空白。