海量矢量图形在非自交多边形边界中的裁剪显示

李清艳 傅自钢

摘要：该文介绍和研究海量矢量图形在非自交多边形边界中的裁剪显示图形。程序采用快速排斥试验，跨立试验等算法实时高效地计算矢量图形与非矩形且非自交的凸多边形及凹多边形区域的交点，判断图形的哪些部分在多边形边界内部，哪些部分在多边形边界外部，同时能正确显示位于多边形边界内部的图形部分，不显示位于多边形边界外部的图形部分。最终实现当有百万级的line和circle需要裁剪显示时，统计的完成裁剪显示的时间不超过10s，存储器占用不超过100MB 的效果。

关键词：非自交多边形；裁剪；算法；海量矢量图形

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）31-0168-02

Mass Vector Graphics in a Non-Self-Intersections Clipping in the Polygon Boundary Display

LI Qing- yan， FU Zi-gang

（Hunan Agricultural University Information Institute of Science and Technology， Changsha 410128， China）

Abstract ：This article describes and research mass vector graphics in a non-self-intersections polygon boundary clipping in the display graphics. Using of the quick test procedures， straddling the exclusion pilot algorithms such as effective， real-time computing vector graphics and non-rectangular and non-cross the convex hull polygon regions， and the intersection of the judgment which parts of the graphics in the polygon boundary in which parts of the inside of the polygon boundary and at the same time to display correctly on the polygon boundary in the graphical part of the internal， do not display on the outside of the polygon boundary Graphical sections. The final realization of the millions of when a line to be cropped and circle displayed， the completion of the statistics displayed in the crop time should not exceed 10s， memory utilization not to exceed 100MB.

Key words：Non-self-intersections ； polygon ； clipping ； Algorithm，Mass vector graphics

图形的裁剪是计算机图形学中许多重要问题的基础，裁剪的应用有：从定义的场景中抽取出用于观察的部分；在三维视图中标识出可见面；允许选择图形的一部分来进行拷贝，移动或删除等绘图操作。裁剪对象可以是二维的点，线段或者是封闭的多边形，也可以是三维的多面体。在二维图像裁剪中，线段裁剪是最基本的内容，很多适用于二维线段裁剪的算法通过扩展同样都可以用来处理多边形的裁剪。因此选择二维图形裁剪作为研究课题在图形裁剪领域有重要的意义。

1 算法描述

1.1利用快速排斥试验算法判断线段与多边形的关系

假设多边形的顶点为[Pi]的n次方，[i=0]，其中[Pi]=[Pix，Piy]，[P0=Pn]，裁剪线段为[L]，它的两个端点分别为A和B。用[Ax，Ay]，[Bx，By]分别表示A和B点的x，y坐标。用快速排斥试验的方法判断是否完全不可见，即判断A和B是否落在多边形[P0，P1，…，Pn]包围盒的同一侧，记为公式（1）

[Xmin=minPix0≤i≤nYmin=minPiy0≤i≤n][Xmax=maxPix0≤i≤nYmax=maxPiy0≤i≤n] （1）

