陳挺，徐恩，王浩文，謝小林，吳倩

(1．國網(wǎng)浙江省電力有限公司諸暨市供電公司，浙江 諸暨 311800；2．天地電研(北京)科技有限公司杭州分公司，浙江 杭州 310013；3. 天地電研(北京)科技有限公司，北京 昌平 102206)

0 引言

在配電網(wǎng)規(guī)劃的編制過程中，繪制中壓地理接線圖的環(huán)節(jié)必不可少。目前，多依賴于規(guī)劃人員在繪圖軟件中繪制地理接線圖，效率不高。電網(wǎng)地理接線圖是以地理信息系統(tǒng)(geographic information system，GIS)為背景，以經(jīng)緯度精確標(biāo)注或顯示電力設(shè)備地理位置的接線圖[1]。若能將基于地理坐標(biāo)信息的電網(wǎng)GIS圖用于配電網(wǎng)規(guī)劃中，效率將大大提高。然而，過于強調(diào)GIS圖中配電網(wǎng)設(shè)備和饋線位置的準(zhǔn)確性，線路轉(zhuǎn)彎、中斷、交叉等情況很多，難以直觀辨認饋線主干走向和其上連接設(shè)備的隸屬關(guān)系。

為將地理接線圖按照拓撲連接關(guān)系重新生成易于辨認、清晰美觀的圖形，文獻[2]設(shè)計一種從外向內(nèi)逐次布局的環(huán)形布局算法，采用拓撲搜索和寬度優(yōu)先搜索算法計算出某饋線與聯(lián)絡(luò)饋線的所有可達路徑。文獻[3]采用力導(dǎo)引改進算法生成一個具有明顯聚類結(jié)構(gòu)、能夠體現(xiàn)圖結(jié)構(gòu)信息的初步布局。文獻[4]先通過固定主干線和圖形分塊的方法確定圖形框架，再按照深度對分支節(jié)點進行改進，并對主干線節(jié)點質(zhì)量及距離進行優(yōu)化。文獻[5-7]將單線圖自動成圖方法分成布局和布線兩部分。布局時將布局總面積最小、線路總長度估計值最短作為優(yōu)化目標(biāo)，布線時采用線探索法進行避障布線。上述研究強調(diào)出現(xiàn)的交叉盡可能少或走線路徑最短，成圖多為拓撲圖而非能反映原始走向、長度信息的地理接線圖，不適合規(guī)劃人員開展配電網(wǎng)規(guī)劃工作。

緩沖區(qū)骨架線的本質(zhì)是以原始數(shù)據(jù)集的一個子集來代表整個原始數(shù)據(jù)集，從而達到提取圖形特征參量的目的。其基本思想是給定一個空間或平面實體的集合，給定距離(緩沖半徑或?qū)挾?后，按該距離向外擴張得到幾何形狀的集合。根據(jù)該集合可以確定實體對于外界的影響范圍或輻射范圍。目前已在空間分析等方面得到廣泛應(yīng)用，例如，研究河系結(jié)構(gòu)方面，當(dāng)各有關(guān)內(nèi)部結(jié)構(gòu)如局部寬度變化、分叉等可忽略時，可以用河道骨架線來代表河流[8]。電纜或架空線路敷設(shè)或架設(shè)的廊道中心線也是電纜或架空線路緩沖區(qū)的中心線，是對饋線主體形狀的抽象描述，能夠反映廊道中所布饋線的主延伸方向和主體形狀特征。

受此啟發(fā)，本文將基于泰森多邊形的緩沖區(qū)骨架線提取技術(shù)用于配電網(wǎng)GIS圖中，提出基于泰森多邊形[9-14]的配電網(wǎng)GIS圖美化算法。首先通過緩沖處理把若干條距離相近的饋線合并為一個整體，形成這些饋線的包絡(luò)緩沖區(qū)，利用泰森多邊形得到該緩沖區(qū)的中心線，即緩沖區(qū)中心線或廊道中心線，進一步得到每段廊道所包含的具體饋線段，再按從左到右的順序等間隔排列此段廊道內(nèi)所含的各饋線段，即可達到各饋線段不交叉和美觀排布的目的，最后采用“前推后代”法捋順整條饋線上、下級饋線段之間的連接關(guān)系，將相鄰饋線段順次拼接，并將相關(guān)配電設(shè)備和開關(guān)設(shè)備接入其所屬饋線段，即可完成整條饋線的美化。實現(xiàn)了在饋線段或設(shè)備位置適當(dāng)偏移的基礎(chǔ)上保證連接關(guān)系和主體走向不變，克服了配電網(wǎng)GIS單線圖美化的技術(shù)難關(guān)，使其經(jīng)自動化處理后可直接用于配電網(wǎng)規(guī)劃工作。

