利用图论解决平面图元的关系算法

刘盾

摘要：本文将道路设计中三个图元直线、圆曲线和缓和曲线，利用图论组织起来。解决了方向、桩号和交点的自动识别，实现了交点的动态拖动。

关键词：图论 道路平面设计 平面图元

1图论组织平面数据

道路平面设计中主要有三个元素，直线，圆曲线和缓和曲线[1]。这三个元素都拥有相同的公共属性和自己独特的属性。本文采用图论来组织这三个元素，解决了道路设计中路网和道路相交的问题。

1.1图论概要介绍

图论是一种先进和方便的理论，是最接近描述事物本身及事物之间关系的理论方法。图论中有两个基本构成元素：节点和边。节点是图论中的元素，而边依赖与点存在，边用于连接两个有关系的节点。而通常边分为有方向和没有方向两种，边的这种性质将图分为两种有向图和无向图。

节点是图论中的两个基本要素之一。在描述事物关系中，节点通常用于描述事物本身。节点自身可以加上各种属性。所以在各种数据结构的表达方式中图论是最为方便的。

边是图论的另一个基本要素。在描述事物关系中，边通常用于描述事物与事物之间的关系。一般的数据结构，比如链表、数组之类，对于事物之间的关系不太好表示。

总的来说，图论作为一种适用最为广泛和灵活的理论，是用于描述现实世界实体的较为贴切的数学模型。在道路平面设计中，图论正好用于组织三个平面的基本图元，来表示道路交叉，以及更复杂的路网模型。

1.2平面图元的图论实现

道路平面设计中主要有三个元素，直线，圆曲线和缓和曲线[2]。這三个元素都拥有相同的公共属性和自己独特的属性。在建模的时候，更具三个图元的相通的地方，可以建立统一的公共属性[3]。在图论中用节点来对应表示这三个图元的起点和终点，用边来表示这三个图元。

关于图论这个数据结构的具体实现。在各个语言中都已经有较为成熟的解决方案。本文主要采用C#来做主要的编程语言，所以不能采用上面讲述到的BGL库，采用另一个开源库Quick Graph。将平面的三个图元作为图论中的边，将这些图元的起点和终点作为图论中的节点。

每个图元都具有起点和终点两个属性。这两个属性定义为图论中的点。图元的本身和图元自带的其他桩号方向类型的数据定义为图论中的边。因为图论中每个节点可以和多个边相连接，所以利用图论就可以处理道路相交和路网的情况。

2基于图论组织平面图元

图论作为一个强大的理论工具用于道路设计中的平面图元的组织，具有很好的适应性。当前处理平面图元的方法，采用的是不灵活、速度慢、适用范围狭窄的链表的理论。链表方法的缺点很多导致道路设计关于平面图元的处理非常的被动和臃肿[4]。

采用链表来组织平面图元的原因，可能是因为着眼于一条路。采用链表的线性结构，来保存平面图元的信息，有很多的缺点。首先，链表是一个线性结构，并不能或者说很难表示一个路与其他道路相交的情况。另外由于链表的限制，道路的数据变得非常臃肿，道路的设计方法变得单一。采用链表这个数据结构，那么道路必须按顺序依次设计，使得设计的方法受到了局限。

在涉及到道路与道路相交的交叉口时，链表并不能表示这种情况。使得有关系的两条道路无法建立联系。这样的结果就是导致人工来处理相交的点的高程等一系列问题。

2.1平面图元方向的智能识别

在图论中有一种特殊的图，就是有向图。有向图的定义很简单，连接点与点之间的边有一个特殊的属性：方向。根据方向，讲点与边的关系细化。对于一个点P，连接它的边有两种，出边和入边。出边就是边的方向是从点P出发到另一个点。同样，入边就是边的方向从另一个点出发回到点P。

在这里假设在一条道路中不会出现分叉和交汇，也不会出现循环。在道路设计中，平面中线通常是由各个平面图元组成而成的。根据平面图元的属性，可以判断平面图元属于哪条道路。

根据上面的方法，即可智能判断和修正一条道路中出现方向错误的图元。首先，要求手动点选道路上的某一个图元。程序读出该图元的方向并显示出来。询问方向是否正确。用户选择是或者否，根据用户的反馈。程序读取跟该图元起点相连接的图元，检查道路名称跟选中图元一样的平面图元，检查该图元的方向。

