基于泰森多邊形的配電網GIS圖美化算法

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

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

0 引言

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

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

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

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

1 算法流程

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

圖1 美化流程

1)以配電網GIS圖為數據源，通過GIS軟件提供的接口程序，提取出GIS圖中各點的坐標數據及相關參數。

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

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

4)根據中心線的分叉點生成各緩沖區切片，形成緩沖區切片與饋線段的包含關系。

5)根據緩沖區中心線的上下游組成線段連接關系，確定以其為中心的各條饋線的上下游連接關系。

6)根據連接關系順次連接各段饋線，根據設備與饋線段的隸屬關系，將相應設備連接至所屬饋線段，從而生成整條饋線。

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

2 預處理

2.1 緩沖區生成

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

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

圖2 某變電站所有饋線的緩沖區

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

2.2 生成緩沖區中心線

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

(a)提取前

(b)提取后

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

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

3 緩沖區切片并形成包含關系

3.1 緩沖區切片

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

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

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

3.2 緩沖區中心線段的表達

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

表1 節點索引表

按中心線段的連接順序將各中心線段編成線段索引表，以存放各切片內中心線段首尾節點的信息。線段索引表的結構見表2。

表2 線段索引表

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

4 確定饋線段的連接關系

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

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

(a)確定前

(b)確定后

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

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

4.2 前向遍歷確定饋線段的連接關系

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

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

圖6 緩沖區中心線段連接關系確定

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

2)查詢各緩沖區切片內所含饋線段。假設QP1內有7條饋線段，QP2內有3條饋線段，QP3內有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應與右側饋線段QP3-A-3相連。同法，饋線段QP1-B-1應與左側饋線段QP2-B-2相連，以此類推，捋出QP1中所有饋線段的下游饋線段后，將連接關系記錄在節點索引表(只需記錄該切片內各饋線段的每個轉折點)和邊表索引中。然后再從QP2開始，以廣度優先遍歷的方式“前推”搜索所含所有饋線段的下游連接饋線段，并將連接關系記錄在節點索引表和線段索引表中，從Cen2、Cen3至后續中心線段連接關系的確定方法與此類似，直至最后一個緩沖區切片。

3)存儲各緩沖區切片范圍內所有饋線段的新節點索引表和線段索引表，得到各緩沖區切片所含所有饋線段的連接關系后，需要以新的節點索引表和線段索引表形式存儲各緩沖區切片范圍內所有饋線段的數據。

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

各饋線段從后往前后向遍歷，根據各饋線段與其直接相連上游饋線段的連接關系，對饋線段拼接處理：首先求出交點所在位置(圖5)，再根據交點的位置對兩饋線段作延長或打斷處理，最后將兩者拼接在一起。但大部分情況下，緩沖區切片中包含的饋線段需要與2個線段相連，這時需先判斷交點的數量及位置，屬于同一條饋線的相鄰上下游饋線段一定存在交點；然后根據交點的不同情況完成饋線段拼接，如圖7所示。設QP1內所有饋線段為1級分支，QP2內所有饋線段為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Δ以上，Δ為緩沖區寬度)存在交點且與1個n-1級分支或其延長線之間各存在1個交點。方法是先分別找出2個n級分支與n-1級分支的交點，將2個n級分支分別通過各自交點與n-1級分支相連，再以其中1個n級分支為基準將另一個n級分支調整到與之平行。

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

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

可見，美化的本質是將n-1級饋線段或n級饋線段沿原有走向“拉直”，且各饋線段之間盡量少地構成銳角。根據泰森多邊形的性質，基于中心線分叉點的每個緩沖區切片反映了饋線組內任意有分支轉折饋線的分叉(分支)細節走向，因此按分叉點逐層分級的拼接構圖方法，每次最多有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)所示)。按此方法繼續從后向前遍歷，直至饋線首端，即可得到拼接和美化后的整條饋線。

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

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

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

5 連接設備并連接整條饋線

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

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

圖9 緩沖區切片中的“垂直斷線”

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

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

環網柜(箱)、開關設備、配電變壓器接入饋線段的處理如圖10所示。

圖10 接入設備后的饋線段

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

(a)同一級饋線段的設備出現交叉

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

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

圖12 某變電站經美化后的所有饋線

6 結語

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

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