1 算法流程

該算法主要包括數(shù)據(jù)預(yù)處理，生成緩沖區(qū)中心線、形成包含關(guān)系，確定饋線段上下連接關(guān)系、并拼接饋線段，確定設(shè)備所屬饋線段的過程。美化過程流程如圖1所示。

圖1 美化流程

1)以配電網(wǎng)GIS圖為數(shù)據(jù)源，通過GIS軟件提供的接口程序，提取出GIS圖中各點的坐標(biāo)數(shù)據(jù)及相關(guān)參數(shù)。

2)以單個變電站的所有10 kV饋線為整體，生成包含所有饋線的廊道緩沖區(qū)。

3)根據(jù)泰森多邊形算法提取緩沖區(qū)的中心線。

4)根據(jù)中心線的分叉點生成各緩沖區(qū)切片，形成緩沖區(qū)切片與饋線段的包含關(guān)系。

5)根據(jù)緩沖區(qū)中心線的上下游組成線段連接關(guān)系，確定以其為中心的各條饋線的上下游連接關(guān)系。

6)根據(jù)連接關(guān)系順次連接各段饋線，根據(jù)設(shè)備與饋線段的隸屬關(guān)系，將相應(yīng)設(shè)備連接至所屬饋線段，從而生成整條饋線。

上述各步驟中，生成緩沖區(qū)切片、形成緩沖區(qū)切片與饋線段的包含關(guān)系、緩沖區(qū)中心線的連接關(guān)系、生成各條饋線的連接關(guān)系是該算法的核心。

2 預(yù)處理

2.1 緩沖區(qū)生成

對配電網(wǎng)GIS圖的緩沖處理是以1個變電站內(nèi)所有10 kV出線為整體生成緩沖區(qū)，目的是把距離相近、可一起美化的饋線作為一組饋線，包絡(luò)多邊形反映出這組饋線的走向和分布范圍，在饋線周圍建立一定寬度的帶狀區(qū)。生成緩沖區(qū)的方法有較多的文獻進行闡述[15-20]，包括單目標(biāo)緩沖區(qū)生成和多目標(biāo)重疊緩沖區(qū)多邊形間的合并兩個步驟。在對緩沖區(qū)邊界求交集時設(shè)定邊界之間距離閾值為ε，若大于該閾值，則認為無交集，是獨立的2個緩沖區(qū)。

以某變電站為例，生成的緩沖區(qū)如圖2所示。

圖2 某變電站所有饋線的緩沖區(qū)

圖2中，紅線代表變電站的饋線，黑線代表緩沖區(qū)。緩沖區(qū)確定了該變電站所有饋線出線的邊界。

2.2 生成緩沖區(qū)中心線

首先采用泰森多邊形算法提取緩沖區(qū)中心線，然后以緩沖區(qū)中心線作為饋線組內(nèi)各條饋線等距排布的參考基線，對各原始饋線重新進行等距排布。以某變電站為例，提取緩沖區(qū)中心線前后的效果圖分別如圖3(a)、(b)所示。

(a)提取前

(b)提取后

定義組成緩沖區(qū)中心線的3條及以上線段相交的節(jié)點為“交叉點”。圖3(b)中，紅線為提取出的緩沖區(qū)中心線，節(jié)點A、B、C、D和E均為中心線分叉點。

需要注意的是，初次生成的緩沖區(qū)中心線并不是平滑的線段，而是會出現(xiàn)鋸齒狀，這是由泰森多邊形的性質(zhì)決定的，需要進行優(yōu)化處理。方法是將緩沖區(qū)中心線依照走向分成若干段，然后對各段的首尾進行“拉直”，刪除不必要的節(jié)點。

3 緩沖區(qū)切片并形成包含關(guān)系

