随着城市经济的发展，城市交通越来越发达，道路也越来越错综复杂。人们在日常生活中需要自驾、公交换乘、地铁换乘等，寻找一条最佳线路显得耗时耗力。这些实际生活中的问题也促使一批的研究者们对道路路网的简单易读性进行深入的研究，来帮助用户从实际交通线路图中快速寻找到自己需要到达目的地的路线，并将其映射到实际的地理地图上。如Kopf等人^[1]提出单目的地地图的自动生成方法，Birsak等人^[2]使用细节分镜头实现地图的可视化。而日常生活中，由于城市线路的复杂交错及人脑有限的记忆力，使得用户尤其是非本地用户记忆不了太多的线路及方向。而且，每个城市都有自己的线路特点，没有规律可循。为了改善用户的视觉体验，需要使用一种归一化的布局方式将这些线路按某种规律进行布局。

1933年Harry Beck (http://en.wikipedia.org/wiki/HarryBeck)手工绘制的伦敦地铁线路图，将线路方向规定在了水平、竖直和斜45°倍数方向上。自此，这种基于约束规则的线路变形方法被视为地铁线路的标准可视化方法并沿用至今。但这种技术也只是应用在了线路简单的地铁线路布局方面，而在其他稍微复杂线路布局中的应用比较少见。为便于用户直观使用线路图，提出一种基于约束规则的线路布局方法。

线路变形问题一直是信息可视化研究的热点问题之一，而基于规则的线路变形就属于其中的一种。在一些可视化元素较多，线路走向杂乱无章的图中，为了能避免线路带来的视觉混乱干扰，而进行的一系列的、满足某种约束规则的变形过程称之为基于规则的线路变形^[3]。这些规则可以是约定俗成的常识性标准，也可以是根据用户自定义的规则。

最早的基于规则的线路变形是Harry Beck的手工地铁线路图。这种方式的线路变形布局得到了广泛的应用，但纯手工绘制的方式也浪费大量的时间与人力。Barkowsky等人^[4]是第1个尝试自动生成地铁线路布局的人，他使用离散曲线演化方法，即一个多边形线简化算法，应用到了德国汉堡市的地铁系统中。虽然实现了自动生成布局的算法，但在线路拥挤的市中心，并没有考虑增加站点的间隔距离，导致市中心站点分布过于密集。而且，没有考虑站点重叠的问题。Hong等人^[5-6]在地铁线路自动布局中使用了美学标准。在弹簧算法的基础上使用了5种不同的处理方式进行自动布局，而且还将边的权重考虑在内，线路的方向也限制在了水平，竖直与斜角45°上。但是有标签遮挡线路的情况。Nöllenburg与 Wolff ^[7-8]使用的混合整数程序法(MIP)给地铁地图规定了软约束与硬约束。MIP算法总能找到符合硬约束的画图的路径，并进行一系列与软约束一致的优化，最后也避免了局部最优的问题。但是，运行的速度太慢，处理时间有时会长达数个小时。Stott等人^[9]用基于爬山法的多目标优化法来绘制地铁线路地图。每个初始化图布局中，都有5个度量的准则，他们的迭代过程是以原始图中嵌入的整数网格开始的，并给出了一个启发式的解决局部最优的办法。其最大的特点就是站点标签与线路是同时布局的，这样有效避免了标签遮挡线路的情况。Wang等人^[10]用高斯牛顿方法优化线路来解决小屏幕显示问题，其中还使用了鱼眼的变形方法。这种整体布局线路的呈现形式会随用户选择的路径发生变化，即随着每次选择路径的不同，呈现出的整体布局也不同，这些布局看上去各不相同，很难发现他们描述的是同一个线路。Kieffer等人^[11]将基于规则的变形方法用到了系统生物学图形符号方面，并将不同的类网格技术进行对比分析，其中还加入了交互的功能。罗振珊等人^[12]将基于规则的方法应用到了寻找多目的地地图。首先，定义一组衡量布局质量的约束规则，然后，采用因子图方法将定义的每条规则编码成因子，并对由因子图构建的目标函数进行采样得到符合约束规则的多目的地地图。

综合以上方法，提出一种新的基于约束规则的算法，有效避免了现实中城市道路网的复杂性容易对人产生视觉干扰的缺点，使用户可快速定位目的地，并应用到了合肥市交通线路图中。

基于规则的变形算法关键是变形中所遵循的规则，而在线路变形的过程中，最重要的一点就是必须保持线路的拓扑信息不被改变。为了统一描述，通过表达式G={V,E}来表示线路图，V是点的集合即$V = \{ {v_0},{v_1},\cdots {v_n}\} $，n是图中的点的数量，E是边的集合，$E = \{ {e_1},{e_2},\cdots {e_m}\} $，m是图中的边的数量。

每个规则用一个N_i(i=1,2,3…)表示，则布局中所遵循的所有约束规则及其详细描述如下：

1)夹角规则(N₁)。为了使多条线交叉时更容易辨认路线，边与边的夹角应设置为最大。设定夹角的取值为0°、45°、90°等(即水平、竖直和他们之间连线斜45°方向)，如图 1所示。

