用VC实现的任意多边形裁剪算法

收稿日期:2005-03-

25;修订日期:2005-05-26

作者简介:李海姣(1977-),女,河南郑州人,助理工程师,硕士研究生,主要研究方向:三维CAD 、图形算量.

文章编号:1001-9081(2005)12Z -0421-03

用VC ++实现的任意多边形裁剪算法

李海姣,张维锦

(华东交通大学土木建筑学院,江西南昌330013)

(haijiao_li@https://www.wendangku.net/doc/0816786635.html, )

摘　要:提出了一个用VC ++语言实现的凸多边形、凹多边形,也可以是带内环的多边形的裁剪算法,可以求上述多边形的“交”、“并”以及“差”。首先,该算法使用VC ++支持的CObL ist 类和CA rray 类的对象存储数据,具有占用内存空间少及处理速度快的特点;再通过算法和数据结构的设计不仅使得多边形顶点可按顺时针方向或逆时针方向输入,而且减少了求解过程中对多边形顶点数据的遍历次数;基于判断和计算交点是裁剪算法的主要工作,文中引入了求交前的预处理,避免了大量不必要的求交,降低了算法的时间复杂度。最为重要的是该算法不需要对两多边形的边重合或两多边形在顶点处相交的情况作特殊处理。

关键词:多边形裁剪;VC ++数据结构;凸多边形;凹多边形;交点计算预处理中图分类号:TP391.41 文献标识码:A

0　引言

在图形系统中,二维裁剪是最为基础、最为常用的操作之

一,其典型的应用是在图形的消隐处理等各种三维图形的处理以及各种排料算法等求交操作之中。如图形消陷、缩放、模式识别、导线和元件布局、线性规划[2]以及土木工程计算机辅助设计中梁与柱、墙与板、墙与柱特别是各类型基础工程量的计算等领域中都要广泛应用到多边形的裁剪。对裁剪算法的研究主要集中在裁剪直线和裁剪多边形两方面。在实用中,多边形裁剪与线剪裁相比具有更高的使用频率,因此它是目前裁剪研究的主要课题[1]。多边形愈复杂其裁剪算法就愈难以实现。文献[1]中综述了现有的解决方案,但这些方案或者局限于某一类多边形,或者时间复杂性和空间复杂性都较高。

本文对两个任意多边形相交时可能出现的位置关系做了严格的定义,用VC ++语言实现了两个任意多边形的交、并和差算法。其中的裁剪多边形和被裁剪多边形都可以是一般多边形,既可以是凸多边形、凹多边形,也可以是带内环的多边形。本文针对多边形裁剪中相交的特点,做了多边形求交前的预处理,从而避免了不必要的求交,不仅减少了不必要的求交次数,而且将复杂的乘除法运算用简单的加减法代替,进一步提高了算法的运行速度。最为重要的是该算法不需要对两多边形的边重合或两多边形在顶点处相交的情况作特殊处理,这一点远远优于文献[1]中所述的算法,而且本文算法同样适用于有内环的多边形。算法最终通过简单的遍历多边形交线指针数组,就可以得到每一个结果多边形。

1　算法的数据结构

⑴多边形裁剪

多边形裁剪是指用于裁剪掉被裁剪多边形(又称为实体多边形)位于窗口(又称为裁剪多边形)之外的部分。

⑵相交的定义

如图1(a )、

(b )所示,视为线段AB 与线段CD 不相交;如图1(c )所示,视为线段AB 与线段CD 相交,且交线为C D

。

图1　线段相交示意

多边形裁剪算法需要一个适当的数据结构来存储多边形顶点及交线数组,并能够在其上进行正确的操作。在W eiler 的算法中输入多边形组成一个树形结构。Greiner 2Hor mann 算法采用双向链表结构,每个多边形由一个双向链表来表示。每找到一个交点就将其分别插入到实体多边形和裁剪多边形的两个双向链表中。Greiner 2Hor mann 算法使用了线性链表与W eiler 算法的树形结构相比降低了数据结构的复杂性。

本文算法用VC ++语言编程实现。利用M FC 类的Cob L ist 类以及CA rray 类的对象(动态数组),可以方便地实现多边形顶点及交线的数据存储,同时M FC 类封装了对上述动态数组中数据元素的遍历、获取、插入、删除。

本文算法的每个多边形由一个动态数组来表示,数组按多边形顶点的输入顺序存储其顶点数据,数组的每一个元素对应于多边形的一个顶点。数组的最后一个元素与第1个元素相同以构成一个封闭的多边形,而每两个相邻的元素的一个组合对应于多边形的一条边,而有一个共同元素的一对组合对应于多边形的两条相邻边,公共元素是两条相邻边的相交顶点。

多边形顶点数组中每一个元素的数据结构定义如下:

typedef struct {fl oat x;//结点的X 坐标分量fl oat y;//结点的Y 坐标分量

}Vertex;

如图2所示多边形S 和C 的顶点数组分别为:

第25卷

2005年12月

计算机应用

Computer App licati ons

Vol .25Dec .2005

CA rray S,C;

//声明多边形S 、多边形C 的顶点数组

S ={s 1,s 2,s 3,s 4,s 1};C ={c 1,c 2,c 3,c 4,c 5,c 6,c 1}

;

图2　包围盒示例

如上所述,多边形S 和C 的数组中每两个相邻元素的一个组合表示相应多边形的一条边s 1s 2,表示多边形S 的边s 1s 2。而有一个共同元素的两个组合表示两条相邻边如s 1s 2、s 2s 3表示多边形S 中相交于顶点s 2的两条邻边。

交点的数据结构如下:

typedef struct {fl oat x;fl oat y;fl oat z;

MyPoint Star;//该交点所在的另一多边形的边的起点MyPoint End;//该交点所在的另一多边形的边的终点

}

MyJD;

定义交点数组为:

CA rray m_JD;

定义临时数组m_tempP:

CA rray m_te mpP;

交线的指针数组定义如下:

CTypedPtr L ist CoL ineL ist;

//存储指向每一条交线对象的指针,CD ra wBase 为绘图类的基类

3　算法描述

算法分为4个步骤,为表述方便设多边形分别为S 和C 。

第1步:求包围盒,避免不必要的求交运算。

1)如果两多边形的包围盒不相交,则这两个多边形一定不相交,即它们的交集为空,并集为这两个多边形。

