如何计算两节点间折线路径？求D3.js实现方案及开源算法

一、开源路径计算算法推荐 #

• 曼哈顿路由算法（Manhattan Routing）：这是处理轴对齐直折线的核心方案，通过横向+纵向的拐点连接两个节点的边界点，天然适配绕开重叠节点的场景，你可以基于此逻辑自定义实现路径判断。
• Eclipse Layout Kernel（ELK）：专门针对图布局与边路由的开源库，支持自动计算绕开节点的折线路径，内置多种路由策略（如Manhattan、Orthogonal），可直接集成获取路径坐标。
• Graphviz边路由模块：Graphviz的dot或neato工具支持配置轴对齐折线边，通过edge[style=ortho]参数生成符合要求的路径，可调用其API获取数据后转换为SVG的path字符串。

二、D3.js中的实现方案 #

D3.js本身没有内置复杂节点绕开路由，但可以通过自定义逻辑结合交互能力实现需求：

1. 基础直折线计算 #

针对非重叠、位置明确的节点，直接计算边界点生成折线：

function getBasicPath(sourceEl, targetEl) {
  const sourceBBox = sourceEl.getBBox();
  const targetBBox = targetEl.getBBox();
  // 源节点右侧中点（输出点）
  const sx = sourceBBox.x + sourceBBox.width;
  const sy = sourceBBox.y + sourceBBox.height / 2;
  // 目标节点左侧中点（输入点）
  const tx = targetBBox.x;
  const ty = targetBBox.y + targetBBox.height / 2;
  
  // 近似水平时直接直线连接，否则添加垂直拐点
  return Math.abs(sy - ty) < 5 
    ? `M ${sx} ${sy} L ${tx} ${ty}` 
    : `M ${sx} ${sy} L ${tx} ${sy} L ${tx} ${ty}`;
}

2. 重叠/紧邻节点的绕开处理 #

当节点重叠或侧边无空间时，添加额外拐点绕开节点：

function getAvoidPath(sourceEl, targetEl) {
  const sourceBBox = sourceEl.getBBox();
  const targetBBox = targetEl.getBBox();
  const sx = sourceBBox.x + sourceBBox.width;
  const sy = sourceBBox.y + sourceBBox.height / 2;
  const tx = targetBBox.x;
  const ty = targetBBox.y + targetBBox.height / 2;
  
  // 判断节点是否重叠
  const isOverlap = (sourceBBox.x < targetBBox.x + targetBBox.width) &&
                    (sourceBBox.x + sourceBBox.width > targetBBox.x) &&
                    (sourceBBox.y < targetBBox.y + targetBBox.height) &&
                    (sourceBBox.y + sourceBBox.height > targetBBox.y);
  
  if (!isOverlap) return getBasicPath(sourceEl, targetEl);
  
  // 绕开策略：向下偏移节点底部20px，生成三折线
  const offsetY = Math.max(sourceBBox.y + sourceBBox.height, targetBBox.y + targetBBox.height) + 20;
  return `M ${sx} ${sy} L ${sx} ${offsetY} L ${tx} ${offsetY} L ${tx} ${ty}`;
}

3. Tangled Tree的适用说明 #

Tangled Tree是D3针对层级树状结构的连线组件，仅适合层级化节点连接，无法处理任意节点间的自由连接需求，不建议用于你的场景。

三、拖拽时动态更新线条 #

在D3的拖拽事件中，实时重新计算路径并更新SVG的path元素：

// 初始化拖拽行为
const drag = d3.drag()
  .on("drag", (event, d) => {
    // 更新节点位置
    d3.select(event.target)
      .attr("x", d.x = event.x)
      .attr("y", d.y = event.y);
    // 更新所有关联的连接线
    updateAllConnections();
  });

// 绑定拖拽到节点
node.call(drag);

// 批量更新连接线
function updateAllConnections() {
  d3.selectAll(".connection-path").each(function(d) {
    const sourceEl = d3.select(d.source).node();
    const targetEl = d3.select(d.target).node();
    const pathStr = getAvoidPath(sourceEl, targetEl);
    d3.select(this).attr("d", pathStr);
  });
}

内容的提问来源于stack exchange，提问作者Jack Zhang