基于Voronoi圖的用戶停電區(qū)域可視化方法

夏東風(fēng)

摘要：在當(dāng)前智能配用電系統(tǒng)中，用戶停電區(qū)域大多采用文字描述、表格羅列及一次接線圖等形式進(jìn)行展示，不能直觀的表達(dá)用戶停電區(qū)域的實(shí)際地理位置，該文提出了基于Voronoi圖實(shí)現(xiàn)基于GIS的用戶停電區(qū)域可視化方法，為解決用戶停電區(qū)域自動(dòng)化生成和可視化提供了新的解決思路。經(jīng)過(guò)驗(yàn)證，該方法具有一定的有效性和合理性。

關(guān)鍵詞：停電區(qū)域；Voronoi 圖；計(jì)算幾何；可視化

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）25-0256-02

1引言

隨著社會(huì)和經(jīng)濟(jì)的發(fā)展，用電負(fù)荷持續(xù)增長(zhǎng)，配電網(wǎng)所承受的壓力越來(lái)越大。由于配電網(wǎng)網(wǎng)架復(fù)雜、運(yùn)行環(huán)境開(kāi)放、負(fù)荷大等自身原因，同時(shí)易受雷擊、小動(dòng)物、自然災(zāi)害及設(shè)備老化等因素影響，故障停電難以避免。同時(shí)考慮到用電量需求不斷提升，社會(huì)建設(shè)的多項(xiàng)影響，為了提升供電可靠性和方便配用電網(wǎng)設(shè)計(jì)改造，勢(shì)必進(jìn)行計(jì)劃停電，如何自動(dòng)化生成并直觀的展示停電區(qū)域成為急需解決的問(wèn)題。

當(dāng)前對(duì)于停電區(qū)域生成已經(jīng)有一些研究，如通過(guò)電網(wǎng)拓?fù)渥詣?dòng)化分析停電影響范圍，利用智能電報(bào)故障上報(bào)功能，通過(guò)從用電信息采集系統(tǒng)獲取上報(bào)數(shù)據(jù)進(jìn)行分析和判斷實(shí)現(xiàn)停電范圍定位功能。以上研究均未對(duì)停電范圍直觀可視化提出解決方案，同時(shí)在一些欠發(fā)達(dá)國(guó)家和地區(qū)，配電自動(dòng)化水平較低，難以使用以上方案實(shí)現(xiàn)停電區(qū)域定位和可視化。為了解決以上問(wèn)題，本文提出了基于計(jì)算幾何中定義的Voronoi圖，并結(jié)合地理空間信息系統(tǒng)（GIS），實(shí)現(xiàn)停電區(qū)域生成和可視化的方法，試圖為配用電網(wǎng)停電區(qū)域自動(dòng)化生成和可視化尋求一個(gè)新的途徑。

2 Voronoi圖

Voronoi圖是計(jì)算幾何里的一種解決近鄰性問(wèn)題的幾何結(jié)構(gòu)，也是計(jì)算幾何領(lǐng)域內(nèi)重要研究?jī)?nèi)容之一。最早由荷蘭氣候?qū)W家A.H.Thiessen提出，是一個(gè)根據(jù)離散分布的氣象站的降雨量來(lái)計(jì)算平均降雨量的方法，即將所有的相鄰氣象站連成三角形，做這些三角形的各邊的垂直平分線，于是每個(gè)氣象站的周圍的若干垂直平分線便圍成一個(gè)多邊形，這個(gè)多邊形就是Voronoi圖。Voronoi圖基于離散點(diǎn)劃分這一特性和停電區(qū)域基于停電設(shè)備生成具有相似性。

2.1 Voronoi圖定義和特點(diǎn)

Voronoi圖數(shù)學(xué)定義為：設(shè)p，q是平面上的兩個(gè)點(diǎn)，L是pq的中垂線，L將平面分為兩個(gè)部分【L左】和【L右】，在【L】左內(nèi)的點(diǎn)r有特性|pr|<|qr|，即位于【L左】?jī)?nèi)的點(diǎn)比平面其他點(diǎn)更接近p，不妨記H（p，q）=【L左】，同理H（q，p）=【L右】，給定平面上n個(gè)點(diǎn)的點(diǎn)集S={p1，p2，……pn}。定義V（pi）是所有j（i！=j）的H（pi，pj）的交集，即V（pi）表示比其他點(diǎn)更接近于pi的電的軌跡是n-1個(gè)半平面的交，這是一個(gè)不多于n-1條邊的凸多邊形區(qū)域，稱為關(guān)聯(lián)于pi的Voronoi多邊形（域）。

