Original link: http://vis.pku.edu.cn/blog/shape-based-mixed-metro-map-layout/
In graph visualization, subway map visualization is a classic visualization method, which arranges the nodes in the graph as evenly as possible in the space, while keeping the edges as much as possible and the topology of the final layout and the original graph nodes as much as possible. At the same time, in the actual diagram layout, in addition to improving the readability of the diagram, it is sometimes necessary to embed some specific motivations (motif) into the diagram, which can improve the artistic effect of the diagram layout, and may also improve the user’s understanding of Cognitive abilities of layout.
In the paper “Shape-Guided Mixed Metro Map Layout” [1], Tobias Batik et al. of the Vienna University of Technology proposed a hybrid layout method that combines metro map layout and shape embedding (Fig. 1), which can support user While the defined shapes are embedded in the final map layout, the overall map layout is optimized to the subway map standard.
Figure 1: Combining metro map criteria and heart shape, resulting map layout
In the paper, the author first lists the design requirements of the layout method, which combines the design requirements of traditional subway map layouts and the requirements of user-defined shape embedding (Figure 2).
Figure 2: Design Requirements for the Algorithm
According to this design requirement, the author proposes to “use a part of the points and edges to represent the shape to be embedded as clearly as possible, so that other points and edges are laid out according to the standard of the subway map.” According to this direction, the author proposes to be divided into The three-step algorithm flow of “shape matching-layout optimization-layout fine-tuning” (Figure 3).
Figure 3: The pipeline proposed in the paper
To embed a shape into a subway map, it is first necessary to decide which points and edges are to be laid out into this embedded shape, which is the first step of the whole algorithm, shape matching. In the paper, the author uses the Direction-based Frechet Integral distance[2] to measure. Using this method to calculate, can make the matching non-deformable with translation and scaling, and because in the actual layout, the discrete folding is involved in the calculation. line segment, so it can be solved relatively simply using dynamic programming.
In layout optimization, the author sets several types of energy functions to guide the direction of optimization. The energy functions include the following:
- Shape energy function: Make the distance from the points matching the shape to the corresponding position of the shape, so that these points constitute the embedded shape as much as possible.
- Edge energy function: The difference between the length of each edge and the standard edge, making each edge as bad as possible.
- Angle energy function: the difference between the angle between the two adjacent sides connecting the same point to the standard angle, to avoid a particularly small angle.
- Topological structure energy function: The difference between the actual distance between each point and each subway station makes the final layout close to the actual geographic layout.
- Octolinear energy function: The difference between each edge and the octolinear direction closest to its angle, so that the final angle of each edge is as much as possible in one of the octolinear directions.
Since it is difficult to determine which is the optimal eight-linear direction of each edge at the beginning, the optimization is divided into two steps. First, the first four energy functions are used to optimize the general layout, and then the optimal layout of each edge is determined according to the current results. Similar eight linear directions, and then add the fifth energy function to the optimization.
Even after layout optimization, there are some obvious areas for improvement in the graph layout, which will be addressed in the fine-tuning step (Figure 4). The first problem is that since the current edges are all straight segments, even if the points are arranged according to the shape, it is difficult for the user to recognize the embedded shape, so the edge that matches the shape should be adjusted to the corresponding curve on the shape. The second is that you can use network alignment, and yes, the overall point arrangement is more regular.
Figure 4: Results before and after fine-tuning
After the above steps, the layout method can better solve a map layout that has both subway map characteristics and can display user-defined shapes (Figure 5).
Figure 5: More Examples
In the user experiment of this paper, the author said that when the embedded graph is simpler and the embedding effect is more obvious, the user can achieve better efficiency in the pathfinding task. In large-scale graph layout, if suitable shapes can be automatically embedded in different blocks of the graph according to the corresponding characteristics, this may also improve the user’s cognition and memory of the graph to a certain extent, which may be a future worthwhile. direction of exploration.
references:
[1] Shape-Guided Mixed Metro Map Layout. Tobias Batik, Soeren Terziadis, Yu-Shuen Wang, Martin Nöllenburg, Hsiang-Yun Wu. 2022. Preprent arXiv 2208.14261.
[2] Go with the Flow: The Direction-Based Fréchet Distance of Polygonal Curves. Mark de Berg, Atlas F. Cook IV. 2011. In Proceeding of 17th International Symposium on Spatial and Temporal Databases.
This article is reprinted from: http://vis.pku.edu.cn/blog/shape-based-mixed-metro-map-layout/
This site is for inclusion only, and the copyright belongs to the original author.