梁艷

摘? 要：針對配電線的地理接線圖自動轉(zhuǎn)換為單線圖時，線和設備的重疊交叉問題，該文提出了一種基于層次包圍盒技術的自動成圖排布算法;針對層次包圍盒不緊密性造成的空間浪費，提出了一種對排布方向可能相交的臨近路徑的包圍盒進行相交檢測，及時利用空閑空間排布線路的方法。算法支持架空、地纜及混合型的區(qū)域電氣接線圖，真正解決了實際應用問題。

關鍵詞：配電網(wǎng);電氣接線圖;自動生成;交叉;層次包圍盒

中圖分類號：TM73? ? ? ? 文獻標志碼：A

0 引言

區(qū)域電氣接線圖是配電管理系統(tǒng)中調(diào)度人員監(jiān)控實時運行信息的圖形界面，數(shù)據(jù)一致、排布清晰且實用性強的區(qū)域接線圖是不可缺少的圖形資料。

電氣接線圖自動生成的研究集中于排布策略、防止交叉和空間利用幾方面。1）排布策略上，基于圖論模型提出了根據(jù)所含節(jié)點數(shù)目將饋線分解成若干分支集合的思想，這種方法易于實現(xiàn)，但容易引起排布交叉問題，而消除交叉又會引起性能低下和空白區(qū)域過多的問題;將自動成圖問題歸結為節(jié)點位置自動排布和線路走線2個方面，提出用罰函數(shù)法完成節(jié)點布局和用尋路法完成自動走線，這種布局策略著眼于呈現(xiàn)設備之間的關聯(lián)關系，不能很好體現(xiàn)出電氣接線圖線路主干、支線和潮流方向。2）防止交叉和交叉處理是自動排布研究的重要方面。通過尋找最佳繪制方向來避免重疊的方法，會造成空間浪費而影響設備均勻排布效果;基于拓撲分層的自動生成算法，采用基于引力—斥力模型的布局算法，算法避免了交叉但空間利用率低。3）避免交叉而引起的空間浪費成為另一個研究角度。通過在平移方向上移動必要的樹形分支，以解決線路交叉引起的設備拉伸問題，此方法還有效解決了空間浪費問題;通過空間膨脹和空間壓縮2個階段，實現(xiàn)了避免重疊和有效利用空間，但空間壓縮階段帶來不必要的性能開銷。

以上研究重點關注避免交叉和空間利用等方面，研究集中于架空線路的排布，即線路由非站房設備構成，特點是構成線路的設備占據(jù)空間小、均勻。很少有研究從架空和地纜2個方面分析算法效果;但在配電管理系統(tǒng)實際應用中，對站房設備進、出線接線關系的監(jiān)控是非常重要的，這方面的研究文獻非常少，并且是一直以來的難點。

該文針對區(qū)域電氣接線圖線路類型的多樣性和監(jiān)控實際應用需求，提出了基于層次包圍盒的配電網(wǎng)電氣接線圖自動生成算法。對于電氣接線圖所有設備，自底向上逐步建立設備、路徑分支直到整棵樹的層次包圍盒，有效避免了交叉;對于包含站房設備的配電線，將站房設備連同其內(nèi)部接線一起作為一個節(jié)點參與排布，這種管理方式使算法有效適用于各種類型線路;另外，在建立層次包圍盒的過程中，針對包圍盒的不緊密性可能引起的空間浪費問題，提出對可能相交的臨近包圍盒進行求交判斷，若不相交則利用空閑空間，即無性能損耗又充分利用了空間。

1 配電網(wǎng)的數(shù)據(jù)模型

對配電網(wǎng)饋線電氣拓撲關系數(shù)據(jù)，建立基于圖論的模型。1）節(jié)點，包括變電站電源點，開合設備、配變、T節(jié)點、桿塔、配變、線路末端節(jié)點和站房設備等。以上每一個設備代表一個節(jié)點Vi（i =1，2，3…n），配電線總共有n個設備，節(jié)點的集合V={V1，V2，…，Vi，…，Vn，n≥0}。特別地，站房設備連同其內(nèi)部接線一起作為一個節(jié)點參與排布。2）有向邊，從電源點開始，沿潮流方向首先搜索到的節(jié)點設備為父親節(jié)點，父親節(jié)點Vm到孩子節(jié)點Vn建立有向邊為（其中Vm，Vn∈V）。3）有向圖，依據(jù)節(jié)點和有向邊建立有向圖。4）由此得到一個根節(jié)點為電源點的樹。樹的最大深度路徑包含的節(jié)點構成1級路徑，自頂向下遞歸搜索得到N級路徑（N>1）。樹的度等于路徑的最大級別。一條配電箱分解為一條1級路徑，多條N級路徑（N>1）。

