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

无重叠交叉的配电网单线图自动生成算法陈 勇, 邓其军，周 洪 (武汉大学 自动化系, 湖北 武汉 430072 )摘要：以设备的拓扑连接关系为基础，将配电馈线的地理接线图自动转换成单线图时，存在的最大问题就是线和图标的重叠交叉的消除。基于面向图形对象的单线图绘制工具，提出了一种通过寻找最佳绘制方向来尽可能避免重叠交叉的新方法。当需要向某个方向绘制一个图标时，先检测按此方向绘制是否会与已经存在的对象发生重叠交叉。如果有重叠交叉，则依次尝试向其它两个垂直方向绘制。如果三个方向都无法绘制，则通过局部图幅扩展算法，对图幅进行扩展，得到至少一个图标的位置后按照原方向进行绘制。结合实例详细描述了所提出方法的算法步骤，结果表明该方法能尽可能避免线和图标的重叠交叉，保证自动生成的单线图布局美观合理，并且在城市配电网中得到了成功的应用。关键词：配电网；地理信息系统；单线图；自动生成；拓扑；GDI+ ；重叠交叉0 引言在基于地理信息的配电网管理系统中，馈线的地理图和单线图是配电网运行管理的两类核心资料。目前，在大多数的类似系统13中，设备的地理图是在地理信息系统GIS（Geographic Information System）上绘制完成的(包括设备之间的连接关系)；而电气单线图则是在CAD图上通过手工绘制来完成的。两者之间存在数据、拓扑不一致的隐患。配电馈线的地理图到单线图的自动转换，能够大大减少配电网管理的数据维护工作量，避免数据多头配置，确保数据的一致性4。以设备在地理图上的拓扑连接关系为基础，实现单线图的自动绘制问题，部分文献已经作过研究515，其中最重要的问题，是如何解决线和图标的重叠与交叉问题。文献7和文献8中将一个辐射状的配电网络拓扑结构用图论中的树表示，提出生成辐射状配电馈线电气接线图的方法。文献9,10提出的方法是将各电气设备分级，然后把偶数级水平放置，奇数级垂直放置。若产生交叉或重叠则采取水平或垂直一维局部拉伸平移的方法来消除。文献11,12介绍了采用罚函数法进行输电网电线图的自动生成算法：求得单线图节点初始化布局，然后再对初始化布局进行进一步优化。文献13提出了基于树的配电网模型：模型以网络动态拓扑关系为出发点，对各个用电设备按供电线路分类，依据距离电源点的远近进行分层处理，画电气接线图时，按层次排放和元素数量均衡排列。本文提出了一种通过寻找最佳绘制方向来尽可能避免重叠交叉的新方法。该方法在一种基于GDI+技术的绘制工具15中得到了实现。1 自动绘图的思路馈线地理图向单线图的自动转换可按如下步骤进行：(1)以馈线出线开关为起点，遍历所有连接到的设备(到联络开发、配变或线路末梢为止)形成一棵树；且以层次最深的叶子结点到馈线开关的线所经过的所有点组成的线，作为0级主干。(2)水平向右绘制第0级主干，并记下该主干上所有接有分支的结点，放入BranchNodeList列表中；(3)对BranchNodeList中的第一个对象，找出从其接出的每个后续结点，并从BranchNodeList中删除第一个对象；(4)以第(3)步中找到的每个后续结点为每个分支的第二点(第一点为第(3)步中删除的结点)，开始绘制相应分支。在绘制分支时，如果被绘制的结点接出有分支，则加入BranchNodeList末尾；(5)重复执行第(3)步和第(4)步，直到BranchNodeList中无对象；(6)自动缩放至全屏幕且居中展示。上述步骤中，重点在第(4)步中，如何为每一个将要绘制的结点，找到合适的位置。本文的处理方法是当需要向某个方向绘制一个图标时，先检测向此方向绘制是否会与已经存在的对象发生重叠交叉。如果会发生重叠交叉，则依次尝试向其它两个方向绘制。如果三个方向都无法绘制，则对图幅进行局部扩展，得到至少一个图标的位置再进行绘制。2 最佳绘制方向的寻找算法2.1用于表达已绘制对象所占位置的虚拟矩形单线图绘制的最基本要求，是不能有重叠交叉。同时，线条之间、图标之间以及两者之间，不能太接近，否则看起来就象重叠交叉一样。因此，在判断是会发生重叠交叉时，不能直接以已经绘制的线或图标来判断，而是应该在已经绘制好的线和图标所占的区域的基础上，作适当的扩展。同时为减少对象数量，将每一折线段上所有的线和图标所占的位置，用一个虚拟的矩形来处理，如图1所示。其中，Dn表示电气设备，Rn表示虚拟矩形。图1 虚拟矩形示意图Fig.1 Chart of virtual rectangle虚拟矩形的数据结构如下所示 (本文所有示例代码均使用c#语言)。Struct StructRect DrawObject beginObject; DrawObject endObject; string direction; float rectWidth; RectangleF area; 其中，DrawObject是绘图对象，表示画布上的一个图标11。beginObject表示此虚拟矩形的起点对象（D1,D4,D6,D12）；endObject表示此矩形对象的终点对象（D8,D9,D13,D15）；direction表示矩形的绘制方向(由于单线图要求横平竖直，因此direction是HL、HR、VU、VD之一，分别表示向左、向右、向上、向下)；rectWidth表示矩形垂直于direction方向的宽度，取系统所使用的最大的图标的长边宽度；area 表示该矩形所占的区域，每当一个分支绘制完毕、绘制方向发生了转折或矩形中的对象进行发移动时，就重新计算矩形的area,如图1中虚线方框所示。其计算方法如下：通过endObject的中心点，划一条沿direction方向的直线；沿beginObject的包围矩形的垂直于direction方向的两个边画两条直线；沿endObject的包围矩形的垂直于direction方向的两个边画两条直线；这五条直线得到四个交点。以其中距离最远的两个点作为虚拟矩形的短边中点，短边宽度为rectWidth，从而得了到虚拟矩形的大小及位置。在每次采用局部扩展算法消除重叠交叉后，都需要重新计算已绘制对象构成的虚拟矩形的位置。2.2分支的初始绘制方向的判断分支的绘制方向，要与其上级主干垂直，且不能与该主干已经有的分支重叠。其绘制方向的算法流程如图2所示。图2 分支的初始绘制方向判断流程图Fig.2 Flow chart of search the origin direction of branch对图2说明如下：（1）在绘制每一个对象时都将该对象的绘制方向保存在该对象的属性direcion中。Step1中，根据属性direction中保存的方向，得到与该方向相垂直的两个方向direction1和direction2. direction1表示向上或向左，direction2表示向右或向下。（2）在绘制主干上的每一个分支时，将该分支的绘制方向记录到主干上的接出对象属性vertical1和vertical2中。根据接出对象的绘制方向direction不同，分支方向将被增加到不同的属性中，具体情况见表1.表1 分支方向记录表Tab.1 Table of branch directionsdirection分支方向vertical1vertical2HL/HR向上10HL/HR向下01VU/VD向左10VU/VD向右01其中：HL、HR、VU、VD分别表示水平向左、水平向右、竖直向上和竖直向下。而且，接出对象的绘制方向与分支方向必然垂直。1 表示该属性值加1，0则表示该属性值不变。因此，step2中，从主干上接出对象的属性vertical1、vertical2及direction, 可以分析出在direction1和direction2两个方向上的分支个数count1和count2.（3）step5中，如果发生重叠或交叉的情况，则按照2.4所述方法进行局部扩展。2.3分支上后续对象的绘制方向的判断为尽量避免重叠与交叉，在绘制分支上的每个后续对象之前，先判断该对象的绘制方向。其算法流程图如图2所示。图3 分支后续对象绘制方向判断流程图Fig.3 Flow chart of looking for the direction of followed objects in branch对图3说明如下：（1）利用已绘制对象所构造的虚拟矩形判断以direction为正要绘制对象的绘制方向是否会重叠交叉：将正要绘制的对象所占的区域与所有已绘制对象所构造的虚拟矩形通过RectangleF. IntersectsWith (RectangleF rect)函数进行比较，函数返回true表示发生重叠或交叉。（2）step2中，direct1方向的绘制空间的计算方法如下：假设存在一个虚拟矩形ViRect，该矩形以前一个对象在direct1方向上的末端作为起点，以正要绘制的对象的绘制方向为虚拟矩形的方向，以系统所使用的最大的图标的长边宽度为矩形的宽度，矩形的长度为无穷大。判断矩形ViRect是否与所有已绘制对象所构造的虚拟矩形重叠或交叉，并记录重叠交叉的位置。根据重叠交叉的位置与虚拟矩形ViRect的起点的距离，计算direct1方向的绘制空间的大小并赋给room1。direct2方向的绘制空间的计算方法相同。2.4局部图幅扩展的算法在逐步生成配电网单线图时，难免会发生线条、图标之间的重叠与交叉的现象。我们采用局部图幅扩展算法来消除重叠与交叉，具体方法是：第一步，判断局部拉伸平移的方向。将发生重叠与交叉的虚拟矩形的方向与正要绘制图标的绘制方向相比较，若两者方向平行，则发生重叠，若两者方向垂直，则发生交叉。(1)两者重叠的情况若两者方向为水平方向，且发生重叠的虚拟矩形的纵坐标Y1小于新绘制图标的纵坐标Y2，则拉伸平移方向为竖直向上，否则拉伸平移方向为竖直向下。若两者方向为竖直方向，且发生重叠的虚拟矩形的横坐标X1小于新绘制图标的横坐标X2，则拉伸平移方向为水平向左，否则拉伸平移方向为水平向右。(2)两者交叉的情况正要绘制图标的绘制方向就是拉伸平移的方向。第二步，根据拉伸平移的方向获得拉伸平移对象。(1)若拉伸平移的方向为水平向右，设将要绘制的图标连接到的上一个图标的最大横坐标为XR,则将已生成的单线图中横坐标不小于XR的对象向右平移，直至消除重叠与交叉为止。(2)若拉伸平移的方向为水平向左，设将要绘制的图标连接到的上一个图标的最小横坐标为XL，则将已生成的单线图中横坐标不大于XL的对象向左平移，直至消除重叠与交叉为止。(3)若拉伸平移的方向为竖直向上，设将要绘制的图标连接到的上一个图标的最小纵坐标为YU,则将已生成的单线图中纵坐标不大于YU的对象向上平移，直至消除重叠与交叉为止。(4)若拉伸平移的方向为竖直向下，设将要绘制的图标连接到的上一个图标的最大纵坐标为YD，则将已生成的单线图中纵坐标不小于YD的对象向下平移，直至消除重叠与交叉为止。设分界线的两侧为A侧和B侧，A侧为需要平移的一侧。为使单线图尽量紧凑，避免连接线拉伸过长或不必要的连接线拉伸，往往A侧的一些对象不需要平移，而B侧的一些对象需要平移。具体实现步骤如下： 获得与分界线相交的连接线，其一端相连的图标在A侧，另一端的图标在B侧。以B侧与连接线相连的图标I为顶点，遍历B侧与图标I相连通的所有图标及连接线。判断所遍历的图标的绘制方向是否都与拉伸平移方向相反，如果是，则平移遍历到的所有图标、连接线；否则，拉伸与分界线相交的连接线，以A侧与连接线相连的图标II为顶点，遍历A侧与图标II相连通的所有图标及连接线。判断所遍历的图标的绘制方向是否都与拉伸平移方向相同，如果是，则遍历到的所有图标、连接线不平移；否则，平移遍历到的所有图标、连接线，并拉伸与分界线相交的连接线。3 结论单线图是电力系统重要的图形资料，是电力系统进行计算和分析的基础。本文在配电网模型的基础上，提出了一种通过寻找最佳绘制方向来尽可能避免重叠交叉，通过一维拉伸平移法消除重叠交叉的新方法。本文提出的单线图自动生成算法在江西九江供电公司的基于地理信息的配电网综合管理系统中进行了实践，所生成的单线图布局美观合理、无重叠交叉、占用绘图幅面较小、自动绘制速度快。在单线图制图和电网重构的应用中，极大地减少了系统的维护工作量，提高了单线图的准确度。所得到的单线图，在操作票管理、实时线损监视、调度管理等程序模块中得到了很好的应用。参考文献：1 张洪吉,邹峥嵘,陈军,等.基于GIS的配电网管理信息系统J.测绘科学,2009,34(1): 194-195.ZHANG Hongji, ZOU Zhengrong, CHEN Jun, et al. Power distribution management information system based on GIS J. Science of Surveying and Mapping, 2009, 34(1): 194-195.2 王亚辉,郑连清,白桦.县级配电网地理信息系统的设计与实现J.电气应用,2007,26(5):49-51.WANG Yahui, ZHENG Lianqing, BAI Hua. Design and implementation of distribution power network GIS J. Electrotechnical Application, 2007, 26(5):49-51.3 陈伟忠,秦开明,郇嘉嘉.基于Web的配电网地理信息系统的研究J.电气应用，2009，28（21）：24-28.CHEN Weizhong, QIN Kaiming, XUN Jiajia. Web-based research on distribution power network GIS J. Electrotechnical Application, 2009, 28(21):24-28.4 李晓凯,周长建,许和炎. 配电网管理中的自动制图研究J. 继电器,2008,36(6): 65-70.LI Xiaokai, ZHOU Changjian, XU Heyan. A new automatic mapping algorithm in power distribution managementJ. Relay,2008,36(6):65-70.5 Zhu Yongli, O. P. Malik. Intelligent automatic generation of graphical one-line substation arrangement diagrams J. IEEE Transactions on Power Delivery,2003,18(3):729-735.6 Xianqi Li, Xiaoliang Feng, Zhiyuan Zeng. Distribution feeder one-line diagrams automatic generation from geographic diagrams based on GISC. Nanjing China: DRPT2008, April 2008,2228-2232.7 P. S. Nagendra Rao , Ravishankar Deekshit. A novel algorithm for automatic generation of one-line diagrams of distribution feeders J. Electric Power Components and Systems, 2004,32(12): 1255-1268.8 P. S. Nagendra Rao , Ravishankar Deekshit. Distribution feeder one-line diagram generation: a visibility representationJ. Electric Power Systems Research. 2004, 70(3):173-178.9 刘健,吴媛,刘巩权. 配电馈线地理图到电气接线图的转换J. 电力系统自动化, 2005,29(14):73-77.LIU Jian, WU Yuan, Liu Gongquan. Conversion from GIS based feeder maps to eletric diagram J. Automation of Electric Power Systems, 2005, 29(14): 73-77.10 章坚民,楼坚.基于CIM/ SVG和面向对象的配电单线图自动生成J.电力系统自动化,2008,32(22):61-65.ZHANG Jianming, LOU Jian. Automatic generation of single-line diagram for distribution feeder systems based on CIM/SVG and object orientation J. Automation of Electric Power Systems, 2008,32(22):61-65.11 宋适宇,何光宇,徐彭亮,等. 输电网单线图的自动生成算法J. 电力系统自动化,2007,31(24):12-15.SONG Shiyu, HE Guangyu, XU Pengliang, et al. Automatic generation of single line diagram for transmission networks J. Automation of Electric Power Systems, 2007, 31(24): 12-15.12 徐彭亮,何光宇，梅生伟,等. 基于地理信息的输电网单线图自动生成新算法J.电网技术,2008,32(21):9-12.XU Pengliang, HE Guangyu, MEI Shengwei, et al. Application of geographic information in automatic generation of single-line diagrams for power transmission networksJ. Power System Technology,2008,32(21):9-12.13 胡 森,徐学军,冯晓良. 基于配电GIS 动态拓扑关系生成电气接线图J. 继电器,2007, 35(9):52-55.HU Sen, XU Xuejun, FENG Xiaoliang. GIS-based dynamic relationship of topology to generate electrical diagrams of distribution network J. Relay,2007,35(9):52-55.14 朱永利,栗然,刘艳电力系统厂站主接线图形的自动生成J电力系统及其自动化学报,2000,12(1):43-46.ZHU Yongli, LI Ran, LIU Yan. Automatic generation of plant station main wiring graph in power systemJProceedings of EPSA,2000,12(1):43-46.15 邓其军,周洪，鲁觉面向图形对象的配电网单线图绘制与使用 J电力自动化设备,2009,29(7):43-47.DENG Qijun, ZHOU Hong, LU Jue Drawing and application of GOO single-line display of distribution network J. Electric Power Automation Equipment，2009,29(7):43-47.作者简介：陈 勇 （1986-），男，江苏东台人，硕士研究生，研究方向为电力系统计算机控制、配电网建模与分析；e-mail:邓其军（1975-），男，湖北新洲人，博士，讲师，研究方向为电力系统计算机控制， email:周 洪（1962-），男，湖北武汉人，博士，教授，研究方向为复杂机电过程控制系统、智能发电与电网控制An Algorithm for Automatic Generation of One-line Diagram of Distribution Network without Overlap and IntersectionCHEN Yong, DENG Qijun, ZHOU Hong(Department of Automation, Wuhan University, Hubei, 430072)Abstract: The elimination of the intersection and overlap of buses and other facilities is the biggest problem when automatic converting GIS maps of distribution feeders into one-line diagrams based on the topologic relationships of the equipments. Based on the graphic-object-oriente