复合流图
论文信息:Cornel, D., Konev, A., Sadransky, B., Horváth, Z., Brambilla, A., Viola, I., & Waser, J. (2016). Composite Flow Maps. Computer Graphics Forum, 35(3). http://doi.org/10.1111/cgf.12922
流图(Flow maps)编码成带箭头的线段,线段之间顺序连接一些节点,线段的宽度表示流的度量。流图常用于运动对象在不同位置间的移动过程。例如,物流系统中货物的运输过程;紧急事故发生时,人群的逃生过程;洪水灾难发生时,潮流的变化过程等。为了有效地提供决策,在这些应用中通常需要同时观察多种流的特性,如不同的运动方向、不同的运输材料、从不同房间逃生的人群、可能的形势(“最坏”、“至少”、“期望”)等。在不同的应用场景中,决策者可能需要掌握流的总体趋势,或者需要了解流的局部详细特征。
在这篇论文中,作者提出了一种从大量运动数据中自动生成流图的技术。该技术能够在一个可视化视图中同时呈现多种不同的流的属性,如不同的材质、方向、流的起点和终点。此项技术的基础是根据应用的语义和地理空间上下文把空间分割成多个区域。分割后,计算相邻区域之间的流属性数据。生成的流图可以在不同地图层级间变化,而且能够保留重要的细节特征,如图1(点击图片查看大图,下同)所示。
流图的生成过程
第一步首先对兴趣空间将其分割成一维(图2上部分)或二维(图2下部分)区域。随后计算所有相邻区域间的边界流(border flows)的各项参数(图2b)。边界流通过计算从一个区域到另一个区域的流量值的总和来获取。而判断两个区域是否相邻的方法是一维上两个区域是否共享同一个端点,二维上是否共享多边形的边。通过分割和计算,区域及其连接关系可以通过抽象的区域图来表示(图2c)。最后将抽象的空间关系图映射到地图上(图2d)。
基于语义的区域自动分割
论文并没有分析原始数据中材质的流动来分割区域,而是根据地理空间上下文来分割。作者解释道,随意的分割可能会掩盖用户需要的重要信息。自动分割算法在连接处分割,并且在连接处增加一个空间缓冲来表示连接关系,如街道连接处用直径9.9米的圆形缓冲区,在下水道连接处用直径2米的缓冲区。当且仅当相邻区域之间存在材质流动时,两个区域相互连接,相邻区域间的流量则根据单位时间内的材质流动来计算。
区域连接图的空间映射
将抽象的区域连接图映射到地图上,取决于抽象区域的表示。如果抽象区域是街道则用连线表示,否则用点集表示(单个点表示小区域,多个点的组合表示大区域)。图3a为抽象区域图,图3b为抽象区域转换成街道或点集之后的表示。图3c是根据抽象区域图中连接关系连接之后的表示。连线根据应用的不同将重新采样(物流100米、水:10米、人群疏散:7米),重新采样的目的是为了让线中的顶点更均匀,并且方便后续的(图3d)。经过力引导算法,图中在给定半径r内的顶点合并成为新的顶点。力引导算法与Debiasi的论文“Supervised force directed algorithm for the generation of flow maps”相似,不同之处在于论文中的算法并不需要流是从根节点出发流向叶节点(图3e)。此外,论文中流具有双向特性。在交汇点处,为了避免出现线的重叠,论文设计了圆形图标(仅对三条以上线相交时使用),圆的半径则由连接线的宽度决定。通过在线条上编码颜色来标明流的状态特性,例如在图1的最右边视图中,颜色用来表示人群在该位置停留的时间。
实验结果与评测
作者在三个应用中分别使用了该项自动流图生成技术。第一个应用是描述防止洪水筑建大坝的物资运输路线。为了对物资运输路线进行规划,专家需要了解多个时间相关的全局流视图。实际的运输路线由启发式算法生成。第二个应用是规划下水道的入口。下水道必须要保证在很大水流量时也足够让水流走,为此专家需要了解局部的流特性。第三个应用则与办公室的紧急疏导相关,多个办公室由走廊连接到紧急出口。办公室门的布置以及房间人数的规划需要考虑各种可能的疏散过程,人群要尽快离开而不能堵塞通道。