3.1 緩沖區(qū)切片

以中心線交叉點為參考點對緩沖區(qū)進行切片(即分解)，切片過程能夠得知相互鄰接的切片，切片之間的鄰接關(guān)系也確定了切片內(nèi)所含饋線段的鄰接關(guān)系。

泰森多邊形具有如下特征：對于平面區(qū)域上給定的k個離散點，將區(qū)域相應(yīng)分成k個泰森多邊形的分法是唯一的；泰森多邊形是凸多邊形；任意2個泰森多邊形不存在公共區(qū)域。因此采用泰森多邊形算法對緩沖區(qū)進行切片，所得到的各切片范圍內(nèi)包含的饋線段是唯一的，或者說每條饋線段只屬于1個切片，從原理上避免了交叉。圖3(b)中，黃色的線即為各切片的分界線。采用分別對每個切片求所含饋線，而不是對整個廊道求解所含饋線段的方式，是因為各切片范圍內(nèi)包含的饋線段條數(shù)有限，相比于整體數(shù)量更少，更容易理清各種情形下如何操作才能使所引起的交叉最少。

從獲取到的GIS圖數(shù)據(jù)中查詢整條饋線的名稱(或ID)和各個饋線段的名稱(或ID)，并為各緩沖區(qū)切片命名。每個饋線段的名稱或ID由三層結(jié)構(gòu)組成：第一層是緩沖區(qū)切片名稱或ID，第二層是整條饋線名或ID，第三層是饋線段名或ID。形成切片名-饋線名-線段名的饋線段三級命名。

3.2 緩沖區(qū)中心線段的表達

各條饋線由各個饋線段順次連接組成，為方便得到各饋線段的連接關(guān)系，需要進行圖形數(shù)字化處理，采用節(jié)點索引表和線段索引表表達。以緩沖區(qū)中心線為例，以節(jié)點索引表和線段索引表的方式記錄每個中心線段的起始(首)節(jié)點ID和終止(尾)節(jié)點ID，具有相同ID的節(jié)點便是兩個中心線段的連接點。對相互連接的中心線段進行匹配時，只需保證中心線段節(jié)點具有相同的ID即可。對中心線段節(jié)點按照X坐標(biāo)從小到大、Y坐標(biāo)從小到大的順序排序，使得搜索過程簡化為僅對中心線段的首尾節(jié)點進行判斷。節(jié)點索引表的結(jié)構(gòu)見表1。

表1 節(jié)點索引表

按中心線段的連接順序?qū)⒏髦行木€段編成線段索引表，以存放各切片內(nèi)中心線段首尾節(jié)點的信息。線段索引表的結(jié)構(gòu)見表2。

表2 線段索引表

反之，根據(jù)表2中提供的中心線段信息，按中心線段ID的連接順序，對表中首尾節(jié)點ID進行提??；把具有相同ID的節(jié)點及其所連接的線段按表1結(jié)構(gòu)寫入，便可得到表1所示的節(jié)點索引表。在形成節(jié)點索引表的過程中，只需對線段索引表結(jié)構(gòu)中的線段起點ID、終點ID反復(fù)遞增掃描即可提取出所需信息，比起對原數(shù)據(jù)文件進行反復(fù)遍歷搜索，可大大減少時間。此步驟中所確定的切片中心線段與節(jié)點之間的關(guān)系，是下一步各饋線段上下級連接關(guān)系的基礎(chǔ)。

4 確定饋線段的連接關(guān)系

4.1 以緩沖區(qū)中心線為參考確定饋線段的位置

對各饋線段以緩沖區(qū)中心線為基準(zhǔn)進行偏移處理：若饋線段的數(shù)量為奇數(shù)，則將最中間的饋線段放置在緩沖區(qū)中心線上，其余線段以此為對稱軸左右依次排開；若饋線段的數(shù)量為偶數(shù)，則緩沖區(qū)中心線上不放置任何饋線段，所有線段以緩沖區(qū)中心線為對稱軸左右依次排開，如圖4所示。

(a)確定前

(b)確定后