綜合已有的Voronoi研究文獻(xiàn)，可以歸納出Voronoi圖的具有如下特點(diǎn)：

1）以離散點(diǎn)為中心，將平面劃分成若干個(gè)Voronoi圖，每個(gè)Voronoi圖只包含一個(gè)離散點(diǎn)，Voronoi圖內(nèi)所有點(diǎn)到離散點(diǎn)的距離比到其他離散點(diǎn)的距離都小；

2）Voronoi圖的邊是某對(duì)離散點(diǎn)的中垂線的一個(gè)線段或者射線，位于平面邊界的Voronoi圖可能難以閉合，

3）Voronoi圖至多有2*n-5個(gè)頂點(diǎn)和3*n-6條邊，Voronoi點(diǎn)恰好是三條Voronoi邊的交點(diǎn)（假如任何四點(diǎn)都不共圓的話）。也就是說(shuō)Voronoi點(diǎn)就是形成三邊的三點(diǎn)的外界圓圓心，而且所有的這些外界圓有個(gè)特點(diǎn)：各自內(nèi)部不含任何平面點(diǎn)集的點(diǎn)（空心圓）。

2.2常見(jiàn)應(yīng)用和生成方法

Voronoi圖在多邊形剖分、幾何搜索、多邊形求交、可見(jiàn)性計(jì)算、路徑規(guī)劃、碰撞檢測(cè)、骨架計(jì)算、文獻(xiàn)特征提取、半色調(diào)圖像生成以及信息可視化等方面都有一些成熟的應(yīng)用，Voronoi圖和電力行業(yè)相結(jié)合的研究有很多，但主要集中在輸電網(wǎng)中變電站選址規(guī)劃方面， 用戶停電區(qū)域劃分和顯示方面的應(yīng)用較少。

已知的Voronoi圖的矢量生成方法有很多種， 常見(jiàn)的生成方法有增量法、分治法、并行法和間接法等四種，由于基于停電設(shè)備生成停電區(qū)域時(shí)，并無(wú)法確定V圖的已知頂點(diǎn)，因此前三種根據(jù)已知頂點(diǎn)直接生成頂點(diǎn)Voronoi圖的方式并不適用于這個(gè)場(chǎng)景； 而間接法是先生成Voronoi圖的對(duì)偶Delaunay三角網(wǎng)， 然后生成Voronoi圖，因此本文則采用了間接法生成Voronoi圖。

3停電區(qū)域生成

當(dāng)發(fā)生停電時(shí)，根據(jù)停電設(shè)備信息獲取設(shè)備坐標(biāo)、結(jié)合設(shè)備供電半徑計(jì)算停電設(shè)備離散點(diǎn)的最小外包矩形，根據(jù)在電力空間信息系統(tǒng)中格局矩形范圍獲取矩形內(nèi)所有設(shè)備計(jì)算Voronoi圖。查找停電設(shè)備所在的Voronoi圖，并著色顯示。

3.1凸包構(gòu)建

輸入停電設(shè)備坐標(biāo)到電力空間信息系統(tǒng)中，根據(jù)停電設(shè)備坐標(biāo)計(jì)算出包含停電設(shè)備的最小矩形區(qū)域，由于Voronoi圖特點(diǎn)（參考本文2.1），位于邊界的離散點(diǎn)生成多邊形邊界區(qū)域的圖形可能難以閉合，因此需要將最目標(biāo)區(qū)域按停電設(shè)備的供電半徑進(jìn)行擴(kuò)大，在擴(kuò)大后的目標(biāo)區(qū)域內(nèi)進(jìn)行空間查詢，獲取區(qū)域內(nèi)所有的設(shè)備的坐標(biāo)信息，構(gòu)建初始的電力設(shè)備坐標(biāo)點(diǎn)集。

求出電力設(shè)備坐標(biāo)點(diǎn)集中滿足min（x-y）、min（x+y）、max（x-y）、max（x+y）的四個(gè)點(diǎn)，并按逆時(shí)針?lè)较蚪M成一個(gè)點(diǎn)的多邊形。這4個(gè)點(diǎn)是電力設(shè)備坐標(biāo)點(diǎn)集中與包含電力設(shè)備坐標(biāo)點(diǎn)的外接矩形的4個(gè)角點(diǎn)最近的點(diǎn)。這4個(gè)點(diǎn)構(gòu)成的多邊形作為初始凸包。初始凸包構(gòu)建完成后，按以下步驟處理不在凸包內(nèi)的電力設(shè)備坐標(biāo)點(diǎn)：

