无重叠交叉的配电网单线图自动生成算法陈勇，邓其军，周洪（武汉大学自动化系，湖北武汉430072）摘要：以设备的拓扑连接关系为基础，将配电馈线的地理接线图自动转换成单线图时，存在的最大问题就是线和图标的重叠交叉的消除。

基于面向图形对象的单线图绘制工具，提出了一种通过寻找最佳绘制方向来尽可能避免重叠交叉的新方法。

当需要向某个方向绘制一个图标时，先检测按此方向绘制是否会与已经存在的对象发生重叠交叉。

如果有重叠交叉，则依次尝试向其他2个垂直方向绘制。

如果3个方向都无法绘制，则通过局部图幅扩展算法对图幅进行扩展，得到至少1个图标的位置后按照原方向进行绘制。

结合实例详细描述了所提出方法的算法步骤。

关键词：配电网；地理信息系统；单线图；自动生成；拓扑；GDI +技术；重叠交叉中图分类号：TM 744文献标识码：A 文章编号：1006－6047（2010）11－0090－04电力自动化设备Electric Power Automation EquipmentVol．30No．11Nov.2010第30卷第11期2010年11月0引言在基于地理信息的配电网管理系统中，馈线的地理图和单线图是配电网运行管理的2类核心资料。

目前，在大多数的类似系统［1-3］中，设备的地理图是在地理信息系统GIS （Geographic Information System ）上绘制完成的（包括设备之间的连接关系）；而电气单线图则是在CAD 图上通过手工绘制来完成的。

配电馈线的地理图到单线图的自动转换，能够极大减少配电网管理的数据维护工作量，避免数据多头配置，确保数据的一致性［4］。

以设备在地理图上的拓扑连接关系为基础，实现单线图的自动绘制问题，部分文献已经研究过［5-15］，其中最重要的问题，是如何解决线和图标的重叠与交叉问题。

文献［7］和文献［8］中将一个辐射状的配电网络拓扑结构用图论中的树表示，提出生成辐射状配电馈线电气接线图的方法。

文献［9-10］提出的方法是将各电气设备分级，然后把偶数级水平放置，奇数级垂直放置。

文献［11-12］介绍了采用罚函数法进行输电网电线图的自动生成算法。

文献［13］提出了基于树的配电网模型。

本文提出一种通过寻找最佳绘制方向来尽可能避免重叠交叉的新方法。

该方法在一种基于GDI +技术的绘制工具［15］中得到了实现。

1自动绘图的思路馈线地理图向单线图的自动转换可按6个步骤进行。

a.以馈线出线开关为起点，遍历所有连接到的设备（到联络开关、配变或线路末梢为止）形成一棵树；且以层次最深的叶子结点到馈线开关的线所经过的所有点组成的线，作为0级主干。

b.水平向右绘制第0级主干，并记下该主干上所有接有分支的结点，放入BranchNodeList 列表中。

c.对BranchNodeList 中的第1个对象，找出从其接出的每个后续结点，并从BranchNodeList 中删除第1个对象。

d.以c 步中找到的每个后续结点为每个分支的第2点（第1点为c 步中删除的结点），开始绘制相应分支。

在绘制分支时，如果被绘制的结点接出有分支，则加入BranchNodeList 末尾。

e.重复执行c 步和d 步，直到BranchNodeList 中无对象。

f.自动缩放至全屏幕且居中展示。

上述步骤中，重点在d 步中，即如何为每个将要绘制的结点到合适的位置。

本文的处理方法是当需要向某个方向绘制一个图标时，先检测向此方向绘制是否会与已经存在的对象发生重叠交叉。

如果会发生重叠交叉，则依次尝试向其他2个方向绘制。

如果3个方向都无法绘制，则对图幅进行局部扩展，得到至少1个图标的位置再进行绘制。

2最佳绘制方向的寻找算法2.1用于表达已绘制对象所占位置的虚拟矩形单线图绘制的最基本要求是不能有重叠交叉。

同时，线条之间、图标之间以及两者之间，不能太接近，否则看起来就像重叠交叉一样。

因此，在判断是否会发生重叠交叉时，不能直接以已经绘制的线或图标来判断，而是应该在已经绘制好的线和图标所占的区域的基础上，作适当的扩展。

同时为减少对象数量，将每一折线段上所有的线和图标所占的位收稿日期：2010－03－06；修回日期：2010－05－31结束count1＜count2？开始步骤1根据主干的绘制方向，获得与主干的绘制方向垂直的2个方向direction1、direction2步骤2获得从接出点接出的在direction1和direction2的2个方向上的分支个数count1、count2以direction1作为分支方向会重叠交叉？以direction2作为分支方向会重叠交叉？步骤3以direction1作为分支方向步骤5局部扩展步骤4以direction2作为分支方向YNYYNN图2分支的初始绘制方向判断流程图Fig.2Flowchart of original drawing direction judgment for branch置，用1个虚拟的矩形来处理，如图1所示。

其中，D n 表示电气设备，R n 表示虚拟矩形。

虚拟矩形的数据结构如下所示（本文所有示例代码均使用C #语言）。

