北京大学可视化暑期学校第二天上午的报告由悉尼大学的Peter Eades教授带来题为《Graph Drawing》的报告。Peter在1984的论文中[1]首次提出了力导向算法的原型，是图布局最经典的绘制算法。在课程中，Peter Eades为了大家介绍了图可视化的相关内容。图可视化中最重要的问题就是图布局。简单来讲，图布局就是给拓扑中的节点赋予坐标，并且在节点间用连线表示拓扑中的连接。什么是一个好的图绘制呢？首先，图绘制的结果必须是忠实（faithfulness）的，即绘制的图能够准确表示原始的数据，但是现在还没有一个正式的规则来评价忠实性；其次，图绘制的结果必须具有可读性（readability），即用户可以准确理解图中的知识信息。好的图布局会避免边交叉，弯曲的边以及节点的重合。
图1. Peter Eades教授介绍平面图的检测算法
首先，Peter介绍了平面图的概念，一个可以在平面展示而没有交叉边的图称为平面图。接下来，Peter介绍了正交画法、网格画法等图绘制方法，基于力导向的图布局算法以及大图的谱布局算法。
正交画法中所有的边均相互平行或相互正交，网格画法中节点均位于网格中的格点上。力导向算法由Peter本人首先提出，是一种物理模拟方法，每个节点是一个粒子，任意两个粒子之间存在静电斥力，节点之间的连边相当于弹簧，存在弹力。节点在会一致受力方向移动，最终所有节点受力为0，或者系统能量最低时，模拟终止，得到了最后的图布局。为了提高大图的计算效率，可以通过四叉树划分的方式，提高斥力的计算效率。
谱布局是力导向算法的一种，通过计算图的拉普拉斯矩阵，将两个较小的非零特征值对应的特征向量组合作为节点的坐标，对图进行布局。该方法易于理解，计算效率高，但是只适合网格状的图。最后Peter介绍了图布局中仍未有效解决的问题，如何计算图布局的忠实度？如何与大图交互？大图中的边交叉影响大吗？同学们就这些问题与Peter进行了热烈的讨论。
下午，来自美国宾夕法尼亚州立大学的张小龙教授介绍了地图可视化以及基于此的意义构建。基于地理信息的可视化方法由来已久。主要针对包含空间特征的数据，此外也有一些工作将信息转化为地图来理解。
图2. 张小龙教授介绍协同式地理分析系统
张教授对地理信息系统（Geographic Information Science, GIS）的历史和现状做出了基本介绍，地理信息系统是为了解决传统地图学中面临的问题，引入动态、交互、图形展示、数据分析等功能。逐渐演变成支持空间数据处理、面向多种设备显示的分析平台。张教授以IEEE可视分析科学技术挑战赛数据及一些参赛系统为例表示地图可视化的有用性。
接着，张教授介绍了他基于地图可视化的协同式意义构建（Sensemaking）的一项工作，该工作支持多位不同领域的专家协同在紧急情况发生时制定应急方案。系统设置私人地图和公用地图。专家们可以利用各自的专业信息在地图上进行分析，并可以通过公有地图将信息分享。该系统提高了协同工作的效率。各自认知提高了形成统一的解决方案的效率。
在介绍完前沿工作之后，张小龙教授介绍了实用的位置服务编程方法。以百度地图API接口为例，张教授提供了大量基础代码示例，从地图基本视图控制、覆盖物添加到对组件的控制都有详细介绍。
之后，张教授对地图可视化的认知基础做出了深入浅出的讲解。感知是人类与生俱来的能力，而认知通常结合了先验知识。张教授列举许多视觉错觉，建议设计应该尽量避免选择丰富颜色来编码量化数据、避免大块颜色填充。此外合理人类视觉特征进行设计将大幅提高可视系统的有用性。
今日的学习从图可视化布局理论到地图可视化及可视分析设计原则。同学们收益匪浅。
参考资料：
[1] Peter Eades. A heuristics for graph drawing. Congr. Numer. 42 (1984) 149-160.
评论关闭。