Writer: Curious

preface

Some time ago, netease Cloud Music launched an H5 activity based on the social voting method of acquaintances. This activity divided the grid blocks according to the weight value of the votes, and greatly increased the fun through the seamless squeezing effect between the grid blocks. This article will focus on how to achieve a stable dynamic lattice squeezing effect based on TreemAP (Rectangular tree graph) and some problems encountered in this process.

Rectangular tree graph exploration

Input a set of 18 random size values, how to make this set of data weight values on a fixed size canvas map on the two-dimensional plane and render 18 different size grids? Is it possible to create visually distinct boundaries, so that people can read at a glance, which lattice composition is the largest, and which lattice composition seems insignificant? In front end engineering practice, using the webpack-bundle-Analyzer plug-in, reminiscent of the webPack compilation scenario, generates a visual rectangular tree of all the packaged files. One idea might be to try using a rectangular tree, as shown below:

​

Stability of the algorithm

Treemap (rectangular tree graph) was first proposed by American computer scientist Ben Shneiderman in 1992. In order to deal with the common problem of hard disk full, Ben Shneiderman innovatively proposed the idea of generating directory tree structure visualization. This representation even found a place in later rectangular art.

Common rectangular tree diagram

Many data sets are hierarchical in nature, and a good hierarchical visualization facilitates rapid multiscale differentiation: a microscopic view of individual elements and a macroscopic view of the entire data set. Rectangular tree graph is suitable for displaying hierarchical data, which can intuitively reflect the comparison between the same level.

Take the implementation of D3-Hierarchy as an example:

treemapBinary

The idea is to recursively divide the specified nodes into approximately balanced binary trees, and select horizontal partitions for wide rectangles and vertical partitions for tall rectangles.

  function partition(i, j, value, x0, y0, x1, y1) {
    while (k < hi) {
      var mid = k + hi >>> 1;
      if (sums[mid] < valueTarget) k = mid + 1;
      else hi = mid;
    }

    if ((valueTarget - sums[k - 1]) < (sums[k] - valueTarget) && i + 1 < k) --k;

    var valueLeft = sums[k] - valueOffset,
        valueRight = value - valueLeft;
		/ / width of the rectangle
    if ((x1 - x0) > (y1 - y0)) {
      var xk = value ? (x0 * valueRight + x1 * valueLeft) / value : x1;
      partition(i, k, valueLeft, x0, y0, xk, y1);
      partition(k, j, valueRight, xk, y0, x1, y1);
    } else {
      / / high rectangle
      varyk = value ? (y0 * valueRight + y1 * valueLeft) / value : y1; partition(i, k, valueLeft, x0, y0, x1, yk); partition(k, j, valueRight, x0, yk, x1, y1); }}}Copy the code

Figure:

treemapDice

According to the value of the child node of each specified node, the rectangle region calculated from the input coordinates of X0, y0, X1 and y1 is divided horizontally. Starting from the left edge (x0) coordinates of the given rectangle, the partitioned children are arranged in order.

export default function (parent, x0, y0, x1, y1) {
    var nodes = parent.children,
        node,
        i = -1,
        n = nodes.length,
        k = parent.value && (x1 - x0) / parent.value

    // Divide horizontally in order
    while(++i < n) { ; (node = nodes[i]), (node.y0 = y0), (node.y1 = y1) ; (node.x0 = x0), (node.x1 = x0 += node.value * k) } }Copy the code

Figure:

treemapSlice

According to the value of the child node of each specified node, the rectangle region calculated from the input coordinates of X0, y0, X1 and y1 is divided in the vertical direction. Starting from the coordinates of the upper edge (y0) of the given rectangle, the segmented child elements are arranged in order.

export default function (parent, x0, y0, x1, y1) {
    var nodes = parent.children,
        node,
        i = -1,
        n = nodes.length,
        k = parent.value && (x1 - x0) / parent.value

    // Vertically split in order
    while(++i < n) { ; (node = nodes[i]), (node.y0 = y0), (node.y1 = y1) ; (node.x0 = x0), (node.x1 = x0 += node.value * k) } }Copy the code

Figure:

treemapSliceDice

TreemapSlice if the specified node has an odd depth value; treemapDice if not.