1）設(shè)初始凸包上的電力設(shè)備坐標(biāo)點(diǎn)為p，它的后續(xù)點(diǎn)為q，計(jì)算矢量線段pq右側(cè)的所有點(diǎn)到矢量線段pq的距離，并求出距離最大的電力設(shè)備坐標(biāo)點(diǎn)o。

2）將最大的電力設(shè)備坐標(biāo)點(diǎn)o插入p、q之間，并將o賦給q。

3）重復(fù)第一、二步，直到電力設(shè)備坐標(biāo)點(diǎn)集中沒(méi)有在矢量線段pq右側(cè)的點(diǎn)為止。

4）將q賦給p，q取其后續(xù)點(diǎn)，重復(fù)第一、二、三步。

5）當(dāng)初始凸包中任意相鄰兩點(diǎn)連線的右側(cè)不存在電力設(shè)備坐標(biāo)點(diǎn)時(shí)，結(jié)束電力設(shè)備坐標(biāo)點(diǎn)集凸包求取過(guò)程。完成這一步后，形成了包含所有電力設(shè)備坐標(biāo)點(diǎn)集的凸包。

3.2三角網(wǎng)構(gòu)建

凸包構(gòu)建完成后，在凸包的基礎(chǔ)上進(jìn)行三角網(wǎng)構(gòu)建，方法為：循環(huán)位于凸包邊上的點(diǎn)，查找由相鄰兩個(gè)凸包邊組成的三角形，如果該三角形內(nèi)部和邊界上都不包含其他不在凸包變邊上的點(diǎn)，則將這個(gè)三角形的點(diǎn)從凸包點(diǎn)集合中去掉，重復(fù)這個(gè)過(guò)程直到凸包邊上的點(diǎn)都形成三角形。

對(duì)凸包進(jìn)行三角網(wǎng)構(gòu)建的初步過(guò)程結(jié)束之后，采用逐點(diǎn)內(nèi)插的方法對(duì)不在凸包上的其余離散點(diǎn)進(jìn)行剖分?；静襟E為：

1）獲取一個(gè)沒(méi)有構(gòu)成三角形的電力設(shè)備坐標(biāo)點(diǎn)

2）在已經(jīng)生成的三角形中，找到包含電力設(shè)備坐標(biāo)點(diǎn)的三角形或者電力設(shè)備坐標(biāo)點(diǎn)和三角形邊相交的三角形。

3）如果電力設(shè)備坐標(biāo)點(diǎn)在三角形的內(nèi)部，則將該三角形以及三角形的邊刪除，然后將三個(gè)頂點(diǎn)以及電力設(shè)備坐標(biāo)點(diǎn)分別連接，形成三個(gè)新的三角形。如果電力設(shè)備坐標(biāo)點(diǎn)在三角形的邊上，刪除改邊和左右相鄰的三角形，對(duì)產(chǎn)生的電力設(shè)備坐標(biāo)點(diǎn)重新連接。

4）對(duì)于新生成的三角形的每個(gè)邊進(jìn)行空外接圓檢測(cè)。具體步驟為：找出三角形的邊相鄰的兩個(gè)三角形，如果該邊一側(cè)的對(duì)角的頂點(diǎn)位于另外一個(gè)三角形的外接圓的里面，則將兩個(gè)對(duì)角連接起來(lái)，拆分為兩個(gè)新的三角形。對(duì)于拆分出的三角形的邊，也需要進(jìn)行空外接圓檢測(cè)。如此重復(fù)執(zhí)行，直到所有生成的三角形都通過(guò)空外接圓檢測(cè)為止。

重復(fù)執(zhí)行上述四步，直到所有不在凸包上的其余電力設(shè)備坐標(biāo)點(diǎn)都插入完為止，從而完成三角網(wǎng)的構(gòu)建。

3.3 Voronoi圖構(gòu)建

將三角網(wǎng)和構(gòu)成三角網(wǎng)的電力設(shè)備坐標(biāo)點(diǎn)進(jìn)行編號(hào)，記錄每個(gè)三角形是由哪三個(gè)電力設(shè)備坐標(biāo)點(diǎn)構(gòu)成的。找出三角網(wǎng)中具有相同頂點(diǎn)的所有三角形，并記錄三角形編號(hào)。逆時(shí)針?lè)较驅(qū)εc每個(gè)電力設(shè)備坐標(biāo)點(diǎn)相鄰的三角形進(jìn)行排序，便于下一步連接生成Voronoi圖。計(jì)算排序后的每個(gè)三角形的外接圓圓心，并編號(hào)。第獲取每個(gè)電力設(shè)備坐標(biāo)點(diǎn)的相鄰三角形，連接這些相鄰三角形的外接圓圓心，得到Voronoi圖。