$ {N_1} = \sum\limits_{\{ u,v\} \in E} {\left| {\sin 4\left( {{{\tan }^{ - 1}}\frac{{{y_u} - {y_v}}}{{{x_u} - {x_v}}}} \right)} \right|} $

(1)

式中，{u,v}是点集合V中的两个点，并且u-v是集合E中的边。y_u与y_v分别是坐标系中两个点的纵坐标，x_u与x_v分别是其横坐标。

2)边长度规则(N₂)。为了保证城市中每条线的长度与整体地图协调，不能有太长的边，即各条线路长度近似相等。且不能有超过屏幕显示区域部分的点及线。

$ {N_2} = \alpha \left| {\frac{{\left| {{e_1}} \right| + \left| {{e_2}} \right| + \cdots + \left| {{e_m}} \right|}}{m}} \right| $

(2)

式中，|e_i|,i=1,2,…,m表示每条边的长度，α表示一条线路中线段的数量，即每一条路都要近似的为线段平均长度的倍数。当边长度规则和其他规则冲突时，以其他规则为准。

3)相对位置规则(N₃)。要保证布局中点的相对位置与初始布局中的相对位置一致。例如：点a在初始布局中在点b的北方，则新布局中点a依然在点b的北方，或者是同一条线上，不能变到点b的其他方向。

$ {x_u} > {x_v},{y_u} > {y_v} \to {x_u}' \ge {x_v}',{y_u} \ge {y_v}' $

$ {N_3} = \sum\limits_{{v_i}' \in V'} {{{\left| {{v_i}' - {v_i}} \right|}^2}} $

(3)

式中，x_u，x_v，y_u，y_v表示原始布局中的点(x_u，y_u)，(x_v，y_v)的坐标位置，而变换后点的位置用x′_u，x′_v，y′_u，y′_v表示，v_i表示原始布局中的点，v′_i表示变换后的点。图 2是一个违背相对位置规则的一个例子。但是当相对位置规则和其他规则冲突时，相对位置可以发生改变，但是不能出现大的逻辑错误。当与边长度规则冲突时，以相对位置规则为准。

4)不重叠规则(N₄)。点移动的过程中不能丢失原有的交叉点，边移动的过程中也不能与其他边产生新的交叉点，更不能出现边移动到其他的点上面的情况。几种常见错误情况见图 3。

5)边缘排序规则(N₅)。保存点周围的边(道路)的顺序。记录图中要移动的点的所有邻居结点，以及边的顺时针顺序，保证新旧布局中的边顺序不变。

6)框内规则(N₆)。点在变形的过程中始终在屏幕显示区域内部。框即屏幕显示区域，是要显示这个线路图的范围。

$ \begin{array}{l} {x_{\min }} < x{'_u} < {x_{\max }}\\ {y_{\min }} < y{'_u} < {y_{\max }} \end{array} $

式中，x′_u，y′_u为变形后点u的新位置，x_min，x_max，y_min，y_max分别为显示区域的横坐标的最小值、最大值，纵坐标的最小值、最大值。

需要特别说明的是，为了更容易分辨出各种不同的道路，将每条路径设置为不同颜色。每种颜色可以重复使用，但是相邻的两条线尽量不使用同一种颜色，有相交的两条线路一定不使用同一种颜色。

7)标签非歧义性规则(N₇)。标签的标定，要一眼能看出它代表的是哪个位置。有些标签的放置具有二义性，使用户不知道他表示的是哪个点。因此，要避免出现这种误导人的标签。