export default function (parent, x0, y0, x1, y1) {
    // Determine the node depth; (parent.depth &1 ? slice : dice)(parent, x0, y0, x1, y1)
}
Copy the code

Figure:

treemapSquarify

This squarified tree layout splits the rectangles as closely as possible using the specified ratio, making the resulting rectangles as close to the square as possible, with a better average aspect ratio.

export function squarifyRatio(ratio, parent, x0, y0, x1, y1) {
    while (i0 < n) {
        // Find the next non-empty node.
        do sumValue = nodes[i1++].value
        minValue = maxValue = sumValue
        alpha = Math.max(dy / dx, dx / dy) / (value * ratio)
        beta = sumValue * sumValue * alpha
        minRatio = Math.max(maxValue / beta, beta / minValue)

        // Keep adding nodes while the aspect ratio maintains or improves.
        for (; i1 < n; ++i1) {
            sumValue += nodeValue = nodes[i1].value
            if (nodeValue < minValue) minValue = nodeValue
            if (nodeValue > maxValue) maxValue = nodeValue
            beta = sumValue * sumValue * alpha
            newRatio = Math.max(maxValue / beta, beta / minValue)
            if (newRatio > minRatio) {
                sumValue -= nodeValue
                break
            }
            minRatio = newRatio
        }
    }
}
Copy the code

treemapResquarify

TreemapResquarify uses a squarified tree layout for the first time to ensure a good average aspect ratio. Subsequent data changes only change the size of the nodes, not their relative positions. This layout works better for tree animations because it avoids the instability of the layout caused by node changes, which can be distracting.

function resquarify(parent, x0, y0, x1, y1) {
    if ((rows = parent._squarify) && rows.ratio === ratio) {
        var rows,
            row,
            nodes,
            i,
            j = -1,
            n,
            m = rows.length,
            value = parent.value
        // In the subsequent layout, only the size of the node is changed, not the relative position
        while(++j < m) { ; (row = rows[j]), (nodes = row.children)for (i = row.value = 0, n = nodes.length; i < n; ++i) row.value += nodes[i].value
            if (row.dice)
                treemapDice(row, x0, y0, x1, value ? (y0 += ((y1 - y0) * row.value) / value) : y1)
            else treemapSlice(row, x0, y0, value ? (x0 += ((x1 - x0) * row.value) / value) : x1, y1)
            value -= row.value
        }
    } else {
        // Squarify is used for the first layout
        parent._squarify = rows = squarifyRatio(ratio, parent, x0, y0, x1, y1)
        rows.ratio = ratio
    }
}
Copy the code

Figure:

Detailed rectangular tree effect can be viewed in demo

conclusion

The average aspect ratio refers to the ratio of length to width of the generated rectangle. The better the average aspect ratio is, the closer the rectangle is to the square, and the better the user’s experience. Node orderliness refers to the degree of change of node position in tree graph when input data weight value changes. The stability of the tree graph is also better with ordered nodes.

* * * * Average aspect ratio Node order The stability of
treemapBinary good Part of the order general
treemapSlice Is very poor The orderly good
treemapDice Is very poor The orderly good
treemapResquarify good The orderly good
treemapSquarify good Part of the order general

As you can see, treemapSquarify has a superior average aspect ratio. On the other hand, treemapResquarify also has a good average aspect ratio when it is first laid out, and a good stability when the data weight value changes due to the ordered nature of the nodes.

Make the rectangle tree more vivid

A first demo

Start a set of demo tests based on treemapSquarify tree diagram ideas. Enter a random set of inputs with value data:

[
    { value: 10, color: 'red' },
    { value: 7,  color: 'black' },
    { value: 4,  color: 'blue' },
    ...
]
Copy the code

Perform treemapSquarify calculation and transform the generated results to obtain a set of data lists with position coordinates and width and height, as shown below:

[
    {
      x: 0,
      y: 0,
      width: 330.56,
      height: 352.94,
      data: { value: 10, color: 'red' },
    },
    {
      x: 0,
      y: 352.94,
      width: 330.56,
      height: 247.06,
      data: { value: 7, color: 'black' },
    },
    {
      x: 330.56,
      y: 0,
      width: 295.56,
      height: 157.89,
      data: { value: 4, color: 'blue' },
    }
    ...
]
Copy the code

