基于直线斜率的凸多边形线裁剪算法

《 基于直线斜率的凸多边形线裁剪算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于直线斜率的凸多边形线裁剪算法基于直线斜率的凸多边形线裁剪算法基于直线斜率的凸多边形线裁剪算法基于直线斜率的凸多边形线裁剪算法基于直线斜率的凸多边形线裁剪算法基于直线斜率的凸多边形线裁剪算法基于直线斜率的凸多边形线裁剪算法基于直线斜率的凸多边形线裁剪算法基于直线斜率的凸多边形线裁剪算法第22卷第8期2005年8月计算机应用与软件ComputerApplicationsandSoftwareVo1.22,No.8Aug.2005基于直线斜率的凸多边形线裁剪算法唐棣单会秋(辽宁师范大学计算机科学系辽宁大连116029)摘要凸多边形的线裁剪算法在计算机图形学中占据着很重要的地位,

2、现在的许多领域均有很重要的应用.本文提出了一种非常有效的基于直线斜率的凸多边形线裁剪算法,并与Cyrus—Berk算法进行了比较.结果表明:本算法更加简单,高效.关键词凸多边形斜率线裁剪法矢量LINECLIPPlNGALGoRITl1[ToNCONVEXP0LYGoNBASEDoNLINE’SSLoPETangDiShanHuiqiu(DepartmentofComputerScanCe.LiaoningNormalUniversit),DalianLiaoning116029,China)AbstractThelineclippingonconvexpolygonhasan

3、importantstatusinComputerGraphics,andisbeingusedinmanyfields.Thistextputsforwardaveryeffectiveclippingalgorithmbasedonline’Sslope,andcomparesitwithCyrus—BerkAlgorithmTheresultindicatesthatitissimplerandmoreeffective.KeywordsConvexpolygonLineslopeLineclippingNormalvector1引言裁剪是计算机图形学的重要内容,是在指

4、定区域内识别图形内外部分的一个过程.计算机图形学的许多重要操作以它作为基础.裁剪主要应用在:从定义的场景中抽取出用于观察的部分;在三维视图中标志需要的可见面;清晰各个对象之问的模糊边界;用实体造型来创造对象;显示多窗口的环境等等方面.目前对于二维的矩形窗口的线裁剪已经得到了人们深入的研究,端点编码算法,Cohen—Suhenerland线段细分裁剪算法以及中点分割等算法都比较成熟.然而,在许多应用中,裁剪窗口并非规则矩形.因此,上面所述算法无一适用.对于一般凸多边形窗口的线裁剪,目前也已有几种算法.其中最着名,最有效的算法是由Cyrus和Berk提出的Cyrus—Berk算法

5、.2Cyrus—Berk算法c,邢一Berk算法通过判断直线段的方向矢量与窗口边法矢量的点积是否为零而将所有交点分为上下两组.然后,分别取上组中的最小交点与下组中的最大交点,即为线段可见部分的端点.考虑一个凸多边形区域月,被裁剪线段P.Pz.设/是R边界上的一点,而,z是该点所处边界的内法线矢量,如图1所示.线段的参数方程为:P(t):PI+(P2一P1)}t(0≤￡≤1)魉图1内法线矢量的方向这时连接线段上一点到边界上其它任一点的矢量与内法线矢量的点积为:n.?[P(t)一]i=1,2,…当所取参数直线段上的点位于区域之内,区域边界上或区域之外时,点积的值分别为大于零,等于

6、零和小于零,这一关系式适用于区域的任意边界.则直线与窗口交点的条件为:n?[P1+(—P1)}t一/=]=0即:n.?(P1一)+n?(P2一P1)}t=0设D=P2一P1;W=P1一/=则:t=.?ni/D?niD≠O,i=1,2,…若所得的t值位于0≤t≤1之外,则可抛弃.把剩余的t值分为两组,一组为下限组,分布于线段起始点一侧;另一组为上限组,分布于线段终点一侧.找出下限组中的最大t值和上限组中的最小￡值.若D?n.>0,侧求下限组中的最大值￡P(￡);相反,若D?n.<0,则求上限组中的最小值t,从P(tL)到P(t)位于窗口内,是可见线段.3基于直线斜率

7、的裁剪算法该算法通过对被裁剪线段所在直线的斜率和凸多边形窗口各边的斜率之问进行比较,并通过找出线段与凸多边形边界的真实交点,快速有效地判断出线段对于凸多边形窗口的位置关系,而裁剪出线段在凸多边形区域内的部分.3.1算法的基本原理多边形与线段的基本位置关系只有四种:线段在凸多边形外,如图2(a);线段在凸多边形内,如图2(b);线段与凸多边形有一个交点,如图2(C);线段与凸多边形有两个交点如图2(d).收稿日期:2004—06—16.唐棣,教授,主研领域:计算ULIE形学的科研与教学工作.116计算机应