实现谱系图的算法优化：解决布局重叠与性能问题

我从数据库获取了如下用户对象数组：

const users = [
  { id: 2, name: "Bob", fatherId: 4, motherId: 5, spouseId: 3, children:[] },
  { id: 3, name: "Mary", fatherId: 6, motherId: 7, spouseId: 2, children:[] },
  { id: 4, name: "Tom", fatherId: null, motherId: null, spouseId: 5, children:[{id:2}] },
  { id: 5, name: "Sue", fatherId: null, motherId: null, spouseId: 4, children:[{id:2}] },
  { id: 6, name: "Jim", fatherId: null, motherId: null, spouseId: 7, children:[{id:3}] },
  { id: 7, name: "Jill", fatherId: null, motherId: null, spouseId: 6, children:[{id:3}] },
];

我尝试遍历这些对象绘制包含父母、配偶及子女的谱系图，但随着对象数量（层级）增加，坐标计算性能下降，且出现元素重叠问题。请问是否存在可整洁绘制该图表的算法？我希望实现能在添加父母、兄弟姐妹、子女时自动调整元素的X、Y坐标的效果。

针对谱系图的自动布局问题，有几种成熟的算法可以解决你的痛点，核心是通过分层布局+冲突调整来避免重叠并保证性能：

1. 分层拓扑布局（家族树专用） #

核心步骤： #

• 层级划分：按代际确定Y轴层级，祖先放在上方，子代依次向下排列。通过递归遍历父/母节点，标记每个节点的代际深度，以此作为Y坐标的基础值。
• X坐标分配：
  • 初始分配：以父节点为中心，子女均匀分布在下方；配偶节点放在同一Y层级的相邻位置（比如主节点右侧）。
  • 冲突检测与调整：遍历每个层级，若发现节点重叠，向左右偏移，同时同步调整其子代的X坐标，保持父子连线垂直对齐。
• 性能优化：用哈希表存储已计算坐标的节点，避免重复计算；大规模数据采用分块计算+局部调整，无需一次性遍历所有节点。

2. Sugiyama框架（经典层次图算法） #

这是适配家族树这类有向无环图（DAG）的标准层次化布局算法：

• 步骤1：层级分配：通过拓扑排序确定每个节点的层级，确保所有边从高层指向低层。
• 步骤2：节点排序：在每个层级内调整节点顺序，减少边的交叉（家族树中可按兄弟姐妹长幼排序，避免配偶与子女的连线交叉）。
• 步骤3：坐标优化：用重心法调整X坐标，让每个节点尽量靠近其子节点的重心，同时加入间距约束防止重叠。

3. 家族树特殊优化规则 #

• 配偶单元处理：将配偶视为同一单元，共享Y层级，X坐标相邻，子女节点的X坐标以该单元的中心为基准排列。
• 兄弟姐妹组布局：同一父母的子女作为一组，统一分配X区间，组内均匀分布，组间保留足够间距。
• 动态更新优化：新增节点时，仅重新计算该节点所在分支及相邻层级的坐标，无需全局重算——比如新增Bob的兄弟姐妹，只需调整Bob所在层级的X位置，以及其父代Tom/Sue的子节点布局，其他节点保持不变。

代码实现思路示例 #

// 构建节点映射表，快速查找节点
const nodeMap = new Map(users.map(u => [u.id, {...u, y: 0, x: 0}]))

// 计算每个节点的代际Y坐标
function setYLevels(nodeId, currentLevel) {
  const node = nodeMap.get(nodeId)
  if (!node || node.y !== 0) return
  node.y = currentLevel
  // 向上处理父母层级
  if (node.fatherId) setYLevels(node.fatherId, currentLevel - 1)
  if (node.motherId) setYLevels(node.motherId, currentLevel - 1)
  // 向下处理子女层级
  node.children.forEach(child => setYLevels(child.id, currentLevel + 1))
  // 配偶同层级
  if (node.spouseId) {
    const spouse = nodeMap.get(node.spouseId)
    spouse.y = currentLevel
  }
}

// 从目标节点（如Bob）开始计算层级
setYLevels(2, 2)

// 分配X坐标并处理重叠
function adjustXPositions() {
  // 按Y层级分组
  const levelGroups = {}
  nodeMap.forEach(node => {
    if (!levelGroups[node.y]) levelGroups[node.y] = []
    levelGroups[node.y].push(node)
  })

  // 遍历每个层级调整X
  Object.values(levelGroups).forEach(nodes => {
    // 按关联关系排序：配偶、兄弟姐妹相邻
    nodes.sort((a, b) => {
      if (a.spouseId === b.id) return -1
      if (b.spouseId === a.id) return 1
      const aParent = a.fatherId || a.motherId
      const bParent = b.fatherId || b.motherId
      return (aParent || 0) - (bParent || 0)
    })

    // 初始分配X，预留间距
    let currentX = 0
    const nodeWidth = 100 // 自定义节点宽度
    const spacing = 50 // 自定义节点间距

    nodes.forEach(node => {
      // 配偶共用中心X，放在右侧
      if (node.spouseId && nodeMap.get(node.spouseId).x === 0) {
        node.x = currentX + nodeWidth/2
        const spouse = nodeMap.get(node.spouseId)
        spouse.x = node.x + nodeWidth + spacing/2
        currentX += nodeWidth * 2 + spacing
      } else if (node.x === 0) {
        node.x = currentX + nodeWidth/2
        currentX += nodeWidth + spacing
      }
    })

    // 检查重叠并调整
    for (let i = 1; i < nodes.length; i++) {
      const prevNode = nodes[i-1]
      const currNode = nodes[i]
      const minGap = nodeWidth + spacing
      const actualGap = currNode.x - prevNode.x
      if (actualGap < minGap) {
        const offset = minGap - actualGap
        // 当前节点及右侧节点偏移
        for (let j = i; j < nodes.length; j++) {
          nodes[j].x += offset
          // 同步调整子节点X，保持对齐
          nodes[j].children.forEach(child => {
            const childNode = nodeMap.get(child.id)
            if (childNode) childNode.x += offset/2
          })
        }
      }
    }
  })
}

adjustXPositions()

这个示例实现了基础的层级划分、坐标分配和重叠调整，你可以根据实际节点尺寸、间距需求修改参数，新增节点时只需重新调用对应的层级计算和局部X调整函数即可。

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