若[Ax]和[Bx和[Bx>Xmax]，或和[By>Ymax]，则为完全不可见线段且与多边形没有交点。若用快速排斥试验不能确定是否可见，则[Xmax=maxPix0≤i≤n；]继续进行运算。若判断出被裁剪线段是否完全不可见，则求出被裁剪线段与多边形窗口边界的真实交点。对求出的所有真实交点和被裁剪线段的端点同时排序，根据排序的结果将被裁剪线段分成若干条子线段，然后选择线段的一个端点判断该端点是否在多边形内。若在多边形之内，表明奇数点到偶数点间的线段在多边形内且显示，偶数点到奇数点间的线段不显示。若该端点在多边形之外，表明奇数点到偶数点间的线段不在多边形内且不显示。

1.2跨立试验算法研究

设以线段[P1P2]为对角线的矩形为R，设以线段[Q1Q2]为对角线的矩形为T.若两线段相交，则两线段必然相互跨立对方。若跨立，则矢量[P1-Q1]和[P2-Q1]位于矢量[Q2-Q1]的两侧，得出：

[P1-Q1×Q2-Q1×P2-Q1×Q2-Q1<0]，将其改写成：

[P1-Q1×Q2-Q1×Q2-Q1P2-Q1>0]

当[P1-Q1×Q2-Q1=0]时，说明和[Q2-Q1]共线，由快速排斥试验分析得知[P1]一定在线段[Q1Q2]上，同理[Q2-Q1×P2-Q1=0]，说明 P2 一定在线段[Q1Q2]上，判断[P1P2]跨立[Q1Q2]的依据是

[P1-Q1×Q2-Q1×Q2-Q1×P2-Q1≥0]

判段跨立[P1P2]的依据是

[Q1-P1×P2-P1×P2-P1×Q2-P1≥0]，具体情况如图1所示：

图1 跨立试验算法研究图

1.2.1 特殊情况处理的一致性方法

对相交的线段求交时裁剪线段通过多边形的顶点，若两个相临边在被裁剪线段的同侧，即不为交点，若在裁剪线段的异侧则记为交点。若相交的线段求交时裁剪线段与多边形的边重合则做顶点的凹凸性判断，即在两线段重合部分的两端点中，若端点是多边形凸顶点，则将该顶点记为交点，若是多边形凹顶点，则该顶点不记为交点。若被裁剪线段的端点在多边形窗口的边上而不在顶点上，将端点记为交点，若该端点在多边形顶点上，则将该端点及其上的所有交点按横坐标从小到大排序来讨论左端点在多边形顶点是否记为交点的情况。

1.3任意多边形裁剪圆的算法研究

求出多边形与圆的交点，记录公共点包括交点与切点的位置与数量，根据多边形与圆的公共点数量对圆进行分类，对“有无公共点圆”进行裁剪。设线段端点[P1（x1，y1）][P2（x2，y2）]得到线段所在直线的方程[ax+by+c=0]，圆心[P0x0，y0]）和半径r得到圆的方程，由点到圆的距离公式算出圆心到线段的距离d。假设圆与线段有两个公共点，将线段P1P2写成参数方程形式。x与y是公共点坐标信息，t为参数用来判断直线与圆公共点是否不在线段范围内。按公式（2）判定出多边形与圆的关系。

（2）

综上分析，若d>r则多边形与圆没有公共点，将两个公共点对象的t置为不合法。若d<=r则通过圆方程与线段参数方程求解公共点坐标与参数，将t合法的公共点对象记录为多边形与圆的公共点。对于d=r的情况视为有两个相同的公共点输出。

2 软件测试与应用分析

图2 裁剪前后对比

图3 百万级矢量图形正确裁剪显示

任意line和circle，与多边形裁剪边界相交时正确裁剪显示：a）是裁剪前图级的line和circle需要裁剪显示时正确的显示图形显示；b）是裁剪后裁剪前图级的line和circle需要裁剪显示时正确的显示图形显示。

3 结论

本文解决了海量矢量图形如何在非自交多边形边界中的裁剪显示问题，通过采用快速排斥试验，跨立试验等算法实时高效地计算海量矢量图形与任意多边形区域的交点，正确显示位于多边形边界内部的图形部分，在实现基本功能的基础上，最终实现当有百万级的line和circle需要裁剪显示时，统计的完成裁剪显示的时间不超过10s，存储器占用不超过100MB，提升了时间和空间效率。

参考文献：

[1] 刘勇奎，刘桂英.一般多边形窗口的线裁剪[J].计算机辅助设计与图形学学报，1993，5（4）：269-274.

[2] 汪灏泓，吴锐迅，蔡志杰.一种几何变换的高效的线裁剪新算法[J].软件学报，1998，9（10）：728-733.

[3] 刘勇奎，颜叶，石教英.一个有效的多边形窗口的线裁剪算法[J].计算机学报，1999，22（11）：209-214.

[4] Cyms M，Beck J.Generalized two—dimensional clipping[J].Computer and Graphics，1978，3（1）：23-28.