如何为树/森林中每个ID节点设置(x,y)坐标实现Canvas分层布局

问题描述 #

在Canvas上按层级展开排布树节点、计算每个ID对应节点坐标时遇到以下问题：

• 待排布结构为无环的单棵树或多棵树（即森林），不存在环路，每个节点的展示框尺寸要求为240×100
• 基于获取到的连接关系数组 connectionsArr 开发布局逻辑，在graphWithTopLeft函数中实现每个ID的坐标计算，但当前运行效果存在部分节点互相重叠、节点间距不符合预期的问题
• 期望最终所有场景下都能实现规整分层树布局效果，要求不使用任何外部第三方库

在线示例与完整代码 #

• 在线Codesandbox示例：empty-dew-ry5tly
• 参考布局效果：

完整JS实现代码：

const connectionsArr = [
  { sourceId: 1, targetId: 2 },
  { sourceId: 1, targetId: 3 },
  { sourceId: 1, targetId: 4 },
  { sourceId: 2, targetId: 5 },
  { sourceId: 2, targetId: 6 },
  { sourceId: 2, targetId: 7 },
  { sourceId: 2, targetId: 8 },
  { sourceId: 3, targetId: 10 },
  { sourceId: 3, targetId: 9 },
  { sourceId: 4, targetId: 11 },
  { sourceId: 4, targetId: 12 },
  { sourceId: 11, targetId: 12 },
  { sourceId: 13, targetId: 12 }
];
const WIDTH = 200;

