实现Squarify Layout

前言 #

这一篇文章是继vite-bundle-analyzer优化后的一次尝试。因为vite-bundle-analyzer使用了@foamsearch/tree尽管这个库十分优秀但是他不提供TreeShake导致 我无法尽可能的压缩体积,因此我需要寻找一个其他的替代方案。本文会从Squarify算法从0到1实现一个Treemap。

为什么是Squarify #

以D3的hierarchy为例。常见的矩形树图本质上是通过对数组的分层形成一个具有层次的结构以便能直观的比较同级和子级占比。这里会分别实现这几种布局算法注意这和d3-hierarchy不一致。

TreemapBinary #

根据描述就是递归的将指定节点划为近似平衡的二叉树,对于宽矩形进行水平划分,对于高矩形进行垂直划分。

function function layoutTreemap(node: Node, x: number, y: number, w: number, h: number): LayoutNodelayoutTreemap(node: Nodenode: Node, x: numberx: number, y: numbery: number, w: numberw: number, h: numberh: number): LayoutNode {
  const const layout: [number, number, number, number]layout: [number, number, number, number] = [x: numberx, y: numbery, w: numberw, h: numberh]
  let let children: LayoutNode[]children: LayoutNode[] = []

  if (node: Nodenode.Node.children: Node[]children && node: Nodenode.Node.children: Node[]children.Array<Node>.length: number
Gets or sets the length of the array. This is a number one higher than the highest index in the array.length > 0) {
    const const totalValue: numbertotalValue = node: Nodenode.Node.children: Node[]children.Array<Node>.reduce<number>(callbackfn: (previousValue: number, currentValue: Node, currentIndex: number, array: Node[]) => number, initialValue: number): number (+2 overloads)
Calls the specified callback function for all the elements in an array. The return value of the callback function is the accumulated result, and is provided as an argument in the next call to the callback function.
@paramcallbackfn A function that accepts up to four arguments. The reduce method calls the callbackfn function one time for each element in the array.@paraminitialValue If initialValue is specified, it is used as the initial value to start the accumulation. The first call to the callbackfn function provides this value as an argument instead of an array value.reduce(
      (sum: numbersum, child: Nodechild) => sum: numbersum + child: Nodechild.Node.value: numbervalue,
      0
    )
    let let accumulatedValue: numberaccumulatedValue = 0
    let let splitIndex: numbersplitIndex = 0
    // Find the split index
    for (; let splitIndex: numbersplitIndex < node: Nodenode.Node.children: Node[]children.Array<Node>.length: number
Gets or sets the length of the array. This is a number one higher than the highest index in the array.length; let splitIndex: numbersplitIndex++) {
      if (let accumulatedValue: numberaccumulatedValue + node: Nodenode.Node.children: Node[]children[let splitIndex: numbersplitIndex].Node.value: numbervalue > const totalValue: numbertotalValue / 2) {
        break
      }
      let accumulatedValue: numberaccumulatedValue += node: Nodenode.Node.children: Node[]children[let splitIndex: numbersplitIndex].Node.value: numbervalue
    }
    // Split the area and layout the children
    if (w: numberw > h: numberh) {
      const [const x1: numberx1, const w1: numberw1] = [x: numberx, w: numberw * let accumulatedValue: numberaccumulatedValue / const totalValue: numbertotalValue]
      const [const x2: numberx2, const w2: numberw2] = [const x1: numberx1 + const w1: numberw1, w: numberw - const w1: numberw1]
      let children: LayoutNode[]children = [
        ...node: Nodenode.Node.children: Node[]children.Array<Node>.slice(start?: number, end?: number): Node[]
Returns a copy of a section of an array.
For both start and end, a negative index can be used to indicate an offset from the end of the array.
For example, -2 refers to the second to last element of the array.
@paramstart The beginning index of the specified portion of the array.
If start is undefined, then the slice begins at index 0.@paramend The end index of the specified portion of the array. This is exclusive of the element at the index 'end'.
If end is undefined, then the slice extends to the end of the array.slice(0, let splitIndex: numbersplitIndex).Array<Node>.map<LayoutNode>(callbackfn: (value: Node, index: number, array: Node[]) => LayoutNode, thisArg?: any): LayoutNode[]
Calls a defined callback function on each element of an array, and returns an array that contains the results.
@paramcallbackfn A function that accepts up to three arguments. The map method calls the callbackfn function one time for each element in the array.@paramthisArg An object to which the this keyword can refer in the callbackfn function. If thisArg is omitted, undefined is used as the this value.map((child: Nodechild) => function layoutTreemap(node: Node, x: number, y: number, w: number, h: number): LayoutNodelayoutTreemap(child: Nodechild, const x1: numberx1, y: numbery, const w1: numberw1, h: numberh)),
        ...node: Nodenode.Node.children: Node[]children.Array<Node>.slice(start?: number, end?: number): Node[]
Returns a copy of a section of an array.
For both start and end, a negative index can be used to indicate an offset from the end of the array.
For example, -2 refers to the second to last element of the array.
@paramstart The beginning index of the specified portion of the array.
If start is undefined, then the slice begins at index 0.@paramend The end index of the specified portion of the array. This is exclusive of the element at the index 'end'.
If end is undefined, then the slice extends to the end of the array.slice(let splitIndex: numbersplitIndex).Array<Node>.map<LayoutNode>(callbackfn: (value: Node, index: number, array: Node[]) => LayoutNode, thisArg?: any): LayoutNode[]
Calls a defined callback function on each element of an array, and returns an array that contains the results.
@paramcallbackfn A function that accepts up to three arguments. The map method calls the callbackfn function one time for each element in the array.@paramthisArg An object to which the this keyword can refer in the callbackfn function. If thisArg is omitted, undefined is used as the this value.map((child: Nodechild) => function layoutTreemap(node: Node, x: number, y: number, w: number, h: number): LayoutNodelayoutTreemap(child: Nodechild, const x2: numberx2, y: numbery, const w2: numberw2, h: numberh))
      ]
    } else {
      const [const y1: numbery1, const h1: numberh1] = [y: numbery, h: numberh * let accumulatedValue: numberaccumulatedValue / const totalValue: numbertotalValue]
      const [const y2: numbery2, const h2: numberh2] = [const y1: numbery1 + const h1: numberh1, h: numberh - const h1: numberh1]
      let children: LayoutNode[]children = [
        ...node: Nodenode.Node.children: Node[]children.Array<Node>.slice(start?: number, end?: number): Node[]
Returns a copy of a section of an array.
For both start and end, a negative index can be used to indicate an offset from the end of the array.
For example, -2 refers to the second to last element of the array.
@paramstart The beginning index of the specified portion of the array.
If start is undefined, then the slice begins at index 0.@paramend The end index of the specified portion of the array. This is exclusive of the element at the index 'end'.
If end is undefined, then the slice extends to the end of the array.slice(0, let splitIndex: numbersplitIndex).Array<Node>.map<LayoutNode>(callbackfn: (value: Node, index: number, array: Node[]) => LayoutNode, thisArg?: any): LayoutNode[]
Calls a defined callback function on each element of an array, and returns an array that contains the results.
@paramcallbackfn A function that accepts up to three arguments. The map method calls the callbackfn function one time for each element in the array.@paramthisArg An object to which the this keyword can refer in the callbackfn function. If thisArg is omitted, undefined is used as the this value.map((child: Nodechild) => function layoutTreemap(node: Node, x: number, y: number, w: number, h: number): LayoutNodelayoutTreemap(child: Nodechild, x: numberx, const y1: numbery1, w: numberw, const h1: numberh1)),
        ...node: Nodenode.Node.children: Node[]children.Array<Node>.slice(start?: number, end?: number): Node[]
Returns a copy of a section of an array.
For both start and end, a negative index can be used to indicate an offset from the end of the array.
For example, -2 refers to the second to last element of the array.
@paramstart The beginning index of the specified portion of the array.
If start is undefined, then the slice begins at index 0.@paramend The end index of the specified portion of the array. This is exclusive of the element at the index 'end'.
If end is undefined, then the slice extends to the end of the array.slice(let splitIndex: numbersplitIndex).Array<Node>.map<LayoutNode>(callbackfn: (value: Node, index: number, array: Node[]) => LayoutNode, thisArg?: any): LayoutNode[]
Calls a defined callback function on each element of an array, and returns an array that contains the results.
@paramcallbackfn A function that accepts up to three arguments. The map method calls the callbackfn function one time for each element in the array.@paramthisArg An object to which the this keyword can refer in the callbackfn function. If thisArg is omitted, undefined is used as the this value.map((child: Nodechild) => function layoutTreemap(node: Node, x: number, y: number, w: number, h: number): LayoutNodelayoutTreemap(child: Nodechild, x: numberx, const y2: numbery2, w: numberw, const h2: numberh2))
      ]
    }
  }
  return { LayoutNode.node: Nodenode, LayoutNode.layout: [number, number, number, number]layout, LayoutNode.children: LayoutNode[]children }
}