2)若这两个多边形的包围盒相交,则求多边形S 的包围盒并剔除多边形C 中不在该包围盒内部的边,剔除后记为C ′;再用多边形C 的包围盒(记为包围盒2)剔除多边形S 不在包围盒2中的边,剔除后记为S ′。

第2步:对S ′的各边循环,将各边与C ′的各边求交,对S ′的任意一边S i S i+1其具体操作如下:

1)清空临时数组m _te m pP;

2)调用库函数Poin tR gn ()测试边S i S i+1的起点S i 是否位于多边形C 内:若位于C 内,则将点S i 加入临时数组m _te m pP (CA rray m _te m pP )中;

3)依次取出C ′的两个相邻顶点,即C ′的边C i C i+1,进行求交前的预处理。

4)在预处理后,若判定两边相交(线段与线段交点不是虚交点),则调用子函数求交点,并分别将求得的交点加入到

临时数组m _te m pP 和交点数组m _JD 中。直至遍历了C ′中的所有边;

5)调用子函数对临时数组m _te m pP 中的各点按边S i S i+1

的方向排序,并依次判断相邻两个交点的中点是否位于多边形C 内:若是,则将以这两个交点为起点和终点的边加入交线指针数组Co L ine L ist 中;

至此,两多边形的所有交点和多边形S 在多边形C 内的部分都已经求出。

第3步:组织交点,构造多边形C 在多边形S 内的边。具体操作是对C ′内的边循环,对每一边C i C i+1:

1)清空临时数组m _te m pP;

2)若C i 位于多边形S 内,则将其加入临时数组m _te m pP;