在传统的软件设计中，由于采用的是链式结构，并不能存储支路的情况，对于较为复杂的路网更是无能为力。通常传统程序采用一根线的形式来组织数据，不方便修改更新，对于相交道路也没有办法处理。

而采用图论的知识，可以读取所有相交的情况，根据路名的不同加以分辨。在用户只用指定一个图元的方向的情况下，就可以识别整条道路的所有方向，速度快且方便。

2.2平面图元桩号的智能识别

平面设计中首先是各个基本图元的设计，其次将这些图元连成一个整体，构成平面路网，将数据用图论的方式加以保存。第一个要处理的是平面设计中路网的方向的处理。

桩号的初始化处理采用图论的知识加以处理显得较为简单。首先，要求用户选定平面中的任意图元，设定其桩号。然后程序会根据图元所在的位置和其他图元的关系，进行上游和下游的搜索来一个个的进行桩号的初始化。对于每个平面图元首先要读取图元的长度属性，根据长度属性计算桩号。

2.3平面图元交点的智能识别与拖动

通过图元法来构建一个平面道路，优点是要求十分松散，用户自主性大，可不按顺序设计平面道路，设计比较自由。缺点是程序需要判断的方面较多。需要程序自动计算交点的坐标等等。

2.3.1交点的处理判断

计算交点的坐标，较为复杂，涉及到自动识别图元，图元顺序，图元的偏转方向等。

1.保证道路的方向已经自动识别过了。

2.从起点开始，判断起点的图元。

3.图元若是直线，记录直线所在的向量。若图元不是直线，那么记录图元的起点切线方向所在的向量。设置偏转方向变量为0。偏转方向向量为1表示左偏，为-1表示右偏，为0表示为初始值，还没有确定偏转的方向。

4.往后面开始遍历。

5.（1）遇到直线图元，则计算此直线图元和先前向量的交点，若有交点则表示计算交点过程结束，程序回到第三步，循环求取交点。

（2）若遇到不是直线，那么检查其偏转方向，若偏转向量为0则将偏转向量赋值，程序回到第四步。若偏转向量不为0，检查偏转向量的表示的偏转方向和当前图元的偏转方向是否一致。若一致，则程序回到第四步。若不一致，计算第三步保存的向量和现图元终点切线的交点，这时求交点结束程序回到第三步。

（3）若此为最后一个图元，计算图元终点的切线向量和第三步求得的向量的交点。程序结束。

（4）图元的终点的向量和第三步求得的向量的偏轉角度已经大于180度，则计算此图元的终点的切线向量和第三步求得的向量的交点。

2.3.2自动识别交点后的图形的动态拖动

动态拖动功能，能大大节约设计人员的设计时间，使得设计工作从以前缓慢的输入数据不断生成图形来试错，一举变成简单的鼠标拖动设计，设计完毕自动给出设计参数的灵活多变的设计模式。对于具体的设计工作中，除了动态拖动之外，也能在拖动中，锁定某个参数，从而得到更好的设计结果。

下面以缓和曲线的基本型举例，说明拖动交点，动态设计的算法。基本型的构成元素是缓和曲线中最基本的也是最普遍的。基本型的构成是：直线1、缓和曲线1、圆曲线、缓和曲线2和直线2动态拖动基本型缓和曲线算法如下：

1.用鼠标点选交点。根据点选的坐标，搜索到交点。

2.根据交点，从图中搜索交点对应的道路的元素：直线1、缓和曲线1、圆曲线、缓和曲线2和直线2。

3.根据要求，读出各段平面图元的参数。直线1的两个端点，缓和曲线1的A值A1，圆曲线的半径R，缓和曲线2的A值A2和直线2的两个端点。

4.根据先前的基本型的计算模块，重新计算基本型的各个图元的形状和位置，并绘制出来，实现动态拖动的效果。

参考文献：

[1]卢彭真. 道路中心线勘测CAD编程的方法. 云南交通科技， 2000（3）： 第55-57页.

[2]杨东援，朱照宏. 关于路线CAD系统中平面线形模型的研究. 华东公路， 1991（4）： 第36-40页.

[3]李全信. 线路中线坐标计算的通用数学模型. 勘察科学技术， 2001（5）： 第43-47页.

[4]万年良. 市政道路线CAD系统的开发与实现. 黑龙江科技信息， 2008（29）： 第41页.

（作者单位：武汉市政工程设计研究院有限责任公司）