基于层次包围盒的配电网电气接线图自动生成算法

梁艳

摘  要：针对配电线的地理接线图自动转换为单线图时，线和设备的重叠交叉问题，该文提出了一种基于层次包围盒技术的自动成图排布算法;针对层次包围盒不紧密性造成的空间浪费，提出了一种对排布方向可能相交的临近路径的包围盒进行相交检测，及时利用空闲空间排布线路的方法。算法支持架空、地缆及混合型的区域电气接线图，真正解决了实际应用问题。

关键词：配电网;电气接线图;自动生成;交叉;层次包围盒

中图分类号：TM73        文献标志码：A

0 引言

区域电气接线图是配电管理系统中调度人员监控实时运行信息的图形界面，数据一致、排布清晰且实用性强的区域接线图是不可缺少的图形资料。

电气接线图自动生成的研究集中于排布策略、防止交叉和空间利用几方面。1）排布策略上，基于图论模型提出了根据所含节点数目将馈线分解成若干分支集合的思想，这种方法易于实现，但容易引起排布交叉问题，而消除交叉又会引起性能低下和空白区域过多的问题;将自动成图问题归结为节点位置自动排布和线路走线2个方面，提出用罚函数法完成节点布局和用寻路法完成自动走线，这种布局策略着眼于呈现设备之间的关联关系，不能很好体现出电气接线图线路主干、支线和潮流方向。2）防止交叉和交叉处理是自动排布研究的重要方面。通过寻找最佳绘制方向来避免重叠的方法，会造成空间浪费而影响设备均匀排布效果;基于拓扑分层的自动生成算法，采用基于引力—斥力模型的布局算法，算法避免了交叉但空间利用率低。3）避免交叉而引起的空间浪费成为另一个研究角度。通过在平移方向上移动必要的树形分支，以解决线路交叉引起的设备拉伸问题，此方法还有效解决了空间浪费问题;通过空间膨胀和空间压缩2个阶段，实现了避免重叠和有效利用空间，但空间压缩阶段带来不必要的性能开销。

以上研究重点关注避免交叉和空间利用等方面，研究集中于架空线路的排布，即线路由非站房设备构成，特点是构成线路的设备占据空间小、均匀。很少有研究从架空和地缆2个方面分析算法效果;但在配电管理系统实际应用中，对站房设备进、出线接线关系的监控是非常重要的，这方面的研究文献非常少，并且是一直以来的难点。

该文针对区域电气接线图线路类型的多样性和监控实际应用需求，提出了基于层次包围盒的配电网电气接线图自动生成算法。对于电气接线图所有设备，自底向上逐步建立设备、路径分支直到整棵树的层次包围盒，有效避免了交叉;对于包含站房设备的配电线，将站房设备连同其内部接线一起作为一个节点参与排布，这种管理方式使算法有效适用于各种类型线路;另外，在建立层次包围盒的过程中，针对包围盒的不紧密性可能引起的空间浪费问题，提出对可能相交的临近包围盒进行求交判断，若不相交则利用空闲空间，即无性能损耗又充分利用了空间。

1 配电网的数据模型

对配电网馈线电气拓扑关系数据，建立基于图论的模型。1）节点，包括变电站电源点，开合设备、配变、T节点、杆塔、配变、线路末端节点和站房设备等。以上每一个设备代表一个节点Vi（i =1，2，3…n），配电线总共有n个设备，节点的集合V={V1，V2，…，Vi，…，Vn，n≥0}。特别地，站房设备连同其内部接线一起作为一个节点参与排布。2）有向边，从电源点开始，沿潮流方向首先搜索到的节点设备为父亲节点，父亲节点Vm到孩子节点Vn建立有向边为（其中Vm，Vn∈V）。3）有向图，依据节点和有向边建立有向图。4）由此得到一个根节点为电源点的树。树的最大深度路径包含的节点构成1级路径，自顶向下递归搜索得到N级路径（N>1）。树的度等于路径的最大级别。一条配电箱分解为一条1级路径，多条N级路径（N>1）。