标签布局跟前面的线路布局一样，也是电子类地图的重要内容之一，其位置的选择是否恰当、标注是否准确、最终效果是否美观，都将直接影响到地图的易读性。若是在线路布局完成后，不进行标签的标注，那么所有的线路不可能传达给用户准确的信息。

地图标注问题，通常分为3类：点状要素的标注、线状要素的标注、面状要素的标注^[14]。本文的标签，主要是标注关键点的，即特指点状要素的标注。点的标签有8个可选位置，其可放位置如图 4所示。

线路数据中，并不是所有记录点数据都是有价值的。为了高效地实现目标布局，需要删除冗余点并插入缺失关键点。以提取后的道路拓扑信息与初始布局道路信息的拓扑最大近似为目标，将初始道路布局中，交叉口以及道路斜率变化较大的点，作为关键点存储起来。

1)将道路中的交叉路口作为关键点。无论是三叉路口、十字路口还是其他路口，只要是有不同道路相交的情况，都将其看成关键点。以图 5(a)中的合肥市北二环某段路为例，其中有与蒙城北路、阜阳北路与淮南路的交叉口，于是插入A、B、D点，插入点后的示意图如图 5(b)所示。

2)线路斜率变化较大者作为关键点。根据实际道路走向情况，在已有关键点之间依据道路的斜率变化情况进行插值，如图 5(b)中的C点。如果没有插入C点，则重新布局后B与D点有可能在一条直线上。而插入C点，则直线BC与CD有可能呈45°夹角，这样更接近原始图的走向。

求解斜率变化最大点常用的方法是基于弦长的相对曲率计算，即计算具有相同采样密度采样点到弦的距离来近似表示每一个采样点处的相对曲率，如图 6(a)所示。这种方法对于采样的精度和用户的绘制稳定性要求比较高，采样的误差或用户的绘制抖动会对曲率的计算产生很大影响。

为降低相对曲率计算对采样及其误差的敏感性，采用基于窗口的相对曲率计算方法，如图 6(b)所示。基本原理是：对于曲率较大的采样点p_i，对其附近的邻居点${p_{i - k}},\cdots {p_{i - 1}},\cdots {p_{i + k}}$到直线段${L_{i - k,i + k}}$的垂直距离$Dis({p_j},{L_{i - k,i + k}})$进行求和再除以${L_{i - k,i + k}}$的长度可以非常好的放大相对曲率的大小程度。即

$ \rho ({p_i},k) = \frac{{\sum\limits_{j = i - k}^{i + k} {Dis({p_j},{L_{i - k,i + k}})} }}{{Len({L_{i - k,i + k}})}} $

(4)

式中，${{L_{i - k,i + k}}}$表示连接p_i-k，p_i+k两点的直线段；${Dis({p_j},{L_{i - k,i + k}})}$表示点p_j到直线段${{L_{i - k,i + k}}}$的垂直距离；${Len({L_{i - k,i + k}})}$表示直线段${{L_{i - k,i + k}}}$的长度。

相对曲率可以正确、有效地反应所在采样点的实际曲率大小，且对噪声不敏感，个别采样点的抖动和误差不会对曲率的计算结果产生明显影响。

约束规则中的夹角规则、边长度规则及不重叠规则可通过力导向算法来实现：将每个点都看成一个带有能量的粒子，距离较近时斥力起主要作用，距离较远时引力起主要作用。当引力斥力达到平衡时即为稳定状态。