// 查找根节点ID
function findParents(connections) {
  const parents = [];
  const notParents = [];
  connections.forEach((con1) => {
    const t = connections.filter((cf) => cf.targetId === con1.sourceId);
    t.forEach((t2) => notParents.push(t2.targetId));
  });
  const allIds = connections.map((con) => con.sourceId);
  const arrayWithDuplicate = allIds.filter((val) => !notParents.includes(val));
  arrayWithDuplicate.forEach((a, index) => {
    if (!parents.find((p) => a === p)) {
      parents.push(a);
    }
  });
  return parents;
}
// 转换为树结构对象数组
function getTrees(flatList) {
  const graph = [];
  flatList.forEach((item) => {
    if (!graph[item.sourceId]) {
      graph[item.sourceId] = { id: item.sourceId, children: [] };
    }
    if (!graph[item.targetId]) {
      graph[item.targetId] = { id: item.targetId, children: [] };
    }
    graph[item.sourceId].children.push(graph[item.targetId]);
  });
  return graph;
}
// 获取指定ID节点下所有后代节点ID
function getAllIds(connections, id) {
  const result = [];
  connections.forEach((connection) => {
    if (connection.sourceId === id) {
      result.push(connection.targetId);
      result.push(...getAllIds(connections, connection.targetId));
    }
  });
  return result;
}
// 为树节点标记层级
function updateLevels(trees, level) {
  for (let i = 0; i < trees.length; i++) {
    if (trees[i].children && trees[i].children.length) {
      updateLevels(trees[i].children, level + 1)
    }
    trees[i].level = level;
  }
  return trees;
}
// 获取树中单节点最大子节点数量
function getMaxChildren(tree) {
  let max = 0;
  let id = 1;
  const getMax = (node) => {
    if (node.children) {
      if (node.children.length > max) {
        max = node.children.length;
        id = node.id;
      }
      node.children.forEach((child) => { getMax(child); });
    }
  };
  getMax(tree);
  return { max, id };
}
const parents = findParents(connectionsArr);
const filterArray = getTrees(connectionsArr).filter(
  (f, index) => f.id === parents[0] || f.id === parents[1] || f.id === parents[2]
);
const updated = updateLevels(filterArray, 0);
// 获取树深度
function getDepth(jsonTree) {
  let depth = 0;
  const recurse = (obj, currentDepth) => {
    if (obj.children) {
      depth = Math.max(depth, currentDepth);
      obj.children.forEach((child) => recurse(child, currentDepth + 1));
    }
  };
  recurse(jsonTree, 0);
  return depth;
}
function graphWithTopLeft(trees, newPositionNodes= [], index = 0, depth = 0, parent = 0) {
  const findLevel = trees.filter((lev) => lev.level === index).sort((a, b) =>
    getAllIds(connectionsArr, a.id).length < getAllIds(connectionsArr, b.id).length ? 1 : -1
  );
  findLevel.forEach((node, indexLevel) => {
    if (node.level === 0) {
      const y = 0;
      const x = indexLevel === 0 ? 0 : indexLevel * getAllIds(connectionsArr, findLevel[indexLevel].id).length * findLevel.length * 200;
      newPositionNodes.push({ id: node.id, name: `Node${node.id}`, left: x, top: y, isDragging: false });
    }
    if (node.level === 1) {
      const getMaxChildInLevel = getMaxChildren(node);
      const findParent = newPositionNodes.find((f) => f.id === parent);
      const axisX = Math.pow(findLevel.length, depth - 1) * getMaxChildInLevel.max;
      const y = node.level * WIDTH;
      const x = indexLevel === 0 ? -(axisX / 3) - (indexLevel * WIDTH + WIDTH) : axisX / 3 + indexLevel <= 1 ? (findParent?.left ) + indexLevel * WIDTH * (node.children.length > 0 ? node.children.length : 1) : (newPositionNodes[indexLevel - 1]?.left) + indexLevel * WIDTH * node.children.length;
      if (axisX === 0 && indexLevel === 0) {
        if (!newPositionNodes.find((n) => n.id === node.id)) {
          const findParent = newPositionNodes.find((f) => f.id === parent);
          newPositionNodes.push({ id: node.id, name: `Node${node.id}`, left: findParent?.left , top: y, isDragging: false });
        }
      } else if (!newPositionNodes.find((n) => n.id === node.id)) {
        newPositionNodes.push({ id: node.id, name: `Node${node.id}`, left: x, top: y, isDragging: false });
      }
    } else {
      if (!newPositionNodes.find((n) => n.id === node.id)) {
        const findParent = newPositionNodes.find((f) => f.id === parent);
        const y = (node.level ) * WIDTH;
        const x = indexLevel === 0 ? (findParent?.left) - WIDTH : indexLevel <= 1 ? (findParent?.left) + indexLevel * WIDTH * (node.children.length > 0 ? node.children.length : 1) : (newPositionNodes[indexLevel - 1]?.left) + indexLevel * WIDTH * node.children.length;
        if (findLevel.length <= 1) {
          newPositionNodes.push({ id: node.id, name: `Node${node.id}`, left: findParent?.left, top: y, isDragging: false });
        } else {
          newPositionNodes.push({ id: node.id, name: `Node${node.id}`, left: x, top: y, isDragging: false });
        }
      }
    }
  });
  for (let i = 0; i < trees.length; i++) {
    const depth = getDepth(trees[i]);
    if (trees[i].children && trees[i].children?.length > 0) {
      graphWithTopLeft(trees[i].children, newPositionNodes, index + 1, depth, trees[i].id);
    }
  }
  return newPositionNodes;
}
const display = graphWithTopLeft(updated, [], 0);
console.log(display);
const canvas = document.querySelector("#paper");
const WIDTHcA = canvas.width;
const HEIGHTCA = canvas.height;
let dragok = false;
let startX;
let startY;
const ctx = canvas.getContext("2d");
function clear() { ctx.clearRect(0, 0, WIDTHcA, HEIGHTCA); }
function drawLine(ctx, begin, end, stroke = "black", width = 1) {
  if (stroke) { ctx.strokeStyle = stroke; }
  if (width) { ctx.lineWidth = width; }
  ctx.beginPath();
  ctx.moveTo(begin[0] + 100, begin[1] + 100);
  ctx.lineTo(end[0] + 100, end[1]);
  ctx.stroke();
}
const draw = (t) => {
  clear();
  ctx.translate(600, 100);
  ctx.stroke();
  for (let i = 0; i < display.length; i++) {
    const x = display[i].left;
    const y = display[i].top;
    ctx.fillStyle = "red";
    ctx.fillRect(x, y, 200, 100);
    ctx.fillStyle = "white";
    ctx.font = "24px Arial";
    ctx.fillText(display[i].name, display[i].left, display[i].top);
  }
  for (let i = 0; i < connectionsArr.length; i++) {
    const sourcePaths = connectionsArr.filter((f) => f.sourceId === connectionsArr[i].sourceId);
    const from = display.find((f) => f.id === connectionsArr[i].sourceId);
    sourcePaths.forEach((s) => {
      const to = display.find((f) => f.id === s.targetId);
      if (to && from) drawLine(ctx, [from?.left, from?.top], [to.left, to.top], "green", 1);
    });
  }
};
requestAnimationFrame(draw);

配套HTML代码：

<html>
  <head>
    <title>Sandbox</title>
    <meta charset="UTF-8" />
    <style>
      body { background: black; margin: 0; }
    </style>
  </head>
  <body>
    <canvas id="paper" width="10000" height="10000"></canvas>
    <script src="src/index.ts"></script>
  </body>
</html>

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