层次包围盒方法是用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，其中根节点包括整个对象，逐次向下的子节点为上一根节点包括的对象的拆分。轴向包围盒AABB（Axis-Aligned BoundingBox）定义为各条边都平行于坐标轴且包括该对象的最小方长方体，AABB包围盒具有构造容易且符合电气接线图横平竖直排布要求的特性。

2 基于层次包围盒的自动排布算法

2.1 设备节点树的建立

定义：节点为TTreeNode，节点集合为TreeNodeList，路径为TBranch，路径集合为BranchList。

步骤（1）建立树：从电源点开始沿配电网馈线电气拓扑数据的设备和连接线进行深度优先递归搜索，建立节点TTreeNode和有向边数据结构，得到节点集合TreeNodeList。

步骤（2）关键路径：对步骤（1）得到的图进行深度优先递归搜索，建立关键路径TBranch数据结构，得到各个等级路径集合BranchList。

步骤（3）路径方向：计算步骤（2）路径集合BranchList每条路径的方向。一般的，奇数级路径水平放置，偶数级线路垂直放置。通常依据地理电气接线图分支潮流方向来计算路径方向。

2.2 层次包围盒排布算法

2.2.1 初始化数据

根据国网配电调度技术图符绘制规范，避免由于显示器差异造成显示误差，因此采用“lb”作为图符绘制单位。定义W等于开合设备图符宽度（规范定义为0.3 lb）。

初始包围盒：依据第1章节定义的最小包围盒，计算TreeNodeList每个设备符号的层次包围盒;特别的，站房设备节点的层次包围盒为站内接线图矩形区域。

初始定义：d定义为两个设备图符之间的距离，当两设备间距小于?d=0.01W时，两设备相交。两设备间的最小距离为?t=W，即两个设备间距小于?t时，认为过渡密集。

根据每个设备的包围盒，可以得到最大图符高度?h。两个设备间的单位距离为定义为L=?h+?t，在此認为所有设备图符大小是均匀的。

2.2.2 自底向上计算设备坐标并建立层次包围盒

计算得到的设备坐标，指的是设备所占据矩形范围中心点的坐标。通过本搜索过程，输出所有设备坐标，得到各个级别路径的包围盒。

2.2.3 空间利用检测

在自底向上构建层次包围盒树的过程中，当向已构建的包围盒中添加新的包围盒时，由于AABB包围盒的不紧密性，可能造成空间的浪费。因此，在构建包围盒时，做快速相交测试来判断是否有可利用空间。已经存在的包围盒为AExit，待加入包围盒为ABranch。流程如下：

3 实例

如图1所示为地理电气接线图的一条配电线，图中“SS”表示变电站，“SW”表示开合设备，“P”表示配变，“T”表示T节点，“N”表示线路末端节点，“X”表示杆塔，“MSW”表示站房设备（有站内接线图的设备，象配电房、电缆分支箱等）。

（1）根据第1章节定义，从电源点开始搜索建立设备树。树的根节点为“VSS1”，树的深度为13，树的度为3。得到树节点为VN5，VX1，VP10

（3）自底向上逐步構建层次包围盒树，同时完成设备坐标的计算排布任务。①树的最大深度叶子节点是VN5，对VN5赋值初始坐标点PN5（Xstart，Ystart）;②VN5节点向上回溯到节点VX1，VX1没有其他分支，VN5和VX1所在的路径方向为自左向右，则VX1坐标为PX1（PN5.X - L，PN5.Y），则VN5和VX1的最小包围盒AN5、AX1构成新的包围盒AB1;③继续回溯到节点VP10，VP10与VX1节点情况相同，则得到VP10坐标PP10（PX1.X - L，PX1.Y），则AB1包围盒和VP10最小包围盒AP10更新了包围盒AB1的范围;④继续向上回溯，经过节点VP9，VP8，得到VP9和VP8的排布坐标，并更新包围盒AB1的范围;⑤继续向上回溯到节点VT3，VT3有其他子树，进入子树分支，从根节点开始进行以上递归回溯过程。

