Wei Dong is a front engineer of Wedoctor. Growth is the process of constantly opening the black box.
The background,
In our work and life, we often encounter rectangular tree diagrams. The following two diagrams are familiar to us.
Recently, I just received a demand to draw the rectangular tree graph of outpatient diseases (as shown below). Although echart, D3 and other frameworks have related implementations, I was curious about their implementation, so I made an in-depth study of their implementation principles. Next, we will introduce the realization of rectangle tree from layout algorithm, color filling and Canvas event system.
Second, layout algorithm
Let’s say we have a sorted set of values that add up to 100 for our convenience
Const data = [{name: 'disease ', value: 36,}, {name:' disease ', value: 30,}, {name: 'disease ', value: 23,}, {name:' disease ', value: 23,}, {name: 'disease' '4' disease, value: 8,}, {name: '5' disease, value: 2,}, {name: '6' disease, value: 1,}]Copy the code2.1 Slice and Dice Algorithm – Start with the simplest implementation
The most easily identifiable feature of the rectangle tree diagram in the requirement is the area/total area of the small rectangle = the number of patients with the disease/the total number of patients. If this feature is only implemented, the rectangle is filled from left to right, and only the area of the small rectangle is considered when filling, the effect is shown in the following figure
We found that both aesthetics and differentiation were not ideal. The right-most rectangle, which was relatively small, did not exist, and it was difficult to select the mouse to view details.
2.2 Squarified algorithm – Square
Next, we further extract requirements characteristics to optimize the layout. We found that there were no long and narrow rectangles in the requirement, but most of the rectangles were very close to squares, and in fact the average aspect ratio was the first metric to evaluate a rectangular tree. Bruls proposed a layout algorithm called Squarified in 1999:
- Sort the child nodes in descending order by weight (value in this case)
- Starting from the first child node, fill the large rectangle with a left-to-right or top-down filling strategy along the shortest edge, immediately to the left or top (depending on the shortest edge)
- When the rectangle of the ith sub-node is inserted, two modes of the same row and new row/column are calculated respectively, and the average aspect ratio of the filled small rectangle from the 1st to the i-1st is compared. The filling method of the ith node with the average aspect ratio lower (close to 1) is selected
As you can see, this is a recursive process, with the core code annotated as follows:
/ * * *@param {Array} Children Array of rectangular areas for layout *@param {Array} Row is an array of rectangular areas for layout *@param {Number} MinSide * / short side
const squarify = (children, row, minSide) = > {
// Recursive exit
if (children.length === 1) {
return layoutLastRow(row, children, minSide);
}
const rowWithChild = [...row, children[0]].// The row in the layout rectangle is empty
// Or add children[0] rowWithChild worst aspect ratio better than row (close to 1)
// This might be a little hard to understand, but the logic here corresponds to step 3 described above.
// If this condition is met, fill the column with the same row (depending on the short edge), otherwise create a new row/column
if (row.length === 0 || worstRatio(row, minSide) >= worstRatio(rowWithChild, minSide)) {
// Delete children[0] from children
children.shift();
// execute squarify recursively
return squarify(children, rowWithChild, minSide);
} else {
// Draw the small rectangle inside the row
layoutRow(row, minSide, getMinSide().vertical);
returnsquarify(children, [], getMinSide().value); }};/** * Worst aspect ratio (see reference 1) *@param {Array} row
* @param {Number} MinSide * / short side
function worstRatio(row, minSide) {
const sum = row.reduce(sumReducer, 0);
const rowMax = getMaximum(row);
const rowMin = getMinimum(row);
return Math.max(((minSide ** 2) * rowMax) / (sum ** 2), (sum ** 2) / ((minSide ** 2) * rowMin));
}
const Rectangle = {
data: [].xBeginning: 0.yBeginning: 0.totalWidth: canvasWidth,
totalHeight: canvasHeight,
};
/** * gets the shortest edge, vertical if height is short, horizontal otherwise */
const getMinSide = () = > {
if (Rectangle.totalHeight > Rectangle.totalWidth) {
return { value: Rectangle.totalWidth, vertical: false };
}
return { value: Rectangle.totalHeight, vertical: true };
};
/** * Calculate the coordinates (x,y,width,height) of each rectangle in the row to be laid out@param {Array} row
* @param {Number} * height is short@param {Boolean} Vertical Indicates whether the layout is vertical. */
const layoutRow = (row, height, vertical) = > {
// Calculate the total area first and divide by the height (short side) to get the width
// Since the rectangles are filled along the heights, the sum of the heights of all row rectangles equals the height of the Rectangle, and the width of the Rectangle is rowWidth
// What is called "fill along height"
// _______________________________
// | A | |
/ / | ____________ hold | |
// |_____B______|__________________|
// {--rowWidth--}
const rowWidth = row.reduce(sumReducer, 0) / height;
row.forEach((rowItem) = > {
const rowHeight = rowItem / rowWidth; // The height of the small rectangle
const { xBeginning } = Rectangle;
const { yBeginning } = Rectangle;
let data;
if(! vertical) {// The position of the small rectangle,
data = {
x: xBeginning,
y: yBeginning,
width: rowWidth,
height: rowHeight,
};
// Move yBeginning to draw the next rectangle
Rectangle.yBeginning += rowHeight;
}
Rectangle.data.push(data);
});
// The rectangle inside the row is drawn
// reset xBeginning, yBeginning, totalWidth
if(vertical) { Rectangle.xBeginning += rowWidth; Rectangle.yBeginning -= height; Rectangle.totalWidth -= rowWidth; }};Copy the codeIts drawing process is shown in the figure
2.3 Other Algorithms
The Pivot algorithmandStrip algorithmThe: Squarified algorithm greatly improves the aspect ratio of rectangles, but sorts the data set first when drawing the graph. When the weights change, there will be a big jump between the old and new tree graphs, and its stability is poor.The Pivot algorithmandStrip algorithmBalance aspect ratio and stability.BinaryTreeBinary tree layout algorithm: recursively divide the specified node into approximately balanced binary tree, select horizontal partition for the wide rectangle, select vertical partition for the tall rectangle layout method
This article does not go into details, see reference link 2 for more information.
2.4 Evaluation Indicators
We mainly evaluate the performance of tree layout algorithm from the average aspect ratio AAR, stability, continuity and other indicators.
Three, color filling
This process is relatively simple, refer to Echart’s scheme, you can set a fixed array of colors, cyclic access
const colors = ['#c23531', '#2f4554', '#61a0a8', '#d48265', '#91c7ae', '#749f83', '#ca8622']
Copy the code
4. Canvas event system
When the mouse moves over a small rectangle, we want to show tips. Since Canvas exists as a whole Canvas and all content is just the result of its internal rendering, we cannot bind various events in the graph rendered by Canvas just like listening for events on Dom elements. How do the rectangles listen for mouse events?
- We can simulate adding events to small rectangles by using the following two apis (Path2D has compatibility issues)
isPointInPath(path, x, y, fillRule)Used to check whether (x, y) is on path- Path: indicates the Path2D application path.
- X: indicates the x coordinate of the detection point
- Y: indicates the y coordinate of the detection point
- FillRule: Algorithm used to determine whether a point is in or out of a path. Nonzero “: non-zero surround rule, default rule. Evenodd “: The odd surround principle.
Path2D: Declare a path with the same path methods as CTX (beginPath, moveTo, etc.)
The simplified core code is as follows:
interface diseaseInfo {
name: string;
value: number;
}
interface rectInfo {
x: number;
y: number;
width: number;
height: number;
data: diseaseInfo
}
rects.forEach((item: rectInfo) = > {
const path = new Path2D()
path.rect(item.x, item.y, item.width, item.height)
ctx.fill(path)
item.path = path
})
const canvasInfo = canvas.getBoundingClientRect()
canvas.addEventListener('mousemove'.(e) = > {
result.forEach(item= > {
if(ctx.isPointInPath(item.path, e.clientX - canvasInfo.left, e.clientY - canvasInfo.top)) {
/ / show the tips
showTips(e.clientX, e.clientY, item.data)
}
})
})
Copy the code-
I also saw an idea in the community that was very clever. The core principle is to mirror an off-screen CanvasOffscreenCanvas, randomly draw a child element ID with a unique RGBA color value when drawing child elements, and then synchronously draw child elements with this color value to OffscreenCanvas. (The only difference between original Canvas and Canvas canvas is that the pixel value of each small rectangle is different and the position size is exactly the same). When the mouse event is monitored on the original canvas, the relative coordinate (x,y) can be obtained, and then the color value corresponding to the coordinate (x,y) can be found in OffscreenCanvas combined with getImageData API(the return value includes rGBA value of (x,y)), so as to find the child element ID
-
other
- Ray method (if the number of points intersected with one side of the polygon is odd, the points are inside the polygon.)
- Angle method (If a point is inside a polygon, then the Angle between the point and all the vertices of the polygon should add up to exactly 360°. Only for convex polygons)
Generally mature visualization frameworks have a publish-subscribe event-based system to support the binding of various events in Canvas.
After a series of operations, the final results are as follows:
5. Reference materials
- www.win.tue.nl/~vanwijk/st…
- zhuanlan.zhihu.com/p/57873460
- Juejin. Cn/post / 688820…