求某个点与其他点的作用力，必须先知道这个点与其他所有点之间的欧氏距离，可按宽度优先搜索算法遍历出图中所有的点。点p_j、p_i的欧氏距离表示为

$ \left\| {{p_i} - {p_j}} \right\| = \sqrt {{{({y_j} - {y_i})}^2} + {{({x_j} - {x_i})}^2}} $

(5)

力导向算法示意图如图 7所示。

单个点与其他所有点之间的引力和为

$ F_i^a = \sum\limits_{j \in N} {k\left\| {{p_i} - {p_j}} \right\|} $

(6)

单个点与其他所有点之间的斥力和为

$ F_i^r = \sum\limits_{j \in N} {\frac{r}{{\left\| {{p_i} - {p_j}} \right\|}}} $

(7)

式中，k，r分别为引力系数与斥力系数，在某段距离时(这个距离即为自己定义的符合边长规则中的长度)若引力斥力达到平衡，则其关系为

$ k = \frac{r}{{{{\left\| {{p_j} - {p_i}} \right\|}^2}}} $

(8)

根据引力与斥力的关系，可得到点移动的方向。由于引力、斥力是根据距离计算的，则保证了边与边的距离近似相等；又由于斥力的作用，保证了点的不重叠规则。

每次迭代点p_i的x，y坐标需要移动的距离分别为Δx_i、Δy_i，则其求解方法分别为

