基于Voronoi图的用户停电区域可视化方法

夏东风

摘要：在当前智能配用电系统中，用户停电区域大多采用文字描述、表格罗列及一次接线图等形式进行展示，不能直观的表达用户停电区域的实际地理位置，该文提出了基于Voronoi图实现基于GIS的用户停电区域可视化方法，为解决用户停电区域自动化生成和可视化提供了新的解决思路。经过验证，该方法具有一定的有效性和合理性。

关键词：停电区域；Voronoi 图；计算几何；可视化

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）25-0256-02

1引言

随着社会和经济的发展，用电负荷持续增长，配电网所承受的压力越来越大。由于配电网网架复杂、运行环境开放、负荷大等自身原因，同时易受雷击、小动物、自然灾害及设备老化等因素影响，故障停电难以避免。同时考虑到用电量需求不断提升，社会建设的多项影响，为了提升供电可靠性和方便配用电网设计改造，势必进行计划停电，如何自动化生成并直观的展示停电区域成为急需解决的问题。

当前对于停电区域生成已经有一些研究，如通过电网拓扑自动化分析停电影响范围，利用智能电报故障上报功能，通过从用电信息采集系统获取上报数据进行分析和判断实现停电范围定位功能。以上研究均未对停电范围直观可视化提出解决方案，同时在一些欠发达国家和地区，配电自动化水平较低，难以使用以上方案实现停电区域定位和可视化。为了解决以上问题，本文提出了基于计算几何中定义的Voronoi图，并结合地理空间信息系统（GIS），实现停电区域生成和可视化的方法，试图为配用电网停电区域自动化生成和可视化寻求一个新的途径。

2 Voronoi图

Voronoi图是计算几何里的一种解决近邻性问题的几何结构，也是计算几何领域内重要研究内容之一。最早由荷兰气候学家A.H.Thiessen提出，是一个根据离散分布的气象站的降雨量来计算平均降雨量的方法，即将所有的相邻气象站连成三角形，做这些三角形的各边的垂直平分线，于是每个气象站的周围的若干垂直平分线便围成一个多边形，这个多边形就是Voronoi图。Voronoi图基于离散点划分这一特性和停电区域基于停电设备生成具有相似性。

2.1 Voronoi图定义和特点

Voronoi图数学定义为：设p，q是平面上的两个点，L是pq的中垂线，L将平面分为两个部分【L左】和【L右】，在【L】左内的点r有特性|pr|<|qr|，即位于【L左】内的点比平面其他点更接近p，不妨记H（p，q）=【L左】，同理H（q，p）=【L右】，给定平面上n个点的点集S={p1，p2，……pn}。定义V（pi）是所有j（i！=j）的H（pi，pj）的交集，即V（pi）表示比其他点更接近于pi的电的轨迹是n-1个半平面的交，这是一个不多于n-1条边的凸多边形区域，称为关联于pi的Voronoi多边形（域）。

综合已有的Voronoi研究文献，可以归纳出Voronoi图的具有如下特点：

1）以离散点为中心，将平面划分成若干个Voronoi图，每个Voronoi图只包含一个离散点，Voronoi图内所有点到离散点的距离比到其他离散点的距离都小；

2）Voronoi图的边是某对离散点的中垂线的一个线段或者射线，位于平面边界的Voronoi图可能难以闭合，

3）Voronoi图至多有2*n-5个顶点和3*n-6条边，Voronoi点恰好是三条Voronoi边的交点（假如任何四点都不共圆的话）。也就是说Voronoi点就是形成三边的三点的外界圆圆心，而且所有的这些外界圆有个特点：各自内部不含任何平面点集的点（空心圆）。

2.2常见应用和生成方法

Voronoi图在多边形剖分、几何搜索、多边形求交、可见性计算、路径规划、碰撞检测、骨架计算、文献特征提取、半色调图像生成以及信息可视化等方面都有一些成熟的应用，Voronoi图和电力行业相结合的研究有很多，但主要集中在输电网中变电站选址规划方面， 用户停电区域划分和显示方面的应用较少。

已知的Voronoi图的矢量生成方法有很多种， 常见的生成方法有增量法、分治法、并行法和间接法等四种，由于基于停电设备生成停电区域时，并无法确定V图的已知顶点，因此前三种根据已知顶点直接生成顶点Voronoi图的方式并不适用于这个场景； 而间接法是先生成Voronoi图的对偶Delaunay三角网， 然后生成Voronoi图，因此本文则采用了间接法生成Voronoi图。

3停电区域生成

当发生停电时，根据停电设备信息获取设备坐标、结合设备供电半径计算停电设备离散点的最小外包矩形，根据在电力空间信息系統中格局矩形范围获取矩形内所有设备计算Voronoi图。查找停电设备所在的Voronoi图，并着色显示。

3.1凸包构建

输入停电设备坐标到电力空间信息系统中，根据停电设备坐标计算出包含停电设备的最小矩形区域，由于Voronoi图特点（参考本文2.1），位于边界的离散点生成多边形边界区域的图形可能难以闭合，因此需要将最目标区域按停电设备的供电半径进行扩大，在扩大后的目标区域内进行空间查询，获取区域内所有的设备的坐标信息，构建初始的电力设备坐标点集。

求出电力设备坐标点集中满足min（x-y）、min（x+y）、max（x-y）、max（x+y）的四个点，并按逆时针方向组成一个点的多边形。这4个点是电力设备坐标点集中与包含电力设备坐标点的外接矩形的4个角点最近的点。这4个点构成的多边形作为初始凸包。初始凸包构建完成后，按以下步骤处理不在凸包内的电力设备坐标点：

