跳到主要内容

思维导图布局算法的实现

· 阅读需 4 分钟
熊滔

思维导图布局实现，如下

简单考虑，只考虑向右展开的布局。

已经条件，知道根节点的位置 (rootX,rootY)(\text{rootX}, \text{rootY})，以及所有节点的大小（宽高），求其他节点的位置 (x,y)(x, y)。

首先看子节点的 xx 和父节点 parentX\text{parentX} 的关系，非常简单，子节点在父节点右侧的 marginX\text{marginX} 处，即

childX=parentX+parentWidth+marginX\text{childX} = \text{parentX} + \text{parentWidth} + \text{marginX}

对于子节点的 yy 的计算就比较复杂了，考虑下图

在知道父元素的位置和宽高的情况下以及所有子节点总体高度的情况下，计算所有子节点整体的 yy，在 yy 方向上要满足一个关系，就是父节点和子节点整体是居中对齐的，即满足

parentY+parentHeight2=childrenY+childrenHeight2\text{parentY} + \dfrac{\text{parentHeight}}{2} = \text{childrenY} + \frac{\text{childrenHeight}}{2}

可以得到

childrenY=parentY+parentHeight2−childrenHeight2\text{childrenY} = \text{parentY} + \dfrac{\text{parentHeight}}{2} - \frac{\text{childrenHeight}}{2}

在知道总体的一个位置之后，计算单个子节点的位置就很简单了，比如对于第 ii 个子节点，它离顶部的距离就是之前所有节点的实际高度加上所有间距

child[i].childrenTop=∑index=0i−1child[index].actualHeight+(i−1)×marginY\text{child[i].childrenTop} = \sum_{\text{index} = 0}^{i - 1}\text{child[index].actualHeight} + (i - 1) \times \text{marginY}

但是这里还需要做一个调整，这里计算的是这个节点占据区域的整体位置，有可能这个节点的高度小于占据的高度，我们还需要将这个节点居中

child.top = child.childrenTop+child.actualHeight - child.height2\text{child.top = child.childrenTop} + \frac{\text{child.actualHeight - child.height}}{2}

上面我们假设 childrenHeight\text{childrenHeight} 是已知的，但实际上是需要计算的，当然很好算，就是所有子节点的占据的高度之和加上所有的间距，注意，这里占据的高度和节点的 height\text{height} 值并不相等，一个节点占据的高度(actualHeight\text{actualHeight})的计算方法是

node.actualHeight=max⁡(node.height,node.childrenHeight))\text{node.actualHeight} = \max(\text{node.height}, \text{node.childrenHeight}))

所有 childrenHeight\text{childrenHeight} 的计算为

node.childrenHeight=∑inchildren[i].actualHeight+(n−1)×marginY\text{node.childrenHeight} = \sum_{i}^{n}\text{children[i].actualHeight} + (n - 1) \times \text{marginY}

需要两次遍历，第一次遍历计算 xx、childrenHeight\text{childrenHeight} 和 actualHeight\text{actualHeight}，第二次遍历计算 yy，可以参考以下代码

const MARGIN_X = 36;
const MARGIN_Y = 16;

const dfs = (node: MindNodeElement, {
  before,
  after,
}, parent: MindNodeElement | null = null, index = 0) => {
  before?.(node, parent, index);
  node.children.forEach((child, index) => {
    this.dfs(child, {
      before,
      after,
    }, node, index);
  });
  after?.(node, parent, index);
}

const layout = (node: MindNodeElement): MindNodeElement => {
  this.dfs(draft, {
    before: (node, parent) => {
      if (parent) {
        node.x = parent.x + parent.width + MARGIN_X;
      }
    },
    after: (node) => {
      if (node.children.length > 0) {
        node.childrenHeight = node.children.reduce((pre, cur) => {
          return pre + cur.actualHeight;
        }, 0) + (node.children.length - 1) * MARGIN_Y;
        node.actualHeight = Math.max(node.childrenHeight, node.height);
      } else {
        node.actualHeight = node.height;
        node.childrenHeight = 0;
      }
    }
  })

  this.dfs(draft, {
    before: (node, parent, index) => {
      if (!parent) return;

      const baseY = parent.y + parent.height / 2 - parent.childrenHeight / 2;
      const beforeSiblings = index > 0 ? parent.children.slice(0, index) : [];
      const siblingsHeight = beforeSiblings.reduce((pre, cur) => {
        return pre + cur.actualHeight;
      }, 0) + beforeSiblings.length * MARGIN_Y;

      const childrenTop = baseY + siblingsHeight;
      node.y = childrenTop + (node.actualHeight - node.height) / 2;
    }
  })
}