Struct StructRect ｛DrawObject beginObject ；DrawObject endObject ；string direction ；float rectWidth ；RectangleF area ；｝其中，DrawObject 是绘图对象，表示画布上的一个图标［11］；beginObject 表示此虚拟矩形的起点对象（D 1、D 4、D 6、D 12）；endObject 表示此矩形对象的终点对象（D 8、D 9、D 13、D 15）；direction 表示矩形的绘制方向（由于单线图要求横平竖直，因此direction 是HL 、HR 、VU 、VD 之一，分别表示水平向左、水平向右、竖直向上、竖直向下）；rectWidth 表示矩形垂直于direction 方向的宽度，取系统所使用的最大图标的长边宽度；area 表示该矩形所占的区域，每当一个分支绘制完毕，绘制方向发生了转折或矩形中的对象发生移动时，就重新计算矩形的area ，如图1中虚线方框所示。

下面说明其计算方法。

通过endObject 的中心点，画1条沿direction 方向的直线；沿beginObject 的包围矩形的垂直于direction 方向的2个边画2条直线；沿endObject 所包围矩形的垂直于direction 方向的2个边画2条直线；这5条直线得到4个交点。

以其中距离最远的2个点作为虚拟矩形的短边中点，短边宽度为rectWidth ，从而得了到虚拟矩形的大小及位置。

在每次采用局部扩展算法消除重叠交叉后，都需要重新计算已绘制对象构成的虚拟矩形的位置。

2.2分支的初始绘制方向的判断分支的绘制方向要与其上级主干垂直，且不能与该主干已经有的分支重叠。

其绘制方向的算法流程如图2所示。

对图2作如下说明。

a.在绘制每一个对象时都将该对象的绘制方向保存在该对象的属性direcion 中。

步骤1中，根据属性direction 中保存的方向，得到与该方向相垂直的2个方向direction1和direction2，direction1表示向上或向左，direction2表示向右或向下。

b.在绘制主干上的每一个分支时，将该分支的绘制方向记录到主干上的接出对象属性vertical1和vertical2中。

根据接出对象的绘制方向direction 不同，分支方向将被增加到不同的属性中，具体情况如表1所示。

其中，HL 、HR 、VU 、VD 分别表示水平向左、水平向右、竖直向上和竖直向下。

而且，接出对象的绘制方向与分支方向必然垂直。

1表示该属性值加1，0则表示该属性值不变。

因此，步骤2中，从主干上接出对象的属性vertical1、vertical2及direction ，可以分析出在direction1和direc -tion2的2个方向上的分支个数count1和count2。

c.步骤5中，如果发生重叠或交叉的情况，则按照2.4节所述方法进行局部扩展。

2.3分支上后续对象的绘制方向的判断为尽量避免重叠与交叉，在绘制分支上的每个后续对象之前，先判断该对象的绘制方向。

其算法流程图如图3所示。

D 1D 3D 2D 4D 5D 6D 7D 8D 10D 11D 12D 13D 14D 15R 1R 2R 3R 4D 9图1虚拟矩形示意图Fig.1Schematic map of virtual rectangle表1分支方向记录表Tab.1List of branch direction方向分支方向vertical1vertical2HL ／HR 向上10HL ／HR 向下01VU ／VD 向左10VU ／VD向右1陈勇，等：无重叠交叉的配电网单线图自动生成算法第11期下面对图3进行说明。

a.利用已绘制对象所构造的虚拟矩形判断以direction 为正要绘制对象的绘制方向是否会重叠交叉：将正要绘制的对象所占的区域与所有已绘制对象所构造的虚拟矩形通过RectangleF.Intersects -With （RectangleF rect ）函数进行比较，函数返回true 表示发生重叠或交叉。

b.步骤2中，direction1方向的绘制空间的计算方法如下：假设存在一个虚拟矩形ViRect ，该矩形以前一个对象在direction1方向上的末端作为起点，以正要绘制对象的绘制方向为虚拟矩形的方向，以系统所使用的最大图标的长边宽度为矩形的宽度，矩形的长度为无穷大。

判断矩形ViRect 是否与所有已绘制对象所构造的虚拟矩形重叠或交叉，并记录重叠交叉的位置。

根据重叠交叉的位置与虚拟矩形ViRect 的起点的距离，计算direction1方向的绘制空间的大小并赋给room1。

direction2方向的绘制空间的计算方法相同。

2.4局部图幅扩展的算法在逐步生成配电网单线图时，难免会发生线条、图标之间的重叠与交叉的现象。

采用局部图幅扩展算法来消除重叠与交叉，具体有2个步骤。

2.4.1步骤1判断局部拉伸平移的方向将发生重叠与交叉的虚拟矩形的方向与正要绘制图标的绘制方向相比较，若两者方向平行，则发生重叠，若两者方向垂直，则发生交叉。

a.两者重叠的情况。

若两者方向为水平方向，且发生重叠的虚拟矩形的纵坐标Y 1小于新绘制图标的纵坐标Y 2，则拉伸平移方向为竖直向上，否则拉伸平移方向为竖直向下；若两者方向为竖直方向，且发生重叠的虚拟矩形的横坐标X 1小于新绘制图标的横坐标X 2，则拉伸平移方向为水平向左，否则拉伸平移方向为水平向右。

b.两者交叉的情况。

正要绘制图标的绘制方向就是拉伸平移的方向。