As you can see, the input data is a random array. After treemapSquarify calculates, a set of data including x and Y coordinates, width and height is obtained. Based on this initial set of input data, we add an offset to the data. By adding a time self-increment and using the characteristics of trigonometry function, the offset is limited to a certain range of the initial data, and a set of data after the offset can be obtained. By constantly changing the offset range of the input data back and forth, multiple sets of initial data offset results can be continuously generated. As follows:

// requestAnimationFrame looping animation
const builtGraphCanvas = () = > {
  / / main logic
  treeMapAniLoop();
  requestAnimationFrame(builtGraphCanvas);
};
builtGraphCanvas();

/ / main logic
treeMapAniLoop() {
  // Increment by time,
  time += 0.02
  for (let i = 0; i < dataInput.length; i++) {
    // Use trigonometric functions to limit the range and change the input back and forth
    const increment = i % 2= =0 ? Math.sin(time + i) : Math.cos(time + i)
    // Assign an offset to change the initial data range
    dataInput[i].value =
      vote[i] + 0.2 * vote[vote.length - 1] * increment * increment
  }

// The treemapSquarify algorithm generates the result
const result = getTreemap({
   data: dataInput,      // Data input with offset
   width: canvasWidth,   / / canvas width
   height: canvasHeight, / / the canvas})}Copy the code

Draw x, y coordinates and width, height on canvas canvas according to the result returned by the offset of multiple sets of data:

treeMapAniLoop() {
  // Draw canvas rectangle
  drawStrokeRoundRect() {
    cxt.translate(x, y);
    cxt.beginPath(0);
    cxt.arc(width - radius, height - radius, radius, 0.Math.PI / 2); cxt.lineTo(radius, height); . cxt.fill(); cxt.stroke(); }}Copy the code

In the browser requestAnimationFrame redraw method, since the initial input data is constantly changing the offset with time increment, a series of resulting data is continuously generated, rendering the animation as follows:

Grid rearrangement

As mentioned above, it seems perfect to input a set of data values, use treemapSquarify to compute the grid coordinates and width and height, and use time incrementing to keep the animation “squeezed”. Try several different sets of input data sources to verify the render effect in various input scenarios, one of which looks like this:

Take a closer look at the bouncing of the lattice after a short, perfect squeeze. In the actual input data source test, it is found that the probability of the jumping of the grid is relatively high. This is actually a rearrangement of the grid. If we sort the grid blocks generated by the initial data on the canvas according to the labels 1-18, we find that the grid block at position 3 at the beginning has changed to position 5 after the autoincrement offset. If the input data sources are very different, the offset of such positions will be more severe. Therefore, the direct representation is that the grid animation on the canvas is beating continuously, which is very poor stability, and the user’s perception experience will be poor.

The reason for the rearrangement

As mentioned above, treemapSquarify makes the resulting rectangle as close to a square as possible, with a good average aspect ratio. In fact, it does not consider how all the levels should be divided at the same time in the beginning, which avoids a lot of computation. The main idea is:

  • Arrange the child nodes in order from largest to smallest;
  • When a node starts filling, there are two options: add it directly to the current row, or fix the current row and start a new row in the remaining rectangular space;
  • The final choice depends on which option will result in a better average aspect ratio, and the lower the aspect ratio, the better the layout

Taking dataset [3, 2, 6, 4, 1, 2, 6] as an example, the sorted sequence is [6, 6, 4, 3, 2, 2, 1]. Step 1, the length of the block is 4 and the width is 1.5, so the length/width ratio is 4/1.5 = 2.6.. Step 2, the length of the block is 3 and the width is 2, so the length-width ratio is 3/2 = 1.5… By analogy, the strategy is to choose the option with a lower average aspect ratio

Therefore, if the input data is offset to a certain extent, The calculation of treemapSquarify is greedy, it will only use the current optimal aspect ratio selection, so when the offset exceeds a certain boundary value, the position of the output grid blocks will inevitably be inconsistent, resulting in rearrangement phenomenon.

To solve the rearrangement

In fact, as mentioned in the summary of the rectangular tree, treemapResquarify also has a very good average aspect ratio because treemapSquarify was used for the first layout. When the data weight value changes, treemapResquarify has good stability due to its unique node ordering characteristics. Therefore, we use treemapResquarify algorithm to generate results on the input values, as shown below:

