无重叠交叉的配电网单线图自动生成算法.doc

无重叠交叉的配电网单线图自动生成算法
陈勇,邓其军，周洪
(武汉大学自动化系,湖北武汉430072)

摘要：以设备的拓扑连接关系为基础，将配电馈线的地理接线图自动转换成单线图时，存在的最大问题就是线和图标的重叠交叉的消除。基于面向图形对象的单线图绘制工具，提出了一种通过寻找最佳绘制方向来尽可能避免重叠交叉的新方法。当需要向某个方向绘制一个图标时，先检测按此方向绘制是否会与已经存在的对象发生重叠交叉。如果有重叠交叉，则依次尝试向其它两个垂直方向绘制。如果三个方向都无法绘制，则通过局部图幅扩展算法，对图幅进行扩展，得到至少一个图标的位置后按照原方向进行绘制。结合实例详细描述了所提出方法的算法步骤，结果表明该方法能尽可能避免线和图标的重叠交叉，保证自动生成的单线图布局美观合理，并且在城市配电网中得到了成功的应用。
关键词：配电网；地理信息系统；单线图；自动生成；拓扑；GDI+；重叠交叉

引言
在基于地理信息的配电网管理系统中，馈线的地理图和单线图是配电网运行管理的两类核心资料。目前，在大多数的类似系统[1~3]中，设备的地理图是在地理信息系统GIS（GeographicInformationSystem）上绘制完成的(包括设备之间的连接关系)；而电气单线图则是在CAD图上通过手工绘制来完成的。两者之间存在数据、拓扑不一致的隐患。配电馈线的地理图到单线图的自动转换，能够大大减少配电网管理的数据维护工作量，避免数据多头配置，确保数据的一致性[4]。
以设备在地理图上的拓扑连接关系为基础，实现单线图的自动绘制问题，部分文献已经作过研究[5~15]，其中最重要的问题，是如何解决线和图标的重叠与交叉问题。
文献[7]和文献[8]中将一个辐射状的配电网络拓扑结构用图论中的树表示，提出生成辐射状配电馈线电气接线图的方法。文献[9,10]提出的方法是将各电气设备分级，然后把偶数级水平放置，奇数级垂直放置。若产生交叉或重叠则采取水平或垂直一维局部拉伸平移的方法来消除。文献[11,12]介绍了采用罚函数法进行输电网电线图的自动生成算法：求得单线图节点初始化布局，然后再对初始化布局进行进一步优化。文献[13]提出了基于树的配电网模型：模型以网络动态拓扑关系为出发点，对各个用电设备按供电线路分类，依据距离电源点的远近进行分层处理，画电气接线图时，按层次排放和元素数量均衡排列。
本文提出了一种通过寻找最佳绘制方向来尽可能避免重叠交叉的新方法。该方法在一种基于GDI+技术的绘制工具[15]中得到了实现。
自动绘图的思路
馈线地理图向单线图的自动转换可按如下步骤进行：
(1)以馈线出线开关为起点，遍历所有连接到的设备(到联络开发、配变或线路末梢为止)形成一棵树；且以层次最深的叶子结点到馈线开关的线所经过的所有点组成的线，作为0级主干。
(2)水平向右绘制第0级主干，并记下该主干上所有接有分支的结点，放入BranchNodeList列表中；
(3)对BranchNodeList中的第一个对象，找出从其接出的每个后续结点，并从BranchNodeList中删除第一个对象；
(4)以第(3)步中找到的每个后续结点为每个分支的第二点(第一点为第(3)步中删除的结点)，开始绘制相应分支。在绘制分支时，如果被绘制的结点接出有分支，则加入BranchNodeList末尾；
(5)重复执行第(3)步和第(4)步，直到BranchNodeList中无对象；
(6)自动缩放至全屏幕且居中展示。
上述步骤中，重点在第(4)步中，如何为每一个将要绘制的结点，找到合适的位置。本文的处理方法是当需要向某个方向绘制一个图标时，先检测向此方向绘制是否会与已经存在的对象发生重叠交叉。如果会发生重叠交叉，则依次尝试向其它两个方向绘制。如果三个方向都无法绘制，则对图幅进行局部扩展，得到至少一个图标的位置再进行绘制。
最佳绘制方向的寻找算法
2.1 用于表达已绘制对象所占位置的虚拟矩形
单线图绘制的最基本要求，是不能有重叠交叉。同时，线条之间、图标之间以及两者之间，不能太接近，否则看起来就象重叠交叉一样。因此，在判断是会发生重叠交叉时，不能直接以已经绘制的线或图标来判断，而是应该在已经绘制好的线和图标所占的区域的基础上，作适当的扩展。同时为减少对象数量，将每一折线段上所有的线和图标所占的位置，用一个虚拟的矩形来处理，如图1所示。其中，Dn表示电气设备，Rn表示虚拟矩形。

图1虚拟矩形示意图
Fig.1Chartofvirtualrectangle
虚拟矩形的数据结构如下所示(本文所有示例代码均使用c#语言)。
StructStructRect
{
DrawObjectbeginObject;
DrawObjectendObject;
stringdirection;
floatrectWid