TreemapDice/Slice/Both #

根据d3-hierarchy文档可以得知Treemap也有水平或者垂直以及混合他们的布局方式。这里提供了一个简易的算法实现。

export function function layoutTreemap(data: Node[], x: number, y: number, w: number, h: number, mode: LayoutMode): LayoutNode[]layoutTreemap(data: Node[]data: Node[], x: numberx: number, y: numbery: number, w: numberw: number, h: numberh: number, mode: LayoutModemode: type LayoutMode = "slice" | "dice" | "auto"LayoutMode) {
  const const result: LayoutNode[]result: LayoutNode[] = []
  if (!data: Node[]data) { return const result: LayoutNode[]result }
  const const recursion: (start: number, x: number, y: number, w: number, h: number) => voidrecursion = (start: numberstart: number, x: numberx: number, y: numbery: number, w: numberw: number, h: numberh: number) => {
    while (start: numberstart < data: Node[]data.Array<Node>.length: number
Gets or sets the length of the array. This is a number one higher than the highest index in the array.length) {
      const const total: numbertotal = data: Node[]data.Array<Node>.reduce<number>(callbackfn: (previousValue: number, currentValue: Node, currentIndex: number, array: Node[]) => number, initialValue: number): number (+2 overloads)
Calls the specified callback function for all the elements in an array. The return value of the callback function is the accumulated result, and is provided as an argument in the next call to the callback function.
@paramcallbackfn A function that accepts up to four arguments. The reduce method calls the callbackfn function one time for each element in the array.@paraminitialValue If initialValue is specified, it is used as the initial value to start the accumulation. The first call to the callbackfn function provides this value as an argument instead of an array value.reduce((acc: numberacc, cur: Nodecur) => acc: numberacc += cur: Nodecur.Node.value: numbervalue, 0)
      const const node: Nodenode = data: Node[]data[start: numberstart]
      const const sizeToArea: numbersizeToArea = const node: Nodenode.Node.value: numbervalue / const total: numbertotal
      const const vertical: [number, number, number, number]vertical = [x: numberx, y: numbery, w: numberw, h: numberh * const sizeToArea: numbersizeToArea] as [number, number, number, number]
      const const horizontal: [number, number, number, number]horizontal = [x: numberx, y: numbery, w: numberw * const sizeToArea: numbersizeToArea, h: numberh] as [number, number, number, number]
      const const preferHorizontal: booleanpreferHorizontal = !!(const node: Nodenode.Node.children: Node[]children && const node: Nodenode.Node.children: Node[]children.Array<Node>.length: number
Gets or sets the length of the array. This is a number one higher than the highest index in the array.length & 1)
      const const direction: "horizontal" | "vertical"direction = mode: LayoutModemode === 'auto'
        ? const preferHorizontal: booleanpreferHorizontal ? 'horizontal' : 'vertical'
        : mode: "slice" | "dice"mode === 'slice'
        ? 'vertical'
        : 'horizontal'
      const const layout: [number, number, number, number]layout = const direction: "horizontal" | "vertical"direction === 'vertical' ? const vertical: [number, number, number, number]vertical : const horizontal: [number, number, number, number]horizontal
      const result: LayoutNode[]result.Array<LayoutNode>.push(...items: LayoutNode[]): number
Appends new elements to the end of an array, and returns the new length of the array.
@paramitems New elements to add to the array.push({
        LayoutNode.node: Nodenode,
        LayoutNode.layout: [number, number, number, number]layout,
        LayoutNode.children: LayoutNode[]children: const node: Nodenode.Node.children: Node[]children
          ? function layoutTreemap(data: Node[], x: number, y: number, w: number, h: number, mode: LayoutMode): LayoutNode[]layoutTreemap(const node: Nodenode.Node.children: Node[]children, ...const layout: [number, number, number, number]layout, mode: LayoutModemode)
          : []
      })
      if (const direction: "horizontal" | "vertical"direction === 'horizontal') {
        x: numberx += const layout: [number, number, number, number]layout[2]
      } else {
        y: numbery += const layout: [number, number, number, number]layout[3]
      }
      start: numberstart++
    }
  }

  const recursion: (start: number, x: number, y: number, w: number, h: number) => voidrecursion(0, x: numberx, y: numbery, w: numberw, h: numberh)
  return const result: LayoutNode[]result
}