3)判断m _JD 中的所有各点的S ta r 和End 是否与C i C i+1

的起点和终点相同,若相同,则将其加入临时数组m _te m pP 中;

4)若C i+1位于多边形S 内,则将其加入临时数组m _te m pP;

5)调用子函数对临时数组m _te m pP 中的各点按边C i C i+1

的方向排序,并依次判断相邻两个交点的中点是否位于多边形C 内:若是,则将以这两个交点为起点和终点的边加入交线指针数组Co L ine L ist 中;

第4步:输出结果多边形。对交线指针数组循环,直至所有的线段均被输出。

当多边形是有内环的多边形时,仅需将带内环的多边的内环与外环的顶点分别存储在两个CA rray 动态数组中,并使得内外环的顶点的输入顺序相反,即可采用上述算法将内环、外环多边形分别与被另一多边形求交。

在上述算法中将有多次用到的操作都做成了子函数以提高代码的复用率。将以上算法稍做修改即可用于多边形求并以及求差。

4　交点的判断与计算前的预处理

由上述分析可知,多边形裁剪的交点判断和计算就是用一多边形的每一条边与另一多边形求交点,可见求交计算是裁剪算法最核心的一部分,它的准确性与效率直接影响裁剪的可靠性与效率。为提高求交的效率本文在求交前采用如下方法做预处理:

⑴运用包围盒进行预处理

首先求出多边形S 和多边形C 的包围盒。在此需要做两步判断:

1)若两多边形的包围盒不相交,则两多边形一定不相交,从而可得其交集为空,其并集为两个多边形的所有边。

2)若两多边形的包围盒相交,则进行求解计算。用多边形S 的包围盒过滤多边形C 位于包围盒外的边以减少不必要的求交和判断。如图2所示用多边形S 的包围盒可剔除多边形C 的边C 6C 1、C 2C 3和C 3C 4,接着用多边形C 剩余边的包围盒剔除多边形S 不在该包围盒内的边。从而在计算过程中仅需要判断或者求解多边形S 与多边形C 剩余边的交点,从而可以大大减少计算量。又因为做一次乘法运算远比加减法(比较运算)耗时,所以采用这一预处理大大减少了算法的时间复杂度。

设多边形的包围盒的四个角点的坐标为:S 1(X left ,Y botto m )S 2(X right ,Y botto m )S 3(X rightYtop )和S 4(X leftYtop )被裁剪线

224

计算机应用2005年

段Q 1Q 2的坐标为:Q 1(x 1,y 1)和Q 2(x 2,y 2)。只有当满足下

列条件时:

MAX (x 1,x 2)≤X left 或M I N (x 1,x 2)≥X right 或MAX (y 1,y 2)≤Y botto m 或M I N (y 1,y 2)≥Y top

才能判断线段Q 1Q 2在包围盒外面可以直接舍弃否则不能判断还需另外处理。如图2中的线段AB 还需要进一步判断。

⑵用两个判定条件做预处理

实际上,大多数情况下虽然线段Q 1Q 2与多边形有交点,但线段Q 1Q 2与多边形的多数边肯定是不相交的。如果能用比线段求交更简单的方法排除这类不相交的线段,则可以大大减少计算量。为此提出如下两个判定条件。

设被裁剪线段Q 1Q 2的直线标准方程为:

F (x,y )=A x +B y +C =0

(1)其中:A =y 2-y 1,B =x 1-x 2,C =-(A ×x 1+B ×y 1)。

对于直线段Q 1Q 2上的点F (x,y )=0;对于直线段上方的点F (x,y )>O;而对于直线段下方的点

F (x,y )

图3　Q 1、

Q 2位于边P i P i+1的同侧根据式(1)设F (x,y )=A x +B y +C 。由图3可看出当多边形某条边P i P i+1(i =0,l,…,n )的两个端点在线段Q 1Q 2的同一侧时,线段Q 1Q 2与多边形的边P i P i+1不相交。把符合这种情况的多

边形的边P i P i+1的两个端点坐标分别代入F (x,y )=A x +B y +C 则有