層次包圍盒方法是用體積略大而幾何特性簡單的包圍盒來近似地描述復雜的幾何對象，其中根節(jié)點包括整個對象，逐次向下的子節(jié)點為上一根節(jié)點包括的對象的拆分。軸向包圍盒AABB（Axis-Aligned BoundingBox）定義為各條邊都平行于坐標軸且包括該對象的最小方長方體，AABB包圍盒具有構造容易且符合電氣接線圖橫平豎直排布要求的特性。

2 基于層次包圍盒的自動排布算法

2.1 設備節(jié)點樹的建立

定義：節(jié)點為TTreeNode，節(jié)點集合為TreeNodeList，路徑為TBranch，路徑集合為BranchList。

步驟（1）建立樹：從電源點開始沿配電網(wǎng)饋線電氣拓撲數(shù)據(jù)的設備和連接線進行深度優(yōu)先遞歸搜索，建立節(jié)點TTreeNode和有向邊數(shù)據(jù)結構，得到節(jié)點集合TreeNodeList。

步驟（2）關鍵路徑：對步驟（1）得到的圖進行深度優(yōu)先遞歸搜索，建立關鍵路徑TBranch數(shù)據(jù)結構，得到各個等級路徑集合BranchList。

步驟（3）路徑方向：計算步驟（2）路徑集合BranchList每條路徑的方向。一般的，奇數(shù)級路徑水平放置，偶數(shù)級線路垂直放置。通常依據(jù)地理電氣接線圖分支潮流方向來計算路徑方向。

2.2 層次包圍盒排布算法

2.2.1 初始化數(shù)據(jù)

根據(jù)國網(wǎng)配電調(diào)度技術圖符繪制規(guī)范，避免由于顯示器差異造成顯示誤差，因此采用“l(fā)b”作為圖符繪制單位。定義W等于開合設備圖符寬度（規(guī)范定義為0.3 lb）。

初始包圍盒：依據(jù)第1章節(jié)定義的最小包圍盒，計算TreeNodeList每個設備符號的層次包圍盒;特別的，站房設備節(jié)點的層次包圍盒為站內(nèi)接線圖矩形區(qū)域。

初始定義：d定義為兩個設備圖符之間的距離，當兩設備間距小于?d=0.01W時，兩設備相交。兩設備間的最小距離為?t=W，即兩個設備間距小于?t時，認為過渡密集。

根據(jù)每個設備的包圍盒，可以得到最大圖符高度?h。兩個設備間的單位距離為定義為L=?h+?t，在此認為所有設備圖符大小是均勻的。

2.2.2 自底向上計算設備坐標并建立層次包圍盒

計算得到的設備坐標，指的是設備所占據(jù)矩形范圍中心點的坐標。通過本搜索過程，輸出所有設備坐標，得到各個級別路徑的包圍盒。

2.2.3 空間利用檢測

在自底向上構建層次包圍盒樹的過程中，當向已構建的包圍盒中添加新的包圍盒時，由于AABB包圍盒的不緊密性，可能造成空間的浪費。因此，在構建包圍盒時，做快速相交測試來判斷是否有可利用空間。已經(jīng)存在的包圍盒為AExit，待加入包圍盒為ABranch。流程如下：

3 實例

如圖1所示為地理電氣接線圖的一條配電線，圖中“SS”表示變電站，“SW”表示開合設備，“P”表示配變，“T”表示T節(jié)點，“N”表示線路末端節(jié)點，“X”表示桿塔，“MSW”表示站房設備（有站內(nèi)接線圖的設備，象配電房、電纜分支箱等）。

（1）根據(jù)第1章節(jié)定義，從電源點開始搜索建立設備樹。樹的根節(jié)點為“VSS1”，樹的深度為13，樹的度為3。得到樹節(jié)點為VN5，VX1，VP10

