多边形裁剪算法在电力系统中的应用

摘 要：文章主要研究多边形裁剪的Weiler-Atherton 算法，相对于其他算法，Weiler-Atherton 算法既适用于裁剪窗口为凸区域的模型，也适用于裁剪窗口为凹区域的模型。通过分析多边形裁剪算法的特点，结合现代电力系统的发展，合一实时准确的选择合理的算法，进而为现代电力仿真分析和电力信息化奠定良好的基础。

关键词：电力信息化；多边形裁剪算法；电力仿真

随着电力系统的发展，我国电网逐渐向大电网，大容量，高电压等级发展。对电力系统海量数据实现准确、高效的管理、分析和显示是电力系统信息化建设中的核心，同时也为其它新技术应用于电力系统奠定了基础。实现电力系统数据信息高效准确地管理，将有助于电力系统的实时监控、分析计算、模拟仿真、信息管理等。计算机图形学具有形象的面向对象管理电力元件图形实体，使其迅速受到电力系统中各种应用分析软件的青睐。借助计算机图形技术来实现数据系统发送消息而作出不同的反应机制，不同的消息激发不同的信息的表达，可以大大降低系统工作人员在的工作量，提高工作效率。图形窗口管理器主要在于管理所有电力系统图形对象的显示结果时保证工作的可靠性，为保障电力系统运行的安全稳定提供了重要的技术支撑。

在图形系统中，二维裁剪是最为基础、最为常用的操作之一，其典型的应用是在图形的消隐处理等各种三维图形的处理以及各种排料算法求交操作之中，如图形消陷、缩放、模式识别、导线和元件布局、线性规划以及电力系统计算机辅助设计各种电力器件，线路布局等，特别是各类型基础工程量的计算中都会广泛地应用多边形裁剪法。目前，对裁剪算法的研究主要集中在裁剪直线和裁剪多边形两方面。在实用中，与直线剪裁相比，多边形裁剪具有更高的使用频率，并且多边形愈复杂其裁剪算法就愈难以实现。

本文主要研究多边形裁剪的Weiler-Atherton 算法，相对于其他算法，Weiler- Atherton 算法既适用于裁剪窗口为凸区域的模型，也适用于裁剪窗口为凹区域的模型。通过分析多边形裁剪算法的特点，结合现代电力系统的发展，合一实时准确的选择合理的算法，进而为现代电力仿真分析和电力信息化奠定良好的基础。

1 Weiler-Atherton算法

Weilerr-Atherton算法的基本思想是：根据多边形处理方向（顺时针/逆时针）和当前处理的多边形顶点对是由外到内，还是由内到外来确定裁剪后多边形的顶点连接方式：沿着多边形边界方向连接；还是沿着窗口边界方向连接。如果顺时针处理顶点，则采用下列规则：

对由外到内的顶点对（交点为进点），沿着多边形边界的方向连接。对由内到外的顶点对（交点为出点），按顺时针沿着窗口边界的方向连接。

实现步骤：（1）建立多边形和裁剪窗口的顶点表；（2）求出多边形与窗口的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边形顶点表中的相同交点间建立双向指针。（3）建立空的裁剪结果多边形的顶点表。选取任一没有被跟踪过的交点为起点，将其输出到结果多边形顶点表中：如果该交点为进点，跟踪多边形边界；否则，跟踪窗口边界（顶点表）。跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点。将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向。如果上一步跟踪的是多边形边界，改为跟踪窗口边界；反之，改为跟踪窗口边界。（4）重复前两步，直到回到起点。

图1 Weiler- Atherton算法步骤

2 直线裁剪的基本原理

如图所示的为直线与窗口边界之间可能出现的几种关系。可以通过检查直线的两个端点是否在窗口之内确定如何对此直线裁剪。如果一直线的两个端点均在窗口边界之内（如图2中P5到P6的直线），则此直线应保留。如果一条直线的一个端点在窗口外（如P9）另一个点在窗口内（如P10），则应从直线与边界的交（P9处裁剪掉边界之外的线段。如果直线的两个端点均在边界外，则可分为两种情况：一种情况是该直线全部在窗口之外；另一种情况是直线穿过两个窗口边界。图中从P3到P4的直线属于前一种情况，应全部裁剪掉；从P7到P8的直线属于后一种情况，应保留P7到P8的线段，其余部分均裁剪掉。

图2 直线相对于窗口边界的栽剪

直线裁剪算法应首先确定哪些直线全部保留或全部裁剪，剩下的即为部分裁剪的直线。对于部分裁剪的直线则首先要求出这些直线与窗口边界的交点，把从交点开始在边界外的部分裁剪掉。一个复杂的画面中可能包含有几千条直线，为了提高算法效率，加快裁剪速度，应当采用计算量较小的算法求直线与窗口边界的交点。

Liang-Barsky算法：Liang（梁友栋）-Barsky算法又称为参数方程法。首先写出端点（x1，y1）及（x2，y2）之间连线的参数方程如下：

（1）

（2）

其中，。参数u可取0 1之间的值，坐标（x，y）表示此范围内的u值定义的直线上的一个点。当u=0时，（x，y）=（x1，y1），直线的另一端u=0时，（x，y）=（x2，y2）。

我们发现，如果直线上的某点处于（x，y）及（xwmin，ywmin）及（xwmax，ywmax）所定义的窗口之内，则满足以下条：

xwmin≤x1+Δxu≤xwmax （3）

ywmin≤y1+Δyu≤ywmax （4）

这四个不等式可以表示为：

upk≤qk， k=1，2，3，4 （5）

其中，参数 定义为；

p1=-Δx， q1=x1-xwmin （6）

p2=-Δx， q2=xwmax-x1 （7）

p3=-Δy， q3=y1-ywmin （8）

p4=-Δy， q4=ywmax-y1 （9）

3 结语

本文深入研究了多边形裁剪算法，给出了算法的基本思想以及实现步骤，并分析了Weilerr-Atherton算法的实际应用特点。Weilerr-Atherton算法是计算机图形学技术快速发展的新技术，随着它的广泛、深入地应用到电力系统中，可以增强电力仿真系统显示结果的真实感，实现直观快捷的仿真操作以及提高对仿真结果的处理、显示和分析功能。而且通常在仿真系统中，有时需要对系统进行建模，这就要求计算机图形学能够提供足够类型的图元模型以现实系统模型的搭建，方便的图元模型自定义和扩充将使软件应用得更为方便，而美观逼真的画面以及不同动、静态效果的定制也给操作以良好的视觉帮助。因此，Weilerr-Atherton算法可以为电力系统实现智能化和自动化奠定坚实的基础，为电网的控制、实时化管理、生产、决策各个环节提供了高效、准确的信息资源，这也是发展智能电网的要求。

参考文献

[1] 杨维芳.两个复杂多边形求交的矢量算法[J].兰州铁道学院学报，2002（01）.

[2] 吴兵，尹伟强.具有拓扑关系的任意多边形裁剪算法[J].小型微型计算机系统，2000（01）.

[3] 王浩，姚长利.一个有效的多边形裁剪算法研究[J].软件学报，2003.

[4] Sutherland Ivan E；Hodgman Gary W. “Reentrant polygon clipping，” Communications of the ACM.Vol.17，1974.

[5] Andree V K D. “Algorithm for Clipping Arbitrary Polygons，” Computer Graphics Forum，1989.

[6] 杜月云.多边形裁剪的一种快速算法[J].计算机应用与软件，2009.

作者简介：杨俊（1983.08- ），男，甘肃电力科学研究院电源技术中心，工程师，主要从事电力系统、新能源发电设备安装、调试和试验的检测和研究工作。