（计算机应用技术专业论文）圆与椭圆对多边形裁剪算法研究.pdf

哈尔滨工程大学硕士学位论文 摘要 裁剪是计算机图形学中的一个重要技术。裁剪有多种类型，其 中，二维多边形裁剪是露前裁剪研究的主要课题。矩形( 或多边形) 对多边形裁剪已有许多经典的算法。由于没有完全避免求解一元二 次方程或开方运算，因和椭匿对多边形裁剪效率较低。 本文对圆和椭圆对多边形裁剪进行深入研究，设计出快速可行 的算法。圆对多边形裁剪是研究的重点，做到完全避免求解一元二 次方程和开方运算。 应用区域编码技术将完全可见或显然完全不可见的多边形判别 出来。对于既不是完全可见也不是显然完全不可见的多边形，需要 用圆对多边形各边进行裁剪。主要通过区域编码技术并借助于距离 平方判别法判别出圜和多边形各边静位置关系；采震中点分割算法 求圆和多边形边的近似交点；通过交点和位于圆内的多边形顶点逆 时针顺序的邻接关系，确定裁剪结果的直线边界；通过对交点的排 序和配对，确定裁剪结果的曲线边界。 圆是一种特殊的椭圆，撼圆不具有圆的所有特性。圆对多边形 裁剪算法不能简单地移植到椭悉对多边形裁剪上，找出阑对多边形 裁剪算法中不适合椭圆对多边形裁剪的地方，设法修改得到完全适 合椭瑟对多边形裁剪的有效算法。 关键词：计算规图形学；算法；裁剪；瑟形窗口；撩菡形窗口 a bs t r a c t c l i p p i n g i so n eo ft h e f u n d a m e n t a lt e c h n i q u e s i n c o m p u t e r g r a p h i e s 。t h e r ea r em a n yt y p e so fc l i p p i n ga m o n g w h i c h2 dp o l y g o n c l i p p i n g i s c u r r e n t l y ap r i m a r y r e s e a r c h t o p i c m a n y c l a s s i c a l a i g o r i t h m sh a v eb e e nd e v e l o p e df o rp o l y g o nc l i p p i n ga g a i n s tr e e 雏g l e ( o rp o l y g o n ) ，h o w e v e rt h ec l i p p i n ga l g o r i t h m so fp o l y g o na g a i n s t c l r c l e o re l l i d s ea r ec o m p u t a t i o n a l l yi n e f f i c i e n td u et o s o l u t i o no fq u a d r a t l e e q u a t i o n so rc o m p u t a t i o n o ft h es q u a r er o o t l nt h et h e s i sp o l y g o nc l i p p i n ga g a i n s tc i r c l ea n de l l i p s ei ss t u d i e d & 觳de 豫e i e n ta n d e f f e c t i v ea l g o r i t h m s a r ep r e s e n t e d e m p h a s i sl s f o c u s e do nc l i p p i n ga g a i n s tc i r c l ew h i c ha v o i d sc o m p l e t e l ys o l u t l o no f q u a d r a t i ce q u a t i o n so rc o m p u t a t i o no f t h es q u a r et o o t p o l y g o n s a r ef i r s t l y i d e n t i f i e da sb e i n gc o m p l e t e l y v i s i b l e , i n v i s i b l e 。o rp a r t i a l l y i n v i s i b l ee d g e so fw h i c hs h o u l d b ec l i p p e d a 敛a i n s tc i r c l e t h em a i nt e c h n i q u e s i n v o l v e da r e a sf o l l o w s ，t h e r e l a t i o n s h i pb e t w e e nc i r c l ea n dt h ep o l y g o ne d g e s a r ed e t e r m i n e dv i a r e g i 。珏e n c o d i n ga n dm e t h o do fs q u a r ed i s t a n c e ；t h ei n t e r s e e t i o 珏p o i n t s b e t w e e ne d g e sa n d c i r c l ea r ec o m p u t e db yu s i n g m i d d l ep o i n t s e g m e n t a t i o na l g o r i t h m s ；t h eb o u n d a r yo fe d g es e g m e n t sl s a c h i e v e d t h r o u g ha d ja c e n tr e l a t i o nb e t w e e ni n t e r s e c t i o np o i n t sa n d v e r t e x e so f p o l y g o n ；f i n a l l y t h ec l i p p i n gr e s u l t s a r eo b t a i n e dv i as o r t i n ga n d p a i r i n go fi n t e r s e c t i o np o i n t s ac i r c l ei sas p e c i a lc a t e g o r yo fe l l i p s et h a th a ss o m es p e c i f i c p r o p e r t i e s i ti st h e r e f o r ei m p o s s i b l et o e x t e n ds t r a i g h t f o r w a r d l yt h e a l g o r i t h m s o fc l i p p i n ga g a i n s tc i r c l e t ot h o s ea g a i n s te l l i p s e b y 。b s e r v i n g w h a ti sn o ta p p r o p r i a t ef o rc l i p p i n ga l g o r i t h m sa g a i n s t e l l i p s e w em o d i f y t h ea l g o r i t h m sr e l a t i n gt oc i r c l e w i n d o wt og e t 哈尔滨工程大学硕士学位论文 e f f e c t i v ea l g o r i t h m so fp o l y g o nc l i p p i n ga g a i n s te l l i p s e 。 k e y w o r d s ：c o m p u t e rg r a p h i c s ；a l g o r i t h m ；c l i p p i n g ；c i r c u l a rw i n d o w ； e l l i p s ew i n d o w 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指 导下，由作者本人独立完成的。有关观点、方法、数据 和文献的引用已在文中指出，并与参考文献相对应。除 文中已注明引用的内容外，本论文不包含任何其他个人 或集体已经公开发表的作品成果。对本文的研究做出重 要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：玉塾壑 曰期：嘴年月? e l 哈尔滨工程大学硕士学位论文 第1 章绪论 熏重课题的来源及意义 1 。1 1 课题的来源 综溉计算机发展的历程，计算机发展豹热潮按时闻先后的顺序 依次是操作系统、数据麾、网络。那么，计算机发展的下一个热潮 是什么? | 有学者从计算机是人的王作工具出发预测：计算机发展的 下一个熟潮是包括图形圈象在内的加强信息利用和沟通的方向雒1 。目 前，在欧美等发达国家，关于图形图象的研究和应用正处于一种爆 炸式的发展阶段。中雷计算机图形学也已取得了长足豹进步，在囡 际图形学界也有席之地。但是，整体地看，中国计算机图形学在 震际上理论研究方面的地位不高。有鉴予此，必须加强对计算机登 形学的研究，必须加强计算机图形学的应用及普及，使我国能更早 地获得图形图象处理方藤的核心的、有竞争性的成果，快速地提高 我国计算机发展的实力，赶超欧美发达国家计算机科学技术水平。 计算机图形学研究的内容比较广泛，裁剪是其中许多重要问题 的基础，也是计算枕图形学中比较重要的操作。裁剪中，二维裁剪 最为常见、最为基础。圆或椭圆作窗口对多边形裁剪的应用也处处 可见。整翦，虽然存在着凡辩圆对多边形裁剪的算法，僵是，或者 是由于求解了一元二次方程组，使用了开方运算，或者是由于建立 和查找规范化交点表，效率都较低。研究快速的医和椭隰对多边形 裁剪算法既具有理论意义又有实际应用价值。 哈尔滨工程大学硕士学位论文 1 1 2 课题研究的目的及意义 鸯1 9 6 3 年美莺麻省理工学院( m i t ) 棒肯实验室i v a n e s u t h e r l a n d 发表的博士论文【2 】确定了计算机图形学作为一个崭新科 学分支的匿+ 余年以来，计算机图形学( c o m p u t e rg r a p h i c s ) 飞速 发展并取得巨大成就和广泛应用。如今，计算机图形学的基本理论、 方法和技术不断完善和发展，新的概念和技术也不断涌现。计算机 图形学的应用已非常广泛，在数字化信息时代里，凡是使用语言、 声音、文字、数字、数学公式、图形或图像的场合，计算机图形学 都大有用武之地，并显对于形象思维无不表现其独到的优越性，可 以说：“图形无所不在 。 裁剪是计算机图形学中比较重要鲍操作，也是计算机图形学、 图像处理和模式识别中许多重要问题的基础。识别位于指定区域内 或指定区域外的图形部分的操作称为裁剪( c l i p p i n g ) 。用来裁剪对 象的区域称为裁剪窗口，简称窗踊( w i n d o w ) 。 裁剪的应用包括：从一幅大画面中剪取局部视图；在三维视图 中标识蹦可见线、可见舔，剔除隐藏线、隐藏面；防止线段或对象 的边界混淆，处理图形反走样；使用体的布尔运算、实体造型来创 建对象；显示多窝墨的环境；允诲选择匿形的一部分以进霉亍复制、 移动或删除等编辑操作。 根据裁剪对象的不同，裁剪可分为：点裁剪、线( 段) 裁剪( 处 理的对象是直线段) 、面裁剪( 处理的对象一般是多边形) 、曲线的 裁剪和文字的裁剪。根据裁剪区域是二维窗口还是三维体，裁剪又 可分为二维裁剪和三维裁剪。裁剪对象和裁剪区域可以是规剐的， 也可以是不规则的。裁剪算法既可以用软件实现，也可以用硬件实 现。 在图形系统中，二维裁剪是最为基础、最为常用的操作之一。 对裁剪算法的研究主要集孛在裁剪直线段和裁剪多边形嚣方蘧。在 实用中，与线段裁剪相比，多边形裁剪舆有更高的使用率，因此是 2 哈尔滨工程大学硕士学位论文 强翦裁剪研究的主要课题。多边形裁剪用于裁剪搏被裁剪多边形( 又 称为实体多边形) 位于窗1 ：3 ( 或是多边形，此时称其为裁剪多边形， 或是匿，或是椭圆) 之外或之虎的部分。多边形愈复杂，其裁剪算 法就愈难以实现。现有的解决方案均不太完美，例如：或者局限于 某_ 类多边形，或者求交运算太多太复杂，或者判断窗豳与多边形 位置关系的方法太复杂，或者数据结构太复杂，时闻消耗大。 圆( 或椭圆) 对多边形的裁剪就是圆( 或椭圆) 作为裁剪窗阴， 裁剪对象是任意多边形的二维裁剪。在实际应用中，匮( 或椭圆) 对多边形的裁剪也是常见的一种裁剪操作。场景中的景物具有各种 形状，景物的投影多见于多边形和圆形( 或椭圆形) 。若圆形( 或椭 圆形) 景物表面位于前面，多边形景物表面位于后面，则圆形( 或 椭圆形) 景物表面是可见面，它遮挡了位于其后的景物表面或景物 表面的一部分( 称为隐藏面) 。取圆或椭圆( 即圆形、椭圆形的景物 表面) 为裁剪窗豳，对排列在其后面的多边形景物表面进行外裁剪， 消去位于圆形( 或椭圆形) 窗固之内的多边形景物表露或其一部分， 绘制或保留位于圆形( 或椭圆形) 窗口之外的多边形景物表面或某 一部分。因此，露( 或椭圆) 对多边形的裁剪也具有非常广泛的实 际应用价值。 同时，圆( 或椭匮) 对多边形的裁剪毒 常类似于童然界中的一 些现象和人类的某些工作、生活的方式。如：鹰眼的所有视线组成 个锥体，它所能看得见的范围是一个圆形或椭圆形的；黑色的夜 晚，手电筒发出的光在地面上形成一个圆形或椭圆形区域，人们只 能看到其内的物体；人们使用望远镜观察到远处的区域也是一个圆 形或椭曛形区域。 另外，在一个具体的域面中，需要对大量的基本图形元素进行 裁剪。因此，裁剪算法麴效率显得十分重要，直接影响整个图形处 理的效率。最影响裁剪效率的有两个因素：一个是裁剪窗口和裁剪 对象位置关系的判别，一个是求交点的运算。在实际中绝大多数都 是通过加强位置关系的判别、减少计算交点的次数，采用简单的求 交运算，+ 来达到提高裁剪算法的效率。在圆( 或椭圆) 作窗1 3 的裁 3 哈尔滨工程大学硕士学位论文 剪中，求交点时，往往涉及开方运算或求解二次方程，浪费很多机 器时间。而且，圆( 或椭圆) 和多边形的位置关系复杂，圆( 或椭 瞩) 与多边形的边是否樵交也不易判断。嚣此，另辟途径，尝试设 计一个快速的圆或椭圆对多边形裁剪的算法也具有很强的理论意 义。 1 2 国内外裁剪研究的现状及发展趋势 主要介绍最为基础的二维裁剪情况。 1 2 1 点裁剪 点裁剪最简单。无论什么样的裁剪窗口，都很容易判别点的可 见性，如检查一点是否在任意多边形内的射线法( 或称累计交点法， 后面要用到此方法) 。 1 2 2 矩形窗口的线段裁剪 由于直线是图形系统中使用最多的一个基本元素，所以，对于 直线段的裁剪算法是使用最广泛的一类算法。这一类算法因此得到 了普遍的重视和较深入的研究，特别是矩形窗口对直线段的裁剪， 嬲现了许多经典的算法。其中，比较著名的算法有： s u t h e r l a n d c o h e n ( 萨瑟兰德科恩) 裁剪算法【3 1 。它是一个最早 最流行的线段裁剪算法。它震线段两个端点的区域编码标识端点相 对于矩形窗口边直线的位置，并利用端点区域编码的性质简单地决 定是否接受或抛弃一条线段。一条线段如果不能被简单地接受或抛 弃，便求窗口边直线与该线段的交点，交点将该线段分割为两段， 褥对每一段进行如上处理。 中点分割裁剪算法f 4 l 。它是由s p r o u l l 和s u t h e r l a n d 为了便于硬件 实现而提出来的，仍然采用线段端点的区域编码和相应的检查方法， 4 哈尔滨工程大学硕士学位论文 通过对分的方法不断地将线段一分为二，抛弃线段的不可见部分， 并用中点逼近线段与矩形窗口边直线的交点。 粱友栋b a r s k y 裁剪算法f 鲥。它是一种特殊形式的c y r u s b e c k 参数 化线段裁剪算法 7 1 。当使用矩形窗口时，它比s u t h e r l a n d c o h e n 裁剪 算法更有效，因为需要计算的交点数目减少了。 n l n ( n i c h o l l 。l e e n i c h o l l ) 裁剪算法泌】。它是利用回避原则而 得到的一个快速的二维线段裁剪算法，仔细检查线段和矩形窗口的 相对位置来篱单地抛弃显然不可觅部分，从而避免了不必要的复杂 求交运算。 1 2 3 多边形窗口的线段裁剪 任意多边形作为窗口的线段裁剪要比矩形窗暖的线段裁剪复 杂，然而，如果加上某些限制，则裁剪操作可能会简单一些。典型 的多边形对线段裁剪算法有： c y r u s b e c k ( 塞勒斯。贝克) 裁剪算法 7 1 。它实现的是任意凸多 边形对线段的裁剪，线段直线采用参数方程表示，并剩用窑墨边界 内法向量与线段方向矢量的内积( 或点乘积) 运算来判断线段完全 可见或曼然完全不可见。根据这个内积大于零和小于零将所有交点 分为上限组和下限组，分别取上限组中的最小交点和下限组中的最 大交点，即得到线段的可见部分。 刘勇奎等提出的适用于一般多边形( 包括凹多边形) 窗口的线 段裁剪算法1 8 1 。它首先在线段直线( 即被裁剪线段所在直线) 上取一 固定点，然后求多边形窑圈的每顶点到该固定点弓| 线髓斜率。这 样对于每个窗口边只需判断线段直线的斜率是否在与该边相关联的 两顶点到固定点孳| 线斜率之闻，就可判断线段直线与边是否相交。 因此，每处理一个与线段直线无交点的窗口边，只需一次除法和 次减法及少量的比较操作。 陆园栋等提出基于顶点编码的多边形窗口线裁剪高效算法 9 1 。 它以被裁剪线段直线为参照系，将多边形窗口划为正区、负区和近 s 哈尔滨工程大学硕士学位论文 零区三类区域，欲焉快速完成多边形窗隧顶点编码。透过窗蜀顶点 编码与传统的线段编码相结合，无须求交即可排出大部分窗外线段， 进步可以直接彳罨到与线段直线相交的窗口边，加快了求交进程。 更有意义的是，通过窗口顶点编码还可以准确判断并快速处理如下 蹰类特殊相交情况：线段直线通过多边形的顶点；线段童线通过多 边形的边。 i 2 4 圆和椭圆窗墨的线段裁剪 圆_ ； 翼椭医对线段裁剪算法也有些： ( 1 ) 圆窗口的线段裁剪 圆窗口的线段裁剪算法也有一些。姚涵珍等和刘勇奎把线段童 线的参数方程代入圆的方程，通过分析一元二次方程的求根判别式 及根的范围来进行裁剪】 1 9 1 。这种算法在直线段与圆形窗口相交时， 效率较高。 沈庆云等利用圆心到线段直线的距离，线段相对从圆心向它所 学| 的主射线嚣位置关系及菡心到线段两端点的距蒜，郎可迅速判断 线段与圆形窗口的位置关系。当线段与圆形窗口相交时，用旋转矢 量法求出交点【2 引。 蔡敏等提出的快速圆形窗口线段裁剪算法 2 2 1 ，是利用圆与其外 切正方形的线性关系，制备规范化交点表，通过映射法查表实现圆 形窗口对线段的裁剪，避免了线圆求交、点。线距离和点点距离计 算，因而大幅度地提高了裁剪效率。 陆圜栋等给爨的算法l 建立在全面分析线段与菡形窑露几何特 性及二者相对位置的基础上。首先引入常规外切正方形一次编码技 术，然后提出旋转4 5 。外切正方形二次编码和广义距离三次编码两种 新的编码技术。常规外切正方形一次编码和旋转外切正方形二次编 码可以快速地舍弃大部分完全位予圆形窗团外的线段，广义距离兰 次编码可以快速地获取完全位予圆形窗口内的线段、快速地判别线 段与圆形窗口的相对位置。在获取线圆相对位置的基础上，通过广 8 哈尔滨工程大学硕士学位论文 义距离既可舍弃剩余酶窗外线段，又能加快线段与匿形密口熬求交 进程。 袁红亮等也提出了一种快速潮形窗飚线段裁剪算法【2 4 】。它利用 圆的外切正六边形和内接正六边形对裁剪平面进行编码，能够快速 地判定大部分的线段与圆形窗口之间的位置关系，然后对两者的位置 关系进一步细分，从而决定是否要进行求交，减少了无谓的求交运 算，前面判断得到的结果还在一定程度上加快了后面的求交过程。 唐棣等给崽的基于坐标变换的圆形窗口线裁剪算法l ，将平移、 旋转坐标变换引入圆形窗口的线裁剪中，使被裁剪线段位于x 轴，左 端位于坐标原点，线段与圆懿位置关系转化为圆与x 轴的位置关系。 唐棣等给出的基于象素的圆窗口的图形裁剪算法 2 6 1 。它特别适 合于图像处理中对图像的裁剪，不太适合于绘图。 孙长嵩教授等人在文献【2 8 】中介绍了六角网格坐标系及圆形窗 网与待裁剪线段的关系。在六角网格上，每个象素周围有六个相邻 的象素，都戮边相邻。他们利用六角两格坐标系统具有的特殊性， 首先对圆形窗口和待裁剪线段的六种位置关系给出了判断方法，在 求交点黠避免了解算二次方程，最后提擞了高效的、快速的基予六 角网格的圆形窗口的线段裁剪算法。 黄文钧等的免解二次方程的圆形窗口裁剪算法【4 4 】，采用距离的 平方判断圆与直线是否相交，利用线段的定比分点公式求解圆与直 线的交点。 ( 2 ) 椭圆窗口的线段裁剪 关予椭圆形窗口对线段的裁剪，由于计算更为复杂，计算量更 大露难以找到一种快速的裁剪算法。刘勇奎给出的算法【l 2 7 】中都包 含大量的二次运算而降低了裁剪速度。黄新贤等利用椭圆的外切长 方形，试图通过对线段所在的不同位置进行分析，尽量不通过复杂 的计算而通过比较分析直接接受或排除那些比较容易判断的线段， 然后对剩余的线段，利用预先制备的规范化表，通过映射法查表， 实现椭圆形窗口对线段的裁剪【2 辨。 哈尔滨工程大学硕士学位论文 1 2 5 矩形窗口的多边形裁剪 多边形是封闭区域，多边形裁剪的结果也应该是势闭区域。这 个要求给多边形裁剪带来了麻烦，需要设计专门的裁剪算法。 s u t h e r l a n d 。h o d g m a n ( 萨瑟兰德霍吉曼) 裁剪算法【3 0 】是种逐次多 边形裁剪算法，即分别用矩形窗口的每条边直线作裁剪线，按某种 顺序依次对多边形的各边进行裁剪。 梁友栋和b a r s k y 对矩形窗口裁剪做了优化，提出了一个多边形 裁剪的新算法【3 1 1 。该算法比s u t h e r l a n d h o d g m a n 裁剪算法快约两倍， 也能推广到任意的凸多边形裁剪窗墨。 1 。2 。6 多边形蜜爨的多边形裁剪 w e i l e r a t h e r t o n ( 韦勒艾瑟顿) 裁剪算法【3 2 】是最一般的多边形 区域对多边形对象的裁剪算法。此算法对窗口多边形( 称为裁剪多 边形) 和被裁剪的多边形( 称为主多边形) 不作任何限制，都可以 是任意的。它们既可以是凸多边形，也可以是凹多边形；既可以是 无孔多边形，也可以是带孔多边形。w e i l e r a t h e r t o n 裁剪算法首先对 裁剪多边形和主多边形的外、内边界规定好方向( 外边界雳顺时针 表示，内边界用逆时针表示) ：然后求_ 出两个多边形边的交点，并 分别为它们建立进点表( 包含主多边形边进入裁剪多边形内部时斡 交点) 和出点表( 包含主多边形边离开裁剪多边形内部时的交点) ； 最后裁剪的时候，从进点表中取如一个交点，从此交点出发，沿着 主多边形边界前行，当遇到另一交点时拐到裁剪多边形边界上继续 前行，以后每遇到一个交点都要换道，直到回到开始的出发点，那 么行走鼹径新罄成的封闭区域就是裁剪的结果。 w e i l e r - a t h e r t o n 裁剪算法使用树形数据结构，后来出现的v a t t i 算法强3 】翮g r e i n e r - h o r m a n n 算法【3 4 1 使用双线性链表数据结构，它们在 复杂性及运行速度方面都优于前者。 8 哈尔滨工程大学硕士学位论文 刘勇奎等给擞的算法【3 5 】只使用单线性链表数据结构，具有数据 结构简单、占用空间少的特点，并且无须事先规定以什么方向输入 多边形的顶点。另外，该算法使用了一个薪的具有最少计算量的交 点判断和计算方法，进步加快了算法的运行速度。算法最终通过 简单的遍历线性表，可以得到每一个输出多边形。该算法优于v a t t i 算法和g r e i n e r ，h o r m a n n 算法。 1 2 7 圆和椭圆窗口的多边形裁剪 圆和椭墓对多边形的裁剪，可麓是最难的裁剪之一。 ( 1 ) 圆窗口的多边形裁剪。在圆作为裁剪窗口对多边形裁剪方面， 桂玉越做了很多工作。他从十年前就开始对这方覆进行磅究，先后 在计算机工程和计算机图象图形学报等刊物上发表了几篇文章。他 在文献【3 6 】中，先计算出多边形边直线与圆形窗网的交点，再根据交 点判断多边形与圆的相交性，这样会增加计算量，降低裁剪速度； 在文献【3 7 】中，他将多边形的边视为有向线段，通过引入多边形顶点 的入边及出边交点酋概念，设计出一种集匮与多边形的区域重叠判 断与重叠区域确定于一体的算法；在文献【3 8 】中，他针对凸多边形， 给出了一个避形窗目对其裁剪的算法。该算法通过引入进、出交点 的概念，解决了如何确定凸多边形被圆形窗口裁剪后封闭区域的边 界问题；在文献【3 9 】中，他先做相交性判断，再求交点，仅当多边形 的边与圆相交时，才求交点，从而加快了裁剪速度。另外，王书文 等也给出了一种圆形窗阴上一般多边形的内外裁剪算法 4 1 】。 ：( 2 ) 椭濯窗瑟麴多边形裁剪。专门讨论椭圆形密叠对多边形裁剪 的相关文献至今未见。 1 2 8 其它方面的裁剪 也有入正在进行对文字的裁剪、对圆或椭圆的裁剪f 4 2 l 4 朝、对一 般曲线的裁剪等方面的研究工作。 9 哈尔滨工程大学硕士学位论文 1 3 裁剪研究的分析与总结 通过前一节关于国嚏外二维裁剪研究情况的了解，现进行如下 分析和总结。 1 3 1 裁剪主要的工作 裁剪处理主簧体现在两方面：一是判断窗罱与裁剪对象的位置 关系；二是求窗口与裁剪对象的交点。为了设计出效率较高的裁剪 算法，人们都在这两方瑟傲文章。有的入充分研究窗口与裁剪对象 的位置关系，给出非常详细的判别方法，能够尽量排除不相交的情 形，减少求交次数，提高裁剪的效率：有的人深入研究熊够避免复 杂的求交运算，尽量使用简单的运算快速求得交点，来提高裁剪的 效率。 当然，裁剪算法所采用的数据结构也是人们关注的个问题。 选用好的数据结构，不但影响存储空间的效率，也会影响时间效率。 复杂的数据结构在建立、维护和遍历时都要花费很多的时闫。 1 3 2 二维裁剪为基础 虽然裁剪可以分为二维裁剪和三维裁剪，但是，二维裁剪是最 基础的、最常用的操作。因为有的二维裁剪算法可直接或稍微修改 就能推广到三维空间中去应用而变成三维裁剪算法。另外，在绘制 图形时，般先将三维物体进行投影变换，然后再进行二维裁剪选 择要绘制的部分。有鉴于此，人们对二维裁剪研究最多，成果也最 多。 王0 哈尔滨工程大学硕士学僦论文 1 3 3 关于线段裁剪 矩形窑墨、多边形窗口对线裁剪的研究工作开展得最早，也最 深入，已经设计出了许许多多有效的好算法。可以说，这方面的研 究工作基本成熟。特别是，矩形窗口对直线段裁剪的研究比较深入 和透彻，这方面的工作做得比较完美。 如果说在线段裁剪方面还有不尽人意的地方的话，那就是圆形 ( 或椭圆) 窗口对直线段的裁剪。造成这种结果的原因是多方面豹， 例如：由于圆( 或椭圆) 的方程是二次的，求圆( 或椭圆) 与线段 或线段直线的交点需要鬃二次方程；由予判断凰( 或椭藏) 与线段 或线段直线是否相交一般都要求两点的距离，需要开方运算。尽管 如此，还是有许多学者在这方面取得了可喜的成采。例如：有入设 计基于像素的裁剪算法能够避免求交运算，但其只能应用于图像的 裁剪，适用面较窄。有入在六焦网格上磷究圆对直线段裁剪问题， 设计出的裁剪算法确实避免了通过解二次方程的求交运算，理论超 前。但是，不得不承认的是，基于六角网格的显示器还未见到或普 及，他们的成果还不能得到实际应用。有入制备规范化交点表，逶 过映射法查表实现圆形窗口对线段的裁剪避免了线圆求交、点线距 离及点点距离计算。但是，这种算法在规范诧交点表的建立和查找 方面都很费时。还有的算法为了尽量将圆与直线段的位置关系分得 清楚面减少求解次数，做了大量的辅助工作，譬如实施了旋转变换， 这又涉及了三角函数的运算。还有的算法避免了求解二次方程，但 没有避免开方运算。总之，圆( 或椭圆) 对直线段的裁剪工作还需 要进一步的深入开展。 王3 。4 关于矩形、多边形对多边形的裁剪 在实际应用中，多边形裁剪与线段裁剪相比具有更高的使用率， 多边形裁剪是目前裁剪研究的主要课题。 哈尔滨工程大学硕士学位论文 i i l l i i i l l li ii i i l l l l l | 皇黛瞄高皇 多边形作为裁剪对象的情况比较复杂。虽然多边影是由首尾相 连的若干直线段组成，但是也不能把现有的线段裁剪算法拿过来对 多边形这个线段集合直接进行裁剪，否则会破坏裁剪结果的封闭性。 因此，对多边形的裁剪需要专门的裁剪算法。一般使用四条边与屏 幕边缘平行的矩形作为裁剪窗口，这个特殊性便于求解窗口边与裁 剪线段的交点，矩形窗霸对多边形裁剪的研究，人们做得较好。 对于多边形窗口对多边形的裁剪，特别是任意多边形( 包括带 孔的) 对任意多边形( 包括带孔的) 的裁剪还存在着许多令人不满 的地方，这方面的工作还需要进一步的完善。 1 3 5 圆对多边形裁剪算法的相关情况 圆对多边形的裁剪比圆对直线段的裁剪、多边形对多边形的裁 剪要复杂得多、困难得多。圆的方程为二元二次方程，较为复杂； 多边形是壶首尾相连的些线段组成的辫闭区域，裁剪结果也应该 要求是封闭的( 个或几个封闭区域) ，裁剪时多边形产生的缺网要 用相应的墓弧来补充；圆形窑躁与多边形的位置关系相当复杂舔且 不易判别，其中可能需要开方运算( 如求两点的距离) ；求交运算也 不易避免解算二次方程；计算霉弧的起始焦度和终端角度，需要三 角函数或反三角函数运算。这些都影响着圆对多边形裁剪的效率。 ( 1 ) 多数算法都采用圆的距离形式方程( 或参数方程) 和直线的 参数方程，最后通过求解一个二次方程来得到交点的参数。解二次 方程效率低，这是缺点；其优点是易求出用来补裁剪缺口的圆弧的 起始是度和终端角度。 ( 2 ) 有的算法是首先计算出圆与多边形边直线的交点的参数，蒋 根据参数的范凰来判断该交点是不是蘧与多边形边的交点。这样会 进行很多没必要的求交运算，大大增加计算量，降低裁剪速度。 ( 3 ) 有的算法是首先研究圆形窗口与多边形的位置关系，然后作 圆形窗暖与多边形边或边直线相交性的判别。这种算法的优点是仅 当相交时才计算交点，减少了不必要的求交次数，从而加快了裁剪 王2 哈尔滨工程大学硕士学位论文 速度。另一方面，这种思想也会造成极端，朗为了尽量降低求交次 数，使判别圆与多边形位置关系、圆与多边形边位置关系的方法过 于详细和复杂。在降低求交的时阋复杂度的同时，反而提高了判别 的时间复杂度，得不偿失，并且还会大大降低算法的阅读性。算法 的阅读性虽然不能像时间复杂度那样给出定量的分析，但是阅读性 确实是衡量算法优劣的个非常重要的指标，应该予以重视。 ( 4 ) 有的算法为了提高裁剪的效率，对多边形加以限制，如对凸 多边形的裁剪。当然，这也限制? 嚣对多边形裁剪熬应瘸范围。 l 。3 。6 椭圆对多边形裁剪算法的相关情况 椭圆对多边形裁剪的难度要比圆对多边形裁剪还要大。圆只有 一个半径，椭圆有长半轴与短半轴之分，椭圆方程比圆方程复杂， 椭圆不具有圆的所有特性。所以，适合圆窗口裁剪的算法不一定适 合椭圆形窗口的裁剪，必须充分根据椭圆的特性及椭圆与多边形的 位置关系，深入研究椭圆对多边形裁剪的方法，设计出快速的椭圆 对多边形裁剪的专门算法。 目前，虽然有圆对多边形裁剪方面的文章，但在计算机学报、 软件学报和计算机研究与发展等国家一级刊物上还未见到 过这方面的文章。圆对多边形裁剪的进展还不如圆对直线段裁剪、 多边形对多边形裁剪的进展。总之，圆和椭圆对多边形的裁剪至今 未有突破性的进展，要做的工作还很多。 由于图形系统具有处理数据量大的特点，对计算机图形学中的 算法，哪怕有一点点的改进，都是令人可喜的一俘事。所以，可以 在圆和椭圆对多边形裁剪方面继续深入探究，设计出一个阅读性、 时间复杂度和空闻复杂度( 在这主要体现的是数据结构) 都比较均 衡的实用的圆( 或椭圆) 对多边形裁