F (P i ,x ,P i ,y )?F (P (i+1),x ,P (i+1),y )>0

(2)为了避免进行乘法运算,上述不等式的判断可转化为:S IGN (F i )-S IGN (F i+1)=0,

S IGN (F i )≠0且S IGN (F i+1≠0)(3)其中函数S IGN (x )表示对x 符号的测试:

S IGN (x )=-1, x <0

0,x =0

1,

x >0

(4)特殊情况:当S IGN (F i )=0或S IGN (F i+1)=0时,即

F (P i ,x ,P i ,y )=0或F (P (i+1),x ,P (i+1),y )=0时,则点P i 或P i+1在直线段Q 1Q 2或其延长线上如图4所示。这时需要根据具体情况分别处理。

①若F (Q 1,x Q 1,y )=0且点Q 2位于多边形S 的内部则将点Q 1和Q 2同时加入交点数组如图4中(c )所示。

②若F (Q 1,x Q 1,y )=0且点Q 2位于多边形S 的外部则点Q 1不作为交点如图4(d )所示。

③对图4中(a )、(b )所示情况按前述定义处理。在(a )中,若Q 2为有效交点必然会被包含Q 1Q 2的多边形中与Q 1Q 2

相邻的边与边P i P i+1在求交时引入,为避免交点重复故此处不将其作为交点。这样处理使得多边形有重合边时也能作为一般情况来处理,从而避免了文献1中的繁琐处理。

判断条件1:

若线段Q 1Q 2按顺时针逐边裁剪窗口多边形P 0P 1P 2…P n -1P n 。对于多边形的边P i P i+1,若满足式(4)时,则可判断直线段Q 1

Q 2与多边形边P i P i+1无有效交点,不用再求交,如图3所示。从而直接判断多边形的下一条边界。

图4　特殊情况

又设多边形边P i P i+1(i =0,1,…,n )的直线标准方程为:

G i (x,y )=A i x +B i y +C =0(5)

其中A i =P i ,y -P (i+1),y ,B i =P (i+1),x -P i ,x ,C i =-(A i P i ,x +

B i P i ,y )。

同理,对于多边形边P i P i+1上的点有G i (x,y )=0;对于

P i P i+1上方的点则有G i (x,y )>0;而对于P i P i+1下方的点则

有G i (x,y )<0。当G i (x 1,y 1)?G (i+1)(x 2,y 2)>0时,即

S IGN (G i )-S IGN (G (i+1))=0

(6)

表示线段Q 1Q 2的两端点在多边形边P i P i+1的同一侧,说明线段Q 1Q 2与多边形边P i P i+1没有有效交点,如图3所示。

判断条件2:

若线段Q 1Q 2按顺时针逐边裁剪窗口多边形P 0P 1P 2…

P n -1,P n 对于多边形的边P i P i+1首先用判断条件1来判断,若

不满足式(3),则继续用式(6)来判断。若满足式(6)则也可判断直线段Q 1Q 2

与多边形边P i P i+1没有有效交点,从而直接跳出,进入多边形下一条边的测试。若两个判断条件都不满足则要进行求交运算。

5　结语

图5　任意多边形求交举例

本文用VC ++及其所支持的MFC 类的特性用动态数组实现了对多边形顶点、交点以及交线的数据存储,大大降低了算法的空间复杂性。算法的改进减少了裁剪过程中的对多边形顶点数据的遍历次数;同时通过求交前的预处理用简单的判断减少了复杂求交的次数,从而进一步降低了算法的时间复杂性。应用本算法成功实现了三维C AD 及图形算量软件中的各类扣减,多边形求交实例见图5。其中虚线边界为两多边形的并,实线边界为两多边形的交。参考文献:

[1]　刘勇奎,高云,黄有群.一个有效的多边形裁剪算法[J ].软件

学报.2003,14(4):845-856.

[2]　周培德.计算几何[M ].北京:清华大学出版社,2000.133-153.

32412月李海姣等:用VC ++实现的任意多边形裁剪算法