3.4可視化

通過(guò)設(shè)備圖層和Voronoi圖生成圖層進(jìn)行疊置分析，生成停電范圍，以轄區(qū)范圍內(nèi)的建筑物圖層作為數(shù)據(jù)源，利用獲得的建筑物坐標(biāo)信息構(gòu)建建筑物地理對(duì)象，并在地圖上顯示勾勒出建筑物范圍，從而獲得用戶停電區(qū)域建筑物范圍。其中在GIS地圖顯示控件上勾勒出的建筑物范圍可以以高亮狀態(tài)顯示，從而直觀地向用戶展示停電區(qū)域。

4應(yīng)用實(shí)例

本文肯尼亞內(nèi)羅畢某城區(qū)配變?yōu)槔?實(shí)現(xiàn)了新增配變的自動(dòng)定位和供電區(qū)域的自動(dòng)最優(yōu)劃分。以現(xiàn)有配變的位置為Delaunay三角網(wǎng)的頂點(diǎn)， 生成Delaunay三角網(wǎng)（虛線） ，以Voronoi圖實(shí)現(xiàn)的供電區(qū)域劃分（實(shí)線） 。根據(jù)Voronoi圖的性質(zhì)， Voronoi圖中的結(jié)點(diǎn)均為其對(duì)應(yīng)的D三角形的外接圓的圓心， 即新增配變的備選位置； 根據(jù)該規(guī)劃區(qū)域的負(fù)荷預(yù)測(cè)和電力電量平衡結(jié)果， 需新增250kVA配變4臺(tái)；按照上述思路， 新增配變的位置及供電區(qū)域的重新劃分結(jié)果如下圖所示。

5結(jié)論

本文基于GIS和Vorono圖的相關(guān)特性實(shí)現(xiàn)停電范圍的自動(dòng)生成和停電區(qū)域的可視化顯示， 提供了一種基于GIS的用戶停電范圍生成和可視化方法， 算例結(jié)果表明了這種嘗試的有效性和合理性。解決供電企業(yè)在停電管理工作過(guò)程中無(wú)法直觀了解停電范圍的不足，實(shí)現(xiàn)了停電范圍的自動(dòng)生成與直觀展示，幫助了停電搶修人員對(duì)停電區(qū)域的準(zhǔn)確定位、提升了搶修效率、從而提供了電可靠性，具有產(chǎn)業(yè)上的利用價(jià)值。

參考文獻(xiàn)：

[1] 陳曉沾.10kV配網(wǎng)故障停電原因分析及解決對(duì)策分析[J].中國(guó)科技縱橫，2015（9）：155-155.

[2] 馬樂(lè).加強(qiáng)配電網(wǎng)計(jì)劃停電管理，提高電網(wǎng)供電可靠性[J].工業(yè)，2016（9）：00174-00174.

[3] 李云峰，毛欣，劉家權(quán)，等.基于營(yíng)配調(diào)貫通的停電影響范圍分析方法及其應(yīng)用[J].科技經(jīng)濟(jì)導(dǎo)刊， 2017（11）.

[4] 陳文斌，段小紅，章瑩.基于用電信息采集系統(tǒng)的突發(fā)停電范圍定位系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].電子制作， 2014（24）：100-100.

[5] 周培德.計(jì)算幾何：算法設(shè)計(jì)與分析[M].4版.北京：清華大學(xué)出版社，2011.

[6] 阿蘇外耶.算法設(shè)計(jì)技巧與分析[M].北京：電子工業(yè)出版社，2004.

[7] 楊承磊.Voronoi圖及其應(yīng)用[M].北京：清華大學(xué)出版社，2013.

[8] 葛少云，李慧，劉洪.基于加權(quán)Voronoi圖的變電站優(yōu)化規(guī)劃[J].電力系統(tǒng)自動(dòng)化，2007，31（3）：29-34.

[9] 王靜娜.配電變壓器選址優(yōu)化模型研究及系統(tǒng)開(kāi)發(fā)[D].西南大學(xué)，2012.

[10] 陳軍.Voronoi動(dòng)態(tài)空間數(shù)據(jù)模型[M].北京：測(cè)繪出版社，2002.

【通聯(lián)編輯：朱寶貴】