this.treeMap = d3
    .treemap()
    .size([size.canvasWidth - size.arrowSize * 2, size.canvasHeight - size.arrowSize * 2])
    .padding(0)
    .round(true)
    // Ratio = 1
    .tile(d3.treemapResquarify.ratio(1))
Copy the code

According to the input value, the output result of leavseResult transformation is obtained. At this point, the position of the output is stable even if the input value is offset.

// Generate treemap results
generateTreeMap(voteTree: Array<number>) {
  this.root.sum(function(d) {
    if (d.hasOwnProperty('idx')) {
      return treeData[d.idx - 1];
    }
    return d.value;
  });

  this.treeMap(this.root);
  const leavesResult = this.root.leaves();

  // Convert the output structure
  this.result = leavesResult.map(i= > ({
    x: i.x0 + arrowSize,
    y: i.y0 + arrowSize,
    width: i.x1 - i.x0,
    height: i.y1 - i.y0,
    value: i.value,
  }));
}
Copy the code

Since the offset of the actual input does not deviate much from the initial data, the effect of the offset of the output position is relatively insignificant.

Some other ideas were tried before treemapResquarify was used to solve the rearrangement problem. For example, when recording the calculation result generated for the first time, it tries to check whether there is a grid “jump” when executing the input data self-increasing offset. If the boundary of the grid “jump” is detected, it tries to “borrow” some grid space from the surrounding of the current grid and prevent the grid “jump”, so as to avoid the rearrangement problem forcibly. However, this problem can not be solved well, in some input data contrast will appear obvious animation lag.

Animated transitions

In addition to the above known result squeeze animation, we also did a lot of transition animation. Subdivision can be divided into 6 scenes, in order to ensure the smoothness of animation, these 6 scenes are made in one canvas. Take the opening animation as an example, the grid blocks gradually bulge in sequence and then gradually shrink to the state of white grid blocks, as shown in the figure below

It works by going from state A to state B in A certain amount of time. This period of time is used as the incrementing variable of the BezierEasing method to output A Bezier animation value. Each frame changes the x and Y coordinates, width and height of state A according to this animation value, and gradually approaches state B, as shown in the core code below:

e2(t) {
  return BezierEasing(0.25.0.1.0.25.1.0)(t);
}
// The opening animation
if (this.time0 > 1 + timeOffset * result.length) {
  this.time4 += 1.5 * aniSpeed;
  const easing = this.e2(this.time4);
  const resultA = this.cloneDeep(this.result);
  // Convert the animation from A state to 0 white state
  this.setTagByResult(resultA, this.initialZeroResult, easing);
}

// The two sets of result and the tween arguments are passed in to export the mixed result.
setTagByResult(resultA, resultB, easing) {
  const result = this.result;
  for (let i = 0; i < result.length; i++) { result[i].x = resultA[i].x + easing * (resultB[i].x - resultA[i].x); result[i].y = resultA[i].y + easing * (resultB[i].y - resultA[i].y); result[i].width = resultA[i].width + easing * (resultB[i].width - resultA[i].width); result[i].height = resultA[i].height + easing * (resultB[i].height - resultA[i].height); }}Copy the code

As shown in the figure below, is the selected state of a known extrusion result page transition to a white grid block. The realization principle is similar, in a certain time range, by changing the coordinate position and size of the lattice, from the squeezed state to the white lattice block state gradually. There are more animation state changes, such as moving from an “unselected” grid state to a “selected” state; When the grid is full, the transition from the “full” state to the resulting squeeze state will not be detailed here.

Let the arrangement be well arranged

Boundary-handling in extreme scenarios is always a tricky business.

Extreme scenarios show problems

As you can imagine, when there is a big difference between the highest and lowest number of votes, there will be complete typographical chaos. As the graph below shows, the highest number of votes is only 20, the lowest number is 0, and the small space of the ballot box is squeezed to the point of “breathing”.

If the division were clearer, with a maximum of 140 votes and a minimum of 0, it would become even more chaotic, as shown below:

