形状引导的混合地铁图布局方法(Shape-Guided Mixed Metro Map Layout)

在图可视化中,地铁图可视化是一个经典的可视化方法,将图中节点尽量均匀地排布在空间中,同时尽可能保持边的且尽可能保持最终布局的拓扑结构与图节点的原始。 同时,在实际的图布局中,除了要提高图的可读性,有时还需要将一些特定的动机(motif)嵌入到图中,这能提高图布局的艺术效果,也可能可以提升用户对该布局的认知能力。

在论文《Shape-Guided Mixed Metro Map Layout》[1]中,维也纳工业大学的Tobias Batik等人提出了一种结合地铁图布局与形状嵌入的混合布局方法(图1),能够支持在保证将用户定义的形状嵌入最终图布局的同时,将整体图布局以地铁图的标准进行优化。

图1: 结合地铁图标准和心形,生成的图布局

在论文中,作者首先列出了布局方法的设计需求,这一设计需求结合和传统地铁图布局的设计需求和用户定义形状嵌入的需求(图2)。

图2:算法的设计需求

根据这一设计需求,作者提出了“用一部分点和边尽可能明显地表示要嵌入的形状,使得其他的点和边按照地铁图的标准进行布局。” 按照这一方向,作者提出了分为“形状匹配-布局优化-布局微调”的三步的算法流程(图3)。

图3:论文中提出的pipeline

要将形状嵌入到地铁图中,首先就要决定将那些点和边布局成这个嵌入的形状,这也就是整个算法的第一步,形状匹配。在论文中,作者使用了Direction-based Frechet Integral distance[2]来衡量,使用这种方式计算,可以使得匹配具有平移与缩放的不变形,且由于在实际布局中,参与计算的是离散的折线段,所以可以较为简单地使用动态规划解决。

在布局优化中,作者设置了几类能量函数指导优化的方向,能量函数包含以下几种:

  • 形状能量函数:使得与形状匹配的点到形状对应位置的距离,使得这些点尽可能构成嵌入的形状。
  • 边能量函数:每条边与标准边长的差,使得每条边尽可能一样差。
  • 角度能量函数:连着同一个点的角度相邻两条边夹角到标准角度的差,避免出现特别小的夹角。
  • 拓扑结构能量函数:每个点与每个地铁站实际距离的差,使得最终布局和实际地理布局接近。
  • 八线性(octolinear)能量函数:每条边与和其角度最接近的八线性方向的差,使得每条边最终角度尽可能是八线性方向中的一个。

由于初始时难以确定每条边最优的八线性方向是哪一种,所以优化分为了两步,先使用前四种能量函数优化出大致的布局,然后再根据当前的结果确定每条边最相近的八线性方向,再将第五种能量函数加入优化中。

即使经过布局优化,图布局中还存在着一些明显可以改进的地方,这些将在布局微调步骤中解决(图4)。第一个问题是由于当前的边都是直线段,即使将点按照形状进行排布,用户也难以识别出嵌入的形状,所以最后要将与形状匹配的边调整为形状上对应的曲线。第二是可以使用网络对齐,是的整体的点排布更加规整。

图4:微调前后的结果

经过上述步骤,该布局方法就能较好地求解出一个同时具有地铁图特性且能展示用户定义的形状的图布局(图5)。

图5:更多例子

在该论文的用户实验中,作者表示当嵌入的图形较为简单,嵌入效果较为明显时,用户在寻路任务上能够取得更好的效率。在大规模图布局时,如果能在图的不同块区按照相应的特点自动化地嵌入合适的形状,这可能也能在一定程度上提高用户对图的认知与记忆,这可能是一个未来值得探索的方向。

参考文献:

[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.

评论关闭。