（4）在递归回溯构建Ⅱ级分支B2.4（VT3，VT4，VT5，VSW6，VN4）过程中，当完成VN4，VSW6，VP7，VP6，VT5层次包围盒的AB2.4构建后，向其中添加Ⅲ级别分支B2.4.1（VT4，VSW4，VP11，VN3）时，发现B2.4.1分支与已构建层次包围盒AB2.4中同级别分支B2.4.2（VT5，VP6，VP7），路径走向相同都为自左向右，则2个分支所在的层次包围盒可能相交但也可能存在可利用空间。对2条分支路径进行相交测试，得到距离层次包围盒AB2.4.2最近的设备P11，距离AB2.4.1最近的设备P6，只要这两个设备不与对方设备相交，则其他设备一定不会相交。

（5）图3为基于层次包围盒的自动排布算法生成效果示意图。整条配电线排布均匀，无交叉并且及时有效地利用了空闲空间;使站房设备排布美观，满足了实际配电监控应用需求。

4 结语

通过实验验证，该文提出的算法有效避免了交叉，并且通过对路径方向可能相交的临近路径包围盒进行相交判断，快速构建包围盒，达到充分利用空间的效果;层次包围盒算法非常适合管理包括站房设备的配电线，解决了对站房设备进出线监控的实际应用问题。但由于AABB层次包围盒对研究对象包裹紧密性较差，因此造成空间浪费，从而增加了利用空闲空间的性能开销，在这方面有待进一步研究。

层次包围盒技术，是虚拟现实动态模型碰撞检测的重要技术，能有效解决复杂的2D、3D相交和碰撞问题，可以为避免交叉研究提供更多新的立足点，象方向包围盒（OBB）、离散方向多面体包围盒（K-DOPs）、包围球（Sphere）等空间紧密性更好的包围盒，针对配电线排布的特点，利用各种类型层次包围盒的优势，构建更加有效的包围盒将是很好的研究方向。

参考文献

[1]刘健，吴娱，刘巩权.配电馈线地理图到电气接线图的转换[J].电力系统自动化，2005，29（14）：73-77.

[2]宋适宇，何光宇，徐彭亮.输电网单线图的自动生成算法[J].电力系统自动化，2007，31（24）：12-15.

[3]陈勇，邓其军，周洪.无重叠交叉的配电网单线图自动生成算法[J].电力自动化设备，2010，30（11）：90-93.

[4]廖凡钦，刘东，闫红漫，等.基于拓扑分层的配电网电气接线图自动生成算法[J].电力系统自动化，2010，38（13）：174-180.

[5]韩文明. 基于模型的配电网单线图自动生成[D].上海：东华大学，2013.

[6]北京国科恒通电气自动化科技有限公司.电网地理信息系统中配电单线图的自动布局方法：中国，201010285953.9[P].2012-04-04.

[7]邹益胜，丁国富，许明恒，等.实时碰撞检测算法综述[J].计算机应用研究，2008，25（1）：8-12.

[8]Vanden B G. Efficient Collision Detection of Complex Deformable Models Using AABB Trees[J].Journal of Graphics Tools， 1997，2（4）： 1-14.

[9]Gottschallk S，Lin M C，Manocha D.Obbtree：a hierarchical structure foe rapid interference detection[C]//Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques，New York，NY，USA，1996：171-180.

[10]Klosowski J，Held M，Mitehell J，et al.Efficient collision detection using bounding volume hierarchies of K-DOPs[J].IEEE Transactions on Visualization and Computer Graphics，1998，4（1）：21-37.

[11]Palmer I J，Grimsdale R L.Collision detection for animation using sphere-trees[J].Computer Graphics Forum，1995，14（2）：105-116.