Therefore, it is necessary to carry out a reasonable transformation of the input data source, and process the cases beyond the maximum multiple ratio by case and transform them in a reasonable range. The maximum multiple is divided into three stages, 10 times, 30 times and over 30 times respectively. It is, in effect, the transformation of an unpredictable random range into a manageable reasonable range.

  // x=1-2, adjusted by the hyperbolic tangent function, output growth rate is fast to slow
  const reviseMethod = i= > Math.tanh(i / 20) * 26;
  const computeVote = (vote: number, quota: number) = > {
    // Base 100 + multiples * each times the share
    return base + (vote / minVote - 1) * quota;
  };

  const stage1 = 10;
  const stage2 = 30;
  // 10-fold interval
  const ceilStage1 = 600;
  // 30 times range
  const ceilStage2 = 1000;
  // More than 30 times
  const ceilStage3 = 1300;

  let quota;
  // Max/min ratio
  const curMultiple = maxVote / minVote;
  const data = voteList.map(i= > {
    let finalVote;

    // Different stages of processing schemes
    if (curMultiple <= stage1 + 1) {
      quota = (ceilStage1 - base) / stage1;
      const reviseValue = reviseMethod(i);
      finalVote = computeVote(reviseValue, quota);
    } else if (curMultiple <= stage2 + 1) {
      quota = (ceilStage2 - base) / stage2;
      finalVote = computeVote(i, quota);
    } else {
      // Need to hide some votes, hide some sharp corners, etc
      quota = ceilStage3 / curMultiple;
      finalVote = computeVote(i, quota);
    }

    return finalVote;
  });
  return data;
};
Copy the code

In addition to the interpartition processing of the grid blocks, the “expression”, “tag words” and “votes” in the grid blocks may also squeeze and block each other. The following is the earliest list of scenarios for tag words, but there are far more scenarios to deal with. The boundary conditions include: label word automatic horizontal arrangement, automatic vertical arrangement processing, font size adaptive, multiple word different processing, blocking between two grids processing, etc. List every possible boundary case and deal with it!

The layout is too neat

As shown below, the animation looks fine. But the highest number of votes was more than 10 times that of the lowest, and we thought that the layout of the animation was so “even” that it would be impossible to tell the difference at a glance. In order to pursue a more clearly distinguishable layout, let the grid block between enough confusion, add some “messy beauty” temperament. This problem can be better optimized by grouping the initial input data sources.

The 18 input data sources originally defined were placed in a hierarchy. We wonder if it is possible to group the data, so that when the data is mapped to a two-dimensional plane, the cells are also divided into multiple modules to show whether it will be more confusing. As shown in the code below, we set the initial values of all the tickets to 1 vote and define multiple group hierarchies, which makes the actual performance much more “messy”.

// Initial group data
export const dataGroupTree = {
  name: 'allGroup'.children: [{name: 'group1'.children: [{idx: 1.value: 1,},... ] }, {name: 'group2'.children: [...]. }, {name: 'group3'.children: [...]. ,}]};Copy the code

With a lovely sharp Angle

In the beginning, we designed the extruded grid with a little sharp corner, as shown below, with cute sharp corners on the edge of the grid. However, we found that in some scenes, sharp corners would block each other or even encounter lattice expressions. Due to the need for targeted boundary processing, it was finally removed due to time constraints.

Other problems

In fact, in addition to the above listed a few problems, but also encountered many large and small problems.

For example, it’s important to take a screenshot of the squeeze effect and share it as an image. When we share screenshots of Canvas canvas, the action of screenshots is based on the ability of HTML2Canvas library, but the screenshots are often blank. The problem was solved by adding the attribute crossOrigin=”anonymous” to the picture link when drawing pictures on canvas. Later, it was found that some Android models still had the problem of occasional screenshot blank when holding down the picture on wechat to save the picture. Finally, this problem was solved by converting the input picture link into base64 address when drawing the picture on canvas. All in all, if you want to achieve a lovely and “perfect” squeeze effect, you may encounter all kinds of problems, nothing else, deal with it!

summary

Finally, I end with a sentence from the poster: It is worth pondering, something, and the sense of youth will never expire.

Interested students can search “Bubbles” on netease Music App to have a taste.

The resources

  • Treemaps for space-constrained visualization of hierarchies
  • Squarified Treemaps​
  • d3-hierarchy
  • d3-treemap-demo

This article is published from netease Cloud Music big front end team, the article is prohibited to be reproduced in any form without authorization. Grp.music – Fe (at) Corp.Netease.com We recruit front-end, iOS and Android all year long. If you are ready to change your job and you like cloud music, join us!