$ \left\{ {\begin{array}{*{20}{c}} {\Delta {x_i} = \sum\limits_{j \in N} {F_i^a \times \frac{{{x_j} - {x_i}}}{{\left\| {{p_j} - {p_i}} \right\|}}} }\\ {\Delta {y_i} = \sum\limits_{j \in N} {F_i^r \times \frac{{{y_j} - {y_i}}}{{\left\| {{p_j} - {p_i}} \right\|}}} } \end{array}} \right. $

(9)

基于规则的线路变形一般是对多目标函数进行优化的过程。多目标优化的算法在线路布局方面的使用非常方便，它使布局结果更加接近目标值，以达到更好的效果。爬山优化算法^[8]是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间集合中选择一个最优解作为当前解，直到达到一个局部最优解。

本文中的多目标，为以上几个规则的实现，具体优化过程为

$ RN = \sum\limits_{k = 1}^7 {{w_k}{N_k}} $

(10)

式中，RN为权重总和，w_k为对应约束规则N_k的权重。

爬山算法实现简单，基于算法复杂度及时间的考虑，本文线路布局中采用爬山算法。整个算法的流程伪代码如下：

/*下列G表示一个已知线路图，V表示图中所有顶点集合，E表示图中所有边集合，L表示所有标签集合*/

G=(V,E,L)

filtrateStation(V,E)

StationCriteria=false;

while(StationCriteria!=true)

   for v∈V do

   if(!snapStation(v))

       moveStation(v)

   end if

   end for

   for e∈E do

     if(!LengthCriteria(e)!AngleCriteria(e₁,e₂))

       moveStation(v)

   end if

   end for

   if(!moveStation(v))

       StationCriteria=true

   end if

   end while

   for l∈L do

       m_L0=calcLabelCriteria(L)

       m_L=findLowestLabelCriteria(L)

       if m_L<m_L0 then

           moveLabel(l)

           end if

   end for

   m_T=calcStationCriteria(V)+calcLabelCriteria(L)

   if m_T>=m_T0 then

   exit

   else

   m_T0=m_T

   end if

   end while

以合肥市道路网为例，用Java开发语言进行实验验证。首先，提取初始图中的交叉路口及拐弯处的点作为关键点，然后再根据这些关键点进行布局。其具体的流程如图 8所示。

分别以合肥市包河区内的道路信息及合肥市一环以内的主要道路信息的布局情况为例进行说明。根据线路范围进行分类的，其各个范围内的线路属性如表 1所示。

由于道路交叉口太多，为了在布局中便于认清楚每条路线的走向，故采用每条路用不同颜色进行区分。没有任何交集且非相邻的两条线路的颜色可以相同。根据图 8所示的算法，对以上两个范围内的线路进行布局，图 9是包河区内线路处理情况。

合肥市一环内的道路信息数据，来源于百度地图。由于其只显示主干道，非主干道的信息看不出，所以相对包河区内的线路图，其规模也只是稍微复杂了一点点。后者明显的特征是其有两个环路及更多的三叉路口(其实外环中的三叉路口只是提取点时没有提取环外的点而造成的，百度地图中大多是四叉口)。根据本文算法进行变形，其变形前后的对比如图 10所示。

从布局后的图 10中可以看出，本文方法在多个环形路中也取得了比较好的效果。以上两个例子中，可以明显感受到线路规整后的舒适感，而且解决了道路方向不统一，布局摆放杂乱无规律所带来的问题，使得用户能快速便捷的找出所走路段。但是由于其线路的调整，故布局后的线路长度无法表示其现实中实际的距离。不过，这点对于用户来说，其时间影响不是很大。

与此同时，利用本文方法对墨西哥城的地铁线路进行布局，并与Wang等人^[10]的Focus+Context布局方法和Stott等人^[9]的Multicriteria Optimization布局方法进行对比。结果如图 11所示。本文结果只是为了展示线路变形，所以舍弃了一些站点没有作为关键点，同时也没有添加标签。

通过图 11的对比发现，Focus+Context方法针对用户特定区域进行更显著的展示，弱化了显示其他线路。而Multicriteria Optimization布局方法则是针对多种布局规则进行多重判据最优化。本文方法结果规整，视觉效果良好,用户可以更加迅速地实现规划线路与换乘或者定位等。

通过一个用户使用测试来验证本文方法的有效性。为了保证实验的客观性，选中20位不是合肥本地的合肥工业大学学生(10位男性，10位女性)来参与测试。20位同学分为A、B两个小组(每组各5位男性和5位女性)，其中A组给定每个用户图 10(a)的图像，B组给定每个用户图 10(b)的图像。给定两组用户相同的出发地和目的地，让其在图中标注出规划线路 ，并记录每次所需时间。经过几组测试后，结果如表 2所示。根据实验结果可以看出根据本文方法可以使用户更加迅速地定位并做出路线规划。

由于基于约束规则的方法还没有在城市交通道路中应用，本文同时采用类似文献[15]的主观评价法验证算法的有效性。在合肥工业大学校园内随机选取60人发放调查问卷，分别从线路的易读性、美观性、实用性、方便性等几个方面展开调查，得出如图 12的调查结果。其中在实用性方面有68.3%的人认为具有实际使用意义。而这几项综合起来，平均有69.6%的用户觉得使用方便，比其他普通地图更能快速地锁定目标，有效地节省了时间。

提出的基于约束规则下的线路变形技术，要经过关键点提取、线路约束规则布局、标签布局等一系列的步骤。首先介绍了关键点提取的两种方法，一种是交叉路口点、另一种是线路走向斜率变化较大的点。然后介绍了线路布局中要遵守的几个规则，每个规则的目的是什么，最后介绍了标签的标定及最后的算法流程。这一系列步骤的最终目的是将城市中地铁线路的实际道路走向或城市公路线路道路中的实际走向布局转化为只有横平、竖直和斜角45°倍数方向的线路。

对于规模更大，线路更复杂的情况，由于本文将线路方向约束在了45°的倍数上，可能会出现增加交叉线路的数目，而交叉路口较多的地方还可能出现线路重叠的情况，。未来工作，对于这种情况可采用分层布局的形式进行布局，分而治之。即先布局一级道路，在一级道路布局好之后，再布局二级道路，依次类推。同时针对细节的可视化展示，目前只是采用了简单的交互，利用鼠标与键盘对关键点和线的长度进行一些控制，之后考虑采用路强等人^[16]的一种基于Multi-focus+context的鱼眼显示技术，这也是未来工作的一个重点。