（3）自底向上逐步構建層次包圍盒樹，同時完成設備坐標的計算排布任務。①樹的最大深度葉子節(jié)點是VN5，對VN5賦值初始坐標點PN5（Xstart，Ystart）;②VN5節(jié)點向上回溯到節(jié)點VX1，VX1沒有其他分支，VN5和VX1所在的路徑方向為自左向右，則VX1坐標為PX1（PN5.X - L，PN5.Y），則VN5和VX1的最小包圍盒AN5、AX1構成新的包圍盒AB1;③繼續(xù)回溯到節(jié)點VP10，VP10與VX1節(jié)點情況相同，則得到VP10坐標PP10（PX1.X - L，PX1.Y），則AB1包圍盒和VP10最小包圍盒AP10更新了包圍盒AB1的范圍;④繼續(xù)向上回溯，經(jīng)過節(jié)點VP9，VP8，得到VP9和VP8的排布坐標，并更新包圍盒AB1的范圍;⑤繼續(xù)向上回溯到節(jié)點VT3，VT3有其他子樹，進入子樹分支，從根節(jié)點開始進行以上遞歸回溯過程。

（4）在遞歸回溯構建Ⅱ級分支B2.4（VT3，VT4，VT5，VSW6，VN4）過程中，當完成VN4，VSW6，VP7，VP6，VT5層次包圍盒的AB2.4構建后，向其中添加Ⅲ級別分支B2.4.1（VT4，VSW4，VP11，VN3）時，發(fā)現(xiàn)B2.4.1分支與已構建層次包圍盒AB2.4中同級別分支B2.4.2（VT5，VP6，VP7），路徑走向相同都為自左向右，則2個分支所在的層次包圍盒可能相交但也可能存在可利用空間。對2條分支路徑進行相交測試，得到距離層次包圍盒AB2.4.2最近的設備P11，距離AB2.4.1最近的設備P6，只要這兩個設備不與對方設備相交，則其他設備一定不會相交。

（5）圖3為基于層次包圍盒的自動排布算法生成效果示意圖。整條配電線排布均勻，無交叉并且及時有效地利用了空閑空間;使站房設備排布美觀，滿足了實際配電監(jiān)控應用需求。

4 結語

通過實驗驗證，該文提出的算法有效避免了交叉，并且通過對路徑方向可能相交的臨近路徑包圍盒進行相交判斷，快速構建包圍盒，達到充分利用空間的效果;層次包圍盒算法非常適合管理包括站房設備的配電線，解決了對站房設備進出線監(jiān)控的實際應用問題。但由于AABB層次包圍盒對研究對象包裹緊密性較差，因此造成空間浪費，從而增加了利用空閑空間的性能開銷，在這方面有待進一步研究。

層次包圍盒技術，是虛擬現(xiàn)實動態(tài)模型碰撞檢測的重要技術，能有效解決復雜的2D、3D相交和碰撞問題，可以為避免交叉研究提供更多新的立足點，象方向包圍盒（OBB）、離散方向多面體包圍盒（K-DOPs）、包圍球（Sphere）等空間緊密性更好的包圍盒，針對配電線排布的特點，利用各種類型層次包圍盒的優(yōu)勢，構建更加有效的包圍盒將是很好的研究方向。

參考文獻

[1]劉健，吳娛，劉鞏權.配電饋線地理圖到電氣接線圖的轉(zhuǎn)換[J].電力系統(tǒng)自動化，2005，29（14）：73-77.

[2]宋適宇，何光宇，徐彭亮.輸電網(wǎng)單線圖的自動生成算法[J].電力系統(tǒng)自動化，2007，31（24）：12-15.

[3]陳勇，鄧其軍，周洪.無重疊交叉的配電網(wǎng)單線圖自動生成算法[J].電力自動化設備，2010，30（11）：90-93.

[4]廖凡欽，劉東，閆紅漫，等.基于拓撲分層的配電網(wǎng)電氣接線圖自動生成算法[J].電力系統(tǒng)自動化，2010，38（13）：174-180.

[5]韓文明. 基于模型的配電網(wǎng)單線圖自動生成[D].上海：東華大學，2013.

[6]北京國科恒通電氣自動化科技有限公司.電網(wǎng)地理信息系統(tǒng)中配電單線圖的自動布局方法：中國，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.