TreemapSquarify #

根据 Mark Bruls、Kees Huizing、Jarke J. van Wijk 算法实现分割 使生成的矩形尽量接近正方形，拥有更佳的平均长宽比。

function function layoutTreemap(data: Node[], x: number, y: number, w: number, h: number): LayoutNode[]layoutTreemap(data: Node[]data: Node[], x: numberx: number, y: numbery: number, w: numberw: number, h: numberh: number) {
  const const result: LayoutNode[]result: LayoutNode[] = []

  const const worst: (start: number, end: number, shortSide: number, totalSizes: number, sizeToArea: number) => numberworst = (start: numberstart: number, end: numberend: number, shortSide: numbershortSide: number, totalSizes: numbertotalSizes: number, sizeToArea: numbersizeToArea: number) => {
    const const first: Nodefirst = data: Node[]data[start: numberstart]
    const const last: Nodelast = data: Node[]data[end: numberend]
    const const maxArea: numbermaxArea = const first: Nodefirst.Node.value: numbervalue * sizeToArea: numbersizeToArea
    const const minArea: numberminArea = const last: Nodelast.Node.value: numbervalue * sizeToArea: numbersizeToArea
    return var Math: Math
An intrinsic object that provides basic mathematics functionality and constants.Math.Math.max(...values: number[]): number
Returns the larger of a set of supplied numeric expressions.
@paramvalues Numeric expressions to be evaluated.max(
      ((shortSide: numbershortSide ** 2) * const maxArea: numbermaxArea) / (totalSizes: numbertotalSizes ** 2),
      (totalSizes: numbertotalSizes * totalSizes: numbertotalSizes) / ((shortSide: numbershortSide ** 2) * const minArea: numberminArea)
    )
  }

  const const squarify: (start: number, x: number, y: number, w: number, h: number) => voidsquarify = (start: numberstart: number, x: numberx: number, y: numbery: number, w: numberw: number, h: numberh: number) => {
    while (start: numberstart < data: Node[]data.Array<Node>.length: number
Gets or sets the length of the array. This is a number one higher than the highest index in the array.length) {
      const const total: numbertotal = data: Node[]data.Array<Node>.reduce<number>(callbackfn: (previousValue: number, currentValue: Node, currentIndex: number, array: Node[]) => number, initialValue: number): number (+2 overloads)
Calls the specified callback function for all the elements in an array. The return value of the callback function is the accumulated result, and is provided as an argument in the next call to the callback function.
@paramcallbackfn A function that accepts up to four arguments. The reduce method calls the callbackfn function one time for each element in the array.@paraminitialValue If initialValue is specified, it is used as the initial value to start the accumulation. The first call to the callbackfn function provides this value as an argument instead of an array value.reduce((acc: numberacc, cur: Nodecur) => acc: numberacc += cur: Nodecur.Node.value: numbervalue, 0)
      const const shortSide: numbershortSide = var Math: Math
An intrinsic object that provides basic mathematics functionality and constants.Math.Math.min(...values: number[]): number
Returns the smaller of a set of supplied numeric expressions.
@paramvalues Numeric expressions to be evaluated.min(w: numberw, h: numberh)
      const const sizeToArea: numbersizeToArea = (w: numberw * h: numberh) / const total: numbertotal
      let let end: numberend = start: numberstart
      let let areaInRun: numberareaInRun = 0
      let let oldWorst: numberoldWorst = 0
      while (let end: numberend < data: Node[]data.Array<Node>.length: number
Gets or sets the length of the array. This is a number one higher than the highest index in the array.length) {
        const const area: numberarea = data: Node[]data[let end: numberend].Node.value: numbervalue * const sizeToArea: numbersizeToArea
        const const newWorst: numbernewWorst = const worst: (start: number, end: number, shortSide: number, totalSizes: number, sizeToArea: number) => numberworst(start: numberstart, let end: numberend, const shortSide: numbershortSide, let areaInRun: numberareaInRun + const area: numberarea, const sizeToArea: numbersizeToArea)
        if (let end: numberend > start: numberstart && let oldWorst: numberoldWorst < const newWorst: numbernewWorst) { break }
        let areaInRun: numberareaInRun += const area: numberarea
        let oldWorst: numberoldWorst = const newWorst: numbernewWorst
        let end: numberend++
      }
      const const split: numbersplit = var Math: Math
An intrinsic object that provides basic mathematics functionality and constants.Math.Math.round(x: number): number
Returns a supplied numeric expression rounded to the nearest integer.
@paramx The value to be rounded to the nearest integer.round(let areaInRun: numberareaInRun / const shortSide: numbershortSide)
      let let areaInLayout: numberareaInLayout = 0
      for (let let i: numberi = start: numberstart; let i: numberi < let end: numberend; let i: numberi++) {
        const const node: Nodenode = data: Node[]data[let i: numberi]
        const const area: numberarea = const node: Nodenode.Node.value: numbervalue * const sizeToArea: numbersizeToArea
        const const lower: numberlower = var Math: Math
An intrinsic object that provides basic mathematics functionality and constants.Math.Math.round(x: number): number
Returns a supplied numeric expression rounded to the nearest integer.
@paramx The value to be rounded to the nearest integer.round(const shortSide: numbershortSide * let areaInLayout: numberareaInLayout / let areaInRun: numberareaInRun)
        const const upper: numberupper = var Math: Math
An intrinsic object that provides basic mathematics functionality and constants.Math.Math.round(x: number): number
Returns a supplied numeric expression rounded to the nearest integer.
@paramx The value to be rounded to the nearest integer.round(const shortSide: numbershortSide * (let areaInLayout: numberareaInLayout + const area: numberarea) / let areaInRun: numberareaInRun)
        const const layout: [number, number, number, number]layout: [number, number, number, number] = w: numberw >= h: numberh
          ? [x: numberx, y: numbery + const lower: numberlower, const split: numbersplit, const upper: numberupper - const lower: numberlower]
          : [x: numberx + const lower: numberlower, y: numbery, const upper: numberupper - const lower: numberlower, const split: numbersplit]
        const result: LayoutNode[]result.Array<LayoutNode>.push(...items: LayoutNode[]): number
Appends new elements to the end of an array, and returns the new length of the array.
@paramitems New elements to add to the array.push({
          LayoutNode.node: Nodenode,
          LayoutNode.layout: [number, number, number, number]layout,
          LayoutNode.children: LayoutNode[]children: const node: Nodenode.Node.children: Node[]children ? function layoutTreemap(data: Node[], x: number, y: number, w: number, h: number): LayoutNode[]layoutTreemap(const node: Nodenode.Node.children: Node[]children, ...const layout: [number, number, number, number]layout) : []
        })
        let areaInLayout: numberareaInLayout += const area: numberarea
      }
      start: numberstart = let end: numberend
      if (w: numberw >= h: numberh) {
        x: numberx += const split: numbersplit
        w: numberw -= const split: numbersplit
      } else {
        y: numbery += const split: numbersplit
        h: numberh -= const split: numbersplit
      }
    }
  }

  const squarify: (start: number, x: number, y: number, w: number, h: number) => voidsquarify(0, x: numberx, y: numbery, w: numberw, h: numberh)
  return const result: LayoutNode[]result
}

总结 #

平均长宽比是指生成的矩形长宽的比值，越佳的平均长宽比，矩形越接近正方形，用户观感的体验也越好。节点有序性是指输入数据权重值发生变化时，树图节点位置的变化程度。 有序的节点，树图的稳定性也更加优秀。

参考 #

• d3-hierarchy
• squarify