1）设初始凸包上的电力设备坐标点为p，它的后续点为q，计算矢量线段pq右侧的所有点到矢量线段pq的距离，并求出距离最大的电力设备坐标点o。

2）将最大的电力设备坐标点o插入p、q之间，并将o赋给q。

3）重复第一、二步，直到电力设备坐标点集中没有在矢量线段pq右侧的点为止。

4）将q赋给p，q取其后续点，重复第一、二、三步。

5）当初始凸包中任意相邻两点连线的右侧不存在电力设备坐标点时，结束电力设备坐标点集凸包求取过程。完成这一步后，形成了包含所有电力设备坐标点集的凸包。

3.2三角网构建

凸包构建完成后，在凸包的基础上进行三角网构建，方法为：循环位于凸包边上的点，查找由相邻两个凸包边组成的三角形，如果该三角形内部和边界上都不包含其他不在凸包变边上的点，则将这个三角形的点从凸包点集合中去掉，重复这个过程直到凸包边上的点都形成三角形。

对凸包进行三角网构建的初步过程结束之后，采用逐点内插的方法对不在凸包上的其余离散点进行剖分。基本步骤为：

1）获取一个没有构成三角形的电力设备坐标点

2）在已经生成的三角形中，找到包含电力设备坐标点的三角形或者电力设备坐标点和三角形边相交的三角形。

3）如果电力设备坐标点在三角形的内部，则将该三角形以及三角形的边删除，然后将三个顶点以及电力设备坐标点分别连接，形成三个新的三角形。如果电力设备坐标点在三角形的边上，删除改边和左右相邻的三角形，对产生的电力设备坐标点重新连接。

4）对于新生成的三角形的每个边进行空外接圆检测。具体步骤为：找出三角形的边相邻的两个三角形，如果该边一侧的对角的顶点位于另外一个三角形的外接圆的里面，则将两个对角连接起来，拆分为两个新的三角形。对于拆分出的三角形的边，也需要进行空外接圆检测。如此重复执行，直到所有生成的三角形都通过空外接圆检测为止。

重复执行上述四步，直到所有不在凸包上的其余电力设备坐标点都插入完为止，从而完成三角网的构建。

3.3 Voronoi图构建

将三角网和构成三角网的电力设备坐标点进行编号，记录每个三角形是由哪三个电力设备坐标点构成的。找出三角网中具有相同顶点的所有三角形，并记录三角形编号。逆时针方向对与每个电力设备坐标点相邻的三角形进行排序，便于下一步连接生成Voronoi图。计算排序后的每个三角形的外接圆圆心，并编号。第获取每个电力设备坐标点的相邻三角形，连接这些相邻三角形的外接圆圆心，得到Voronoi图。

3.4可视化

通过设备图层和Voronoi图生成图层进行叠置分析，生成停电范围，以辖区范围内的建筑物图层作为数据源，利用获得的建筑物坐标信息构建建筑物地理对象，并在地图上显示勾勒出建筑物范围，从而获得用户停电区域建筑物范围。其中在GIS地图显示控件上勾勒出的建筑物范围可以以高亮状态显示，从而直观地向用户展示停电区域。

4应用实例

本文肯尼亚内罗毕某城区配变为例， 实现了新增配变的自动定位和供电区域的自动最优划分。以现有配变的位置为Delaunay三角网的顶点， 生成Delaunay三角网（虚线） ，以Voronoi图实现的供电区域划分（实线） 。根据Voronoi图的性质， Voronoi图中的结点均为其对应的D三角形的外接圆的圆心， 即新增配变的备选位置； 根据该规划区域的负荷预测和电力电量平衡结果， 需新增250kVA配变4台；按照上述思路， 新增配变的位置及供电区域的重新划分结果如下图所示。

5结论

本文基于GIS和Vorono图的相关特性实现停电范围的自动生成和停电区域的可视化显示， 提供了一种基于GIS的用户停电范围生成和可视化方法， 算例结果表明了这种尝试的有效性和合理性。解决供电企业在停电管理工作过程中无法直观了解停电范围的不足，实现了停电范围的自动生成与直观展示，帮助了停电抢修人员对停电区域的准确定位、提升了抢修效率、从而提供了电可靠性，具有产业上的利用价值。

参考文献：

[1] 陈晓沾.10kV配网故障停电原因分析及解决对策分析[J].中国科技纵横，2015（9）：155-155.

[2] 马乐.加强配电网计划停电管理，提高电网供电可靠性[J].工业，2016（9）：00174-00174.

[3] 李云峰，毛欣，刘家权，等.基于营配调贯通的停電影响范围分析方法及其应用[J].科技经济导刊， 2017（11）.

[4] 陈文斌，段小红，章莹.基于用电信息采集系统的突发停电范围定位系统的设计与实现[J].电子制作， 2014（24）：100-100.

[5] 周培德.计算几何：算法设计与分析[M].4版.北京：清华大学出版社，2011.

[6] 阿苏外耶.算法设计技巧与分析[M].北京：电子工业出版社，2004.

[7] 杨承磊.Voronoi图及其应用[M].北京：清华大学出版社，2013.

[8] 葛少云，李慧，刘洪.基于加权Voronoi图的变电站优化规划[J].电力系统自动化，2007，31（3）：29-34.

[9] 王静娜.配电变压器选址优化模型研究及系统开发[D].西南大学，2012.

[10] 陈军.Voronoi动态空间数据模型[M].北京：测绘出版社，2002.

【通联编辑：朱宝贵】