在對饋線段進行等間隔重新排序時，首先依照饋線段本來的走向放置，例如向右的出線盡量往右放置以保持原有大致走向不變。但最終決定是向左出線還是向右出線，需左轉(zhuǎn)和右轉(zhuǎn)2次計算來確定，判斷準(zhǔn)則是以零交叉或與其他饋線段出現(xiàn)交叉次數(shù)最少的方向作為出線方向。各饋線段的位置和方向確定后，還需進行拉直處理，將弧段轉(zhuǎn)為線段。偏移后的各切片內(nèi)饋線段如圖5所示。

圖5 偏移操作之后的饋線段

4.2 前向遍歷確定饋線段的連接關(guān)系

由于各饋線段等間隔偏移后，起止點坐標(biāo)相對于原始坐標(biāo)發(fā)生了改變，不能通過判斷首尾節(jié)點坐標(biāo)是否相同的方式來確定饋線段之間的連接關(guān)系。這時需要以緩沖區(qū)中心線為參考確定各饋線段的上下級連接關(guān)系：

1)以變電站作為起點，從與該變電站直接相連的第一個緩沖區(qū)切片QP1開始搜索。設(shè)緩沖區(qū)切片QP1、QP2、QP3的緩沖區(qū)中心線段ID分別為Cen1、Cen2和Cen3，如圖6所示。

圖6 緩沖區(qū)中心線段連接關(guān)系確定

根據(jù)線段索引表查得其起止點分別為[CNode0，CNode1]，[CNode1，CNode2]，[CNode1，CNode3]；CNode0為搜索的起點，查得線段索引表中對應(yīng)的中心線段為Cen1，起止點為[CNode0，CNode1]；接著查詢線段索引表中以CNode1為起點的所有線段，得到QP2中心線段Cen2和QP3中心線段Cen3；繼續(xù)查得線段索引表中Cen2的起止點[CNode1，CNode2]、Cen3的起止點[CNode1，CNode3]。如此找到緩沖區(qū)中心線的第1個交叉點，并找到以該交叉點為中心所劃分的所有緩沖區(qū)切片QP2和QP3，即可知道各饋線的起點在QP1中。QP1內(nèi)各饋線段要么與QP2中饋線段相連，要么與QP3中饋線段相連。

2)查詢各緩沖區(qū)切片內(nèi)所含饋線段。假設(shè)QP1內(nèi)有7條饋線段，QP2內(nèi)有3條饋線段，QP3內(nèi)有4條饋線段，參見圖4(b)。查得QP2、QP1和QP3中包含的饋線段ID分別為[QP2-B-2，QP2-D-2，QP2-E-2]，[QP1-A-1，QP1-B-1，QP1-C-1，QP1-D-1，QP1-E-1，QP1-F-1，QP1-G-1]，[QP3-A-3，QP3-C-3，QP3-F-3，QP3-G-3]。

以QP1中饋線段QP1-A-1為例，搜索到QP3中存在饋線名為A的線段QP3-A-3，表明QP1-A-1應(yīng)與右側(cè)饋線段QP3-A-3相連。同法，饋線段QP1-B-1應(yīng)與左側(cè)饋線段QP2-B-2相連，以此類推，捋出QP1中所有饋線段的下游饋線段后，將連接關(guān)系記錄在節(jié)點索引表(只需記錄該切片內(nèi)各饋線段的每個轉(zhuǎn)折點)和邊表索引中。然后再從QP2開始，以廣度優(yōu)先遍歷的方式“前推”搜索所含所有饋線段的下游連接饋線段，并將連接關(guān)系記錄在節(jié)點索引表和線段索引表中，從Cen2、Cen3至后續(xù)中心線段連接關(guān)系的確定方法與此類似，直至最后一個緩沖區(qū)切片。

3)存儲各緩沖區(qū)切片范圍內(nèi)所有饋線段的新節(jié)點索引表和線段索引表，得到各緩沖區(qū)切片所含所有饋線段的連接關(guān)系后，需要以新的節(jié)點索引表和線段索引表形式存儲各緩沖區(qū)切片范圍內(nèi)所有饋線段的數(shù)據(jù)。

4.3 逐級后向遍歷拼接以形成整條饋線

各饋線段從后往前后向遍歷，根據(jù)各饋線段與其直接相連上游饋線段的連接關(guān)系，對饋線段拼接處理：首先求出交點所在位置(圖5)，再根據(jù)交點的位置對兩饋線段作延長或打斷處理，最后將兩者拼接在一起。但大部分情況下，緩沖區(qū)切片中包含的饋線段需要與2個線段相連，這時需先判斷交點的數(shù)量及位置，屬于同一條饋線的相鄰上下游饋線段一定存在交點；然后根據(jù)交點的不同情況完成饋線段拼接，如圖7所示。設(shè)QP1內(nèi)所有饋線段為1級分支，QP2內(nèi)所有饋線段為2級分支，……，以此類推。

(a)2個n級分支與1個n-1級分支之間有1交點

(b)2個n級分支與1個n-1級分支之間有2交點

(c)1個n級分支與2個n-1級分支之間有3交點

(d)1個n級分支與2個n-1級分支之間有1交點

圖7(a)是2個n級分支(或其延長線)與1個n-1級分支(或其延長線)之間存在1個交點。方法是先找出分支饋線間的交點O，再將2個n級分支均通過交點與n-1級分支相連。

圖7(b)是2個n級分支相互平行且與1個n-1級分支(或其延長線)之間存在2個交點，或2個n級分支(或其延長線)的交點在遠處(例如：距離n-1級分支線5Δ以上，Δ為緩沖區(qū)寬度)存在交點且與1個n-1級分支或其延長線之間各存在1個交點。方法是先分別找出2個n級分支與n-1級分支的交點，將2個n級分支分別通過各自交點與n-1級分支相連，再以其中1個n級分支為基準(zhǔn)將另一個n級分支調(diào)整到與之平行。

圖7(c)是1個n級分支(或其延長線)與2個n-1級分支(或其延長線)之間存在3個交點。B1、B2與C1、C2為2個n-1級分支，A1、A2為n級分支。方法是先構(gòu)造以A1、B1、C2為頂點的三角形，從n級分支頂點A1向底邊B1、C2做垂線，不論垂點O位于該三角形的內(nèi)部還是外部，連接B1、C2作為n-1級分支，連接A1、D作為n級分支。

圖7(d)是1個n級分支(或其延長線)與2個n-1級分支(或其延長線)之間存在1個交點。AD與CD為2個n-1級分支，BD為n級分支。方法是先構(gòu)造以ABC為頂點的三角形，從n級分支頂點B向底邊AC做垂線，垂點為O，連接AO作為n-1級分支，連接BO作為n級分支。

可見，美化的本質(zhì)是將n-1級饋線段或n級饋線段沿原有走向“拉直”，且各饋線段之間盡量少地構(gòu)成銳角。根據(jù)泰森多邊形的性質(zhì)，基于中心線分叉點的每個緩沖區(qū)切片反映了饋線組內(nèi)任意有分支轉(zhuǎn)折饋線的分叉(分支)細節(jié)走向，因此按分叉點逐層分級的拼接構(gòu)圖方法，每次最多有3條饋線段進行拼接，圖7幾乎囊括了所有可能遇到的情況。最終1個n級分支與多個n-1級分支均可簡化為1個n級分支與1個n-1級分支(如圖7(c)、7(d)所示)，多個n級分支與1個n-1級分支均可簡化為n個n級分支與1個n-1級分支(如圖7(a)、(b)所示)。按此方法繼續(xù)從后向前遍歷，直至饋線首端，即可得到拼接和美化后的整條饋線。

如果遇到切片中的饋線段拼接后出現(xiàn)交叉，如圖8所示，則需要從出現(xiàn)交叉的最末一級(假設(shè)為第n級)饋線段開始交換饋線段的排列次序以最大限度減少交叉，然后調(diào)整第n-1級饋線段的排列次序，直至饋線段的首端。

(a)相鄰切片中的饋線段拼接后出現(xiàn)交叉

(b)從最末級開始調(diào)整直到最初級饋線段

5 連接設(shè)備并連接整條饋線

緩沖區(qū)切片中出現(xiàn)的“垂直斷線”并不代表饋線段是斷開的，如圖9中黑色圈所示。

查詢圖9中“垂直斷線”兩側(cè)饋線段的所屬饋線名稱或ID可知，“垂直斷線”是連接到配電設(shè)備的Π接線。只要將此位置處的配電設(shè)備連接到相應(yīng)饋線段中，該饋線段的形態(tài)就表達完整了，故還需要處理設(shè)備的T接和Π接問題。

圖9 緩沖區(qū)切片中的“垂直斷線”

對配電變壓器做T接處理，將其T接在所屬開關(guān)設(shè)備或饋線上；對環(huán)網(wǎng)箱或環(huán)網(wǎng)柜做Π接處理，將其Π接在所屬饋線上；對斷路器或開關(guān)做串接處理，將其串聯(lián)在所屬饋線上。方法是通過從GIS圖獲取的拓撲關(guān)系得到設(shè)備與某饋線段之間的連接關(guān)系或隸屬關(guān)系。若查詢到某設(shè)備與饋線段之間只有1段連接線，認為是T接；若查詢有2段連接線，認為是Π接。

Π接的規(guī)則是在設(shè)備位置已知的情況下，若與任何饋線段重疊或交叉，則需將該設(shè)備依次偏移一定的距離(例如，以該饋線段為基準(zhǔn)向左向右或向上向下偏移0.5Δ、Δ、1.5Δ……)，作為放置該設(shè)備的新位置；并做設(shè)備至該饋線段的垂線，以該垂線為參照分別向兩側(cè)偏移出2條新的垂線，將其作為Π接線，2條Π接線之間的距離為設(shè)備寬度的1/2。T接的規(guī)則是在設(shè)備位置已知的情況下，若與任何饋線段重疊或交叉，則需將該設(shè)備依次偏移一定的距離(例如，以該饋線段為基準(zhǔn)向左右或向上下偏移0.5Δ、1Δ、1.5Δ)，作為放置該設(shè)備的新位置；并做設(shè)備至該饋線段的垂線，以該垂線作為T接線。斷路器或開關(guān)的位置也做類似的處理，不同的是，斷路器或開關(guān)需要放進所屬饋線中。處理方法是以斷路器或開關(guān)圖元寬度方向兩側(cè)的點為斷點將饋線段打斷，再串入饋線中。

環(huán)網(wǎng)柜(箱)、開關(guān)設(shè)備、配電變壓器接入饋線段的處理如圖10所示。

圖10 接入設(shè)備后的饋線段

同一級饋線段的設(shè)備如果出現(xiàn)較多的交叉，則將各饋線設(shè)備按相反的方向交叉排布以盡量減少交叉，如圖11所示。

(a)同一級饋線段的設(shè)備出現(xiàn)交叉

(b)饋線段的設(shè)備按相反的方向交叉排布

實際應(yīng)用中，某變電站經(jīng)美化后的所有饋線如圖12所示。

圖12 某變電站經(jīng)美化后的所有饋線

6 結(jié)語

本文提出基于泰森多邊形的變電站中壓饋線GIS圖美化算法以最遠端最長線路為主干線，以此確定饋線的主體走向；以較短線段作為分支線，以此決定饋線的外觀形狀。采用泰森多邊形算法得到緩沖區(qū)和緩沖區(qū)中心線，從而確定饋線組的走向和范圍；進而以緩沖區(qū)中心線交叉點為基點對廊道進行泰森多邊形切片，并對各切片中的饋線段重新排布，將每條饋線段重新定位。在“前推后代”過程中采用廣度優(yōu)先遍歷和深度優(yōu)先遍歷相結(jié)合的方法，經(jīng)逐層向下和逐層向上兩次排序，確定上下級饋線段的拼接次序；再根據(jù)設(shè)備的隸屬關(guān)系和拓撲連接，將設(shè)備連接到饋線上，得到美化后的整條饋線。美化后的饋線走向與實際基本一致，彌補了傳統(tǒng)算法中饋線走向與實際情況偏離較大的不足。

本文算法簡單易行，對形狀各異的變電站出線均能很好適應(yīng)，可直接應(yīng)用于配電網(wǎng)規(guī)劃工作中。但研究內(nèi)容僅局限于單個變電站的中壓饋線，未涉及所研究區(qū)域中有多個變電站出線且變電站之間存在線路聯(lián)絡(luò)的情況。下一步需根據(jù)多個變電站的布局，通過拓撲關(guān)系計算變電站饋線之間的聯(lián)絡(luò)，以一個供電單元或供電網(wǎng)格為整體進行配電網(wǎng)GIS圖的美化。