一个基于六角网格的圆形窗口的裁剪算法

基于矩形窗口分区编码的圆形裁剪新算法王蕊;阎晓敏;唐棣【摘要】裁剪是计算机图形学中基本问题之一,其核心问题是效率问题,而矩形窗口是常用的裁剪边界.在分析现有圆裁剪算法的基础上,提出了基于矩形窗口分区编码的圆裁剪算法,首先根据圆的八分对称性求出圆周的关键点,然后按规则进行编码,从而判断圆与矩形窗口的相交关系,并对圆进行相应的裁剪输出.实验结果表明,该算法减少了复杂运算的次数,避免了多余的无用计算,具有较高的运算效率.【期刊名称】《辽宁大学学报（自然科学版）》【年(卷),期】2011(038)002【总页数】4页(P177-180)【关键词】矩形窗口;编码;圆形;裁剪;计算机图形学【作者】王蕊;阎晓敏;唐棣【作者单位】辽宁师范大学,计算机与信息技术学院,辽宁,大连,116029;沈阳音乐学院大连校区计算机教研组,辽宁,大连,116650;辽宁师范大学,计算机与信息技术学院,辽宁,大连,116029【正文语种】中文【中图分类】TP311.520 引言在计算机图形处理系统中，裁剪是一项经常而必需的操作，其原理是在一个窗口内显示一个大画面的局部内容，窗口内的内容得以显示，窗口外的内容被裁剪去除.但受当前显示屏和鼠标指针操作的限制，常用的裁剪窗口多为矩形［1］.基于矩形窗口的线裁剪［2，3］和多边形裁剪已有许多经典算法，如 Cohen—Sutherland 算法［4］、中点分割算法［5］、梁—Barsky 算法［6］，Sutherland—Hodgon［1］算法以及 Nicholl—Lee—Nicholl算法［7］等.而在实际应用中，圆形裁剪的操作也十分普遍，如二维动画的设计、机械构件的检测、机器人运动学等，由于圆属于二次曲线，因此，采用原始的类圆形逼近生成的裁剪算法将会造成复杂的计算和较低的效率.为此，一些学者对圆形裁剪进行了研究，提出了相应的算法，如:文献［8］提出的基于矩形窗口的圆曲线裁剪算法，利用坐标变换的原理对圆形进行空间预处理，得到裁剪结果;文献［9］提出的任意多边形的圆形裁剪算法，以单条直线与圆形相交的计算为基础，将圆形分段为圆弧进行裁剪.现有的算法都能对圆形进行有效的裁剪，但从裁剪复杂度与算法实用性的角度来考察都存在一些局限.本文提出一种基于矩形窗口编码的圆裁剪算法，采用矩形分区编码的方法［1，10～12］进行圆形位置以及圆与矩形窗口相交情况的判定，快速完成矩形窗口对圆的裁剪，实验结果证明了本方法的有效性.1 矩形窗口与圆形的位置判断在二维平面空间中，圆与矩形的相交情况共有五种:(1)无交点:圆在矩形窗口外或圆全部在矩形窗口内，如图1－a;(2)有2n个交点(1≤n≤4):有n段圆弧裁剪结果，如图1－b，c，d，e(以圆心在矩形内部为例);由于圆属于二次曲线，与矩形的相交情况较为复杂，且圆并不一定与矩形四个边界都有相交，因此，为避免因无相交边的求交运算而产生多余的操作，本方法对圆与矩形的相交情况进行了编码预处理:首先，根据圆的八分对称性求出圆的八个关键特征点，再根据特征点的编码结果快速判断圆与矩形的相交情况，从而为裁剪提供依据.图1 圆与矩形的相交情况示例(a.圆与矩形无交点;b.圆与矩形有2个交点;c.圆与矩形有4个交点;d.圆与矩形有6个交点;e.圆与矩形有8个交点)1.1 圆形关键点圆形在几何上具有完全对称的特性，其中八分对称的计算较简单，可以由一个点同时计算出其他七个点，且能完整地表达圆，因此，本方法选用圆周上0°、45°、90°、135°、180°、225°、270°、315°八个角度的点作为圆的特征点，记为(xi，yi)，其中i∈［1，8］，将其作为接下来分区编码、判断是否相交的基础.1.2 矩形窗口分区编码设矩形窗口两个对角的顶点坐标为(xa，ya)、(xb，yb)，其中xa≤xb、ya≤yb.将矩形窗口的边界延长成直线，则把二维平面分成九个区域，本方法规定:每个区域对应一个四位编码，编码意义如下(以二进制形式自右向左给出，如图2):第0位:若点在窗口下边界的下方(即yi＜ya)，则为 1，否则为 0，记为 B［i］;第1位:若点在窗口上边界的上方(即yi＞yb)，则为1，否则为0，记为 U［i］;第2位:若点在窗口右边界的右方(即xi＞xb)，则为1，否则为0，记为 R［i］;第3位:若点在窗口左边界的左方(即xi＜xa)，则为 1，否则为 0，记为 L［i］;图2 窗口分区编码根据编码规则，圆周的每个关键点都具有一个对应的四位二进制编码，该圆则具有八组二进制编码.对圆与矩形各种相交情况下圆的八组编码进行统计可以得出规律，即:(1)将八组编码按照对应位求和，可得到SUM(B)、SUM(U)、SUM(R)、SUM(L)，再将四个算术和中非零的数字求乘积，其奇偶性决定了圆与矩形是否相交;(2)算术和中非零数字对应的位决定了圆与矩形具体相交的边.通过圆形关键点在矩形窗口分区中的编码统计，可以快速判断圆与矩形不相交的情况;在相交的情况下亦可快速判断相交边，从而避免了无用的求交运算.2 基于矩形窗口的圆裁剪算法及实现前文介绍了根据矩形窗口分区编码进行的快速判断，判断结果包括圆是否与矩形相交以及具体相交的边界位置，接下来对此结果进行进一步判断以得到最终的裁剪结果:设圆心坐标为(x0，y0)，半径为 r.(1)若圆与矩形无交点，判断(x0，y0)与(xa，ya)、(xb，yb)的关系，若 xa＜x0＜xb且 ya＜y0＜yb，则圆全部在矩形窗口内，裁剪输出整圆，否则，圆全部在矩形窗口外，输出整个矩形窗口;(2)若圆与矩形有交点，分别判断交点是否在算术和非零的边上，进一步去除没有相交的“伪边”，在真实相交边上求交点，输出边界内圆弧.2.1 算法框架按照上述原理，可以得出本方法的基本框架，如图3所示.图3 算法框架2.2 算法的描述与实现根据上述基本框架，可以得出算法具体的实现步骤:Step1:输入矩形对角顶点坐标(xa，ya)、(xb，yb)，圆心坐标(x0，y0)，半径 r;计算圆周上0°、45°、90°、135°、180°、225°、270°、315°八个角度的特征点Pi(xi，yi)，i∈［1，8］;Step2:按规则对Pi进行编码，分别按位存入数组 E(j)，j∈［1，4］，并分别求算术和 SUM(j)(E(j)为上文提到的 B［i］、U［i］、L［i］、R［i］的集体数组表示); Step3:求SUM中非零数的乘积M，若M是偶数，转Step4;否则，其中非零数对应的可能是相交边，转Step5;Step4:若xa＜x0＜xb且 ya＜y0＜yb，输出整圆，转Step6;否则，输出整个矩形窗口，转Step6;Step5:分别求圆心(x0，y0)与非零数对应边的距离 d1、d2，并使d1≥d2，若d1 ＞r，则是真实相交边，求出圆与边界交点，输出边界内的圆弧，转Step6;否则，则是“伪边”，转Step5继续判断;若非零数对应边均为“伪边”，输出矩形窗口，转Step6;Step6:结束退出.3 结果分析与总结本文从实际应用的角度出发，以符合显示标准的矩形窗口对特殊图形——圆形进行裁剪的方法进行了分析研究，将矩形窗口的边界延长，对分出的每个区域进行二进制编码，从而在较低运算量的前提下完成了圆与矩形相交关系的快速判断，并为进一步求交点、裁剪等后续工作提供了数据;在接下来的裁剪过程中，对每条非零数对应边进行二次相交判定，从中去除“伪边”以及“全伪边”，而对于真实相交边则可以快速地完成求交点及圆弧段输出的操作.与文献［8］的算法进行比较，本文方法在前期通过分区编码的预处理分析了圆与矩形相交的可能情况，预先得到了对于相交情况以及裁剪形式的规定，可以不必对每条边都进行相交的判断，因而计算量少、算法简单，不存在误判的情况，具有较好的稳定性;在裁剪过程中，本文方法根据预先的筛选结果来确定相交的边界，可以快速有序地进行求交点和裁剪输出，避免了多余的无用计算(算法具体对比如表1、表2所示).因此，本文方法复杂度低、执行速度快，能够有效地应用于实际的裁剪操作中.当然，本文方法只考虑了圆形的完全对称特性，而未利用矩形的中心对称特性.接下来的工作将进一步研究矩形的对称性对于裁剪的意义以及在裁剪具体环节中的应用.表1 本文算法与文献［8］算法复杂度对比注:表1中以N个圆与矩形相交的情况为例减法乘法判断开平方文献［8］算法 12N次 2N次 12N次 3N次加、本文算法 10N次 N次 9N次 3N次表2 本文算法与文献［8］算法的裁剪过程对比求交点过程文献［8］算法是否预处理是否各边都需计算与判断个数分别处理本文算法是.平移预处理，使矩形中心与圆中心重合是按照与边的交点是.分区编码，提前确定相交边否.只需处理编码结果中判断出的相交边交点计算简单，按序记录，便于输出裁剪结果参考文献:【相关文献】［1］何援军.计算机图形学［M］.北京:机械工业出版社，2006，1.［2］余加红，邹稳纯.采用动态基线的矩形窗口的裁剪算法［J］.工程图学学报，2007，4:36 －39.［3］彭艳莹，陆国栋，李基拓，王进.基于包围盒编码的三维线段裁剪新算法［J］.计算机辅助设计与图形学学报，2003，11.［4］Newman W.M.，Sproull R.F..Principles of Interactive computer graphics［M］.New York:McGraw －Hill，1979:chapter5.［5］Sproull R.F.，Sutherland I.E..Aclipping diliver［M］.In:FallJointComputerCon.1968，Washington:Thompson Books，765 －775.［6］Liang Y.D.，Barsky B.A..A new concept and method for line cipping［C］.ACM Trans.On Grphics，1984(3):1－22.［7］Nicholl T.M.，Lee D.T.，Nicholl R.A..An efficient new algorithn for 2－D line cipping:Its development and analysis［J］.Computer ＆ Graphics，1987，21(4):253－263. ［8］孙岩，唐棣.矩形窗口的曲线裁剪算法［J］.计算机应用与软件，2003，20(5):35 －36，56. ［9］杭后俊，孙丽萍.任意多边形窗口的圆裁剪算法［J］.计算机技术与发展，2009，19(5):235 －241.［10］陆国栋，邢军伟，谭建荣.基于多重编码技术的圆形窗口线裁剪算法［J］.计算机辅助设计与图形学学报，2002，14(12):1133 －1137.［11］彭欢，陆国栋，谭建荣.基于端点与交点编码的矩形窗口多边形裁剪新算法［J］.工程图学学报，2006，4.［12］何陈祺，陆国栋，谭建荣.基于编码与分类技术的任意多边形裁剪新算法［J］.工程图学学报，2003，21.。

基于适应性相关测试和点斜式查表求交的圆形窗口快速裁剪方法路通;苏丰;杨若瑜【摘要】在智能CAD、图形识别与理解等复杂图形应用系统中,由于图元数量多、图元间关系复杂,且系统实时交互响应要求较高,现有圆形窗口裁剪算法较难满足要求.为此提出圆形窗口对线段的一种新的快速裁剪算法.该算法由基于切线分隔的圆外线段快速适应性测试方法、基于最小范围的圆内线段测试方法和基于点斜式查表的线段与窗口圆快速求交方法三部分组成.通过按端点位置选择适应的测试方法、尽量避免不必要的操作、尽量以简单操作代替复杂操作等措施,大大提高了圆形窗口对线段的裁剪速度.在图形识别及智能CAD等应用中的实验结果表明,采用文中算法可较大地提高效率.%Existing circular window clipping algorithms are inefficient for many complex real-life applications like intelligent CAD and graphics recognition/understanding systems, due to their large number of graphical primitives, complicated geometrical constraints and real-time interaction requirements. This paper presents a fast line clipping algorithm against circular windows. The proposed algorithm is composed of three parts: adaptive identification of invisible lines based on tangent lines separation, fast identification of visible lines based on polygons cutting, and fast line-arc intersections generation based on predefined tables retrieval. Experimental results demonstrate that the proposed algorithm greatly reduces the computational cost to clip lines by adaptive line-circle situation analysis and replacement of time-consuming operations with simpler ones.【期刊名称】《图学学报》【年(卷),期】2012(033)006【总页数】10页(P14-23)【关键词】查表;圆形窗口;快速裁剪;适应性相关测试【作者】路通;苏丰;杨若瑜【作者单位】南京大学计算机软件新技术国家重点实验室,江苏南京210093;南京大学计算机软件新技术国家重点实验室,江苏南京210093;南京大学计算机软件新技术国家重点实验室,江苏南京210093【正文语种】中文【中图分类】TP391.41裁剪算法是计算机图形学的基础性方法，速度更快的算法一直是研究者的不断追求。

改进的六角网格系统上矩形窗口裁剪算法付文超;张传林【摘要】基于类直角坐标系的六角网格系统的特点,提出了一个用矩形窗口裁剪圆的算法,该算法中矩形窗口的左右边界可以用常数表达式表示,相比于传统60°角六角网格系统,算法复杂度大大降低.算法中对圆的裁剪操作分圆与矩形窗口包含、相离、相交三种情况,在包含和相离的情况中,用简单的比较运算代替复杂的求交运算,大大降低了算法的计算量.【期刊名称】《微型机与应用》【年(卷),期】2010(029)022【总页数】5页(P44-48)【关键词】六角网格系统;类直角坐标系;裁剪算法;算法模拟实现【作者】付文超;张传林【作者单位】暨南大学信息科学技术学院,广东广州510632;暨南大学信息科学技术学院,广东广州510632【正文语种】中文【中图分类】TP391.41裁剪是计算机图形学中的一个重要内容，它能对图形做出正确的判断，去除不可见部分，选取可见信息提供给显示系统进行显示。

目前研究的裁剪算法很多，矩形窗口的图形裁剪算法更是使用最广泛的一类算法，但这些算法都是基于方形网格系统提出和实现的。

而早在20世纪60年代初,数学家们就已经提出了平面上点的最佳分布是按六角网格分布的[1]，这种分布就是用正六边形来覆盖整个平面，每个像素对应着一个正六边形，将正六边形的中心点作为网格点。

相比于方形网格系统，六角网格系统具有更好的图形图像显示特性[2-4]，因此基于六角网格显示系统的图形生成和处理算法的研究已成为了发展的必然。

本文给出了一种基于类直角坐标系的六角网格系统，并将其在方形网格显示设备上进行模拟显示，以作为六角网格系统上相关算法实现的模拟平台。

总体来说，六角网格上的裁剪操作要比方形网格上麻烦，参考文献[5]和参考文献[6]中分别给出了一种基于六角网格的矩形窗口的线段和圆裁剪算法，参考文献[7]给出了一种基于六角网格的圆形窗口的裁剪算法。

这几种算法都是基于传统60°角六角网格系统提出的，算法处理比较复杂，导致六角网格系统优于方形网格系统的特性不再明显。

基于端点区域分布的圆形窗口线裁剪算法
圆形窗口线裁剪算法是一种常用的计算机图形学算法，用于在计算机
图形学中对线段进行裁剪。

而基于端点区域分布的圆形窗口线裁剪算
法则是一种更加高效的圆形窗口线裁剪算法。

该算法的基本思想是将圆形窗口分为四个象限，然后根据线段端点所
在的象限来判断线段是否需要进行裁剪。

如果线段的两个端点都在同
一个象限内，则该线段不需要进行裁剪；如果线段的两个端点分别在
两个不同的象限内，则需要对线段进行裁剪。

在实现该算法时，需要先将线段的端点坐标转换为相对于圆形窗口中
心点的坐标。

然后根据端点的坐标值来判断端点所在的象限。

如果两
个端点都在同一个象限内，则该线段不需要进行裁剪；如果两个端点
分别在两个不同的象限内，则需要对线段进行裁剪。

在进行裁剪时，需要根据线段与圆形窗口的交点来确定裁剪后的线段。

具体来说，需要计算出线段与圆形窗口的交点，然后根据交点的坐标
值来确定裁剪后的线段。

该算法的优点是可以快速地判断线段是否需要进行裁剪，从而提高了
算法的效率。

同时，该算法还可以处理多条线段的裁剪，从而更加适
用于实际应用中的图形处理。

总之，基于端点区域分布的圆形窗口线裁剪算法是一种高效的圆形窗口线裁剪算法，可以快速地判断线段是否需要进行裁剪，并可以处理多条线段的裁剪。

该算法在计算机图形学中有着广泛的应用，是一种非常重要的算法。

基于矩形窗口分区编码的圆形裁剪新算法
王蕊;阎晓敏;唐棣
【期刊名称】《辽宁大学学报（自然科学版）》
【年(卷),期】2011(038)002
【摘要】裁剪是计算机图形学中基本问题之一,其核心问题是效率问题,而矩形窗口是常用的裁剪边界.在分析现有圆裁剪算法的基础上,提出了基于矩形窗口分区编码的圆裁剪算法,首先根据圆的八分对称性求出圆周的关键点,然后按规则进行编码,从而判断圆与矩形窗口的相交关系,并对圆进行相应的裁剪输出.实验结果表明,该算法减少了复杂运算的次数,避免了多余的无用计算,具有较高的运算效率.
【总页数】4页(P177-180)
【作者】王蕊;阎晓敏;唐棣
【作者单位】辽宁师范大学,计算机与信息技术学院,辽宁,大连,116029;沈阳音乐学院大连校区计算机教研组,辽宁,大连,116650;辽宁师范大学,计算机与信息技术学院,辽宁,大连,116029
【正文语种】中文
【中图分类】TP311.52
【相关文献】
1.基于端点与交点编码的矩形窗口多边形裁剪新算法 [J], 彭欢;陆国栋;谭建荣
2.基于继承性的圆形窗口多边形裁剪新算法 [J], 邢军伟;陆国栋;谭建荣
3.基于多重编码技术的圆形窗口线裁剪算法 [J], 陆国栋;邢军伟;谭建荣
4.基于矩形窗口裁剪的圆形窗口裁剪算法 [J], 邹北骥
5.基于二重编码和坐标变换圆形窗口对直线裁剪的算法 [J], 杜宏明;姚红卫;朱楷因版权原因，仅展示原文概要，查看原文内容请购买。

一种有效的圆形窗口线裁剪算法任洪海;张飞侠【摘要】根据线段两端点相对于圆形窗口的可能位置讨论裁剪结果.当两端点都在圆形窗口之外时,通过圆切线斜率与线段斜率的比较,及点区域判别来判断线段与窗口的相交情况.在确定线段与圆形窗口有交点的情况下,应用参数化形式求交运算,简化求交方程的构造.实验结果表明,新算法显著提高了裁剪效率.%The result of clipping is discussed according to possible positions for both endpoints of a line segment in relation to circular window. The intersection is determined by comparing the slope of the tangent with the slope of the line segment and the ingenious region detection about the point when both endpoints of the line segment are outside of the circular window. Simplify the intersection equation by means of the intersection calculation with the parametric form when the intersection actually happens. The experimental results show that the new algorithm further improves the clipping efficiency.【期刊名称】《图学学报》【年(卷),期】2011(000)005【总页数】5页(P74-78)【关键词】计算机应用;圆形窗口线裁剪;斜率比较;区域判别【作者】任洪海;张飞侠【作者单位】大连交通大学软件学院计算机图形学教研室,辽宁大连,116052;辽宁对外经贸学院信息技术系,辽宁大连,116052【正文语种】中文【中图分类】TP391线裁剪是计算机图形学中的一个基本操作。

基于六角网格的矩形窗口的圆裁剪法
韩丽
【期刊名称】《渤海大学学报（自然科学版）》
【年(卷),期】2003(024)004
【摘要】裁剪作为计算机图形学中的一个重要内容,目前研究的算法很多,尤其在矩形窗口的图形裁剪算法更是使用最广泛的一类算法,但其算法都是基于直角坐标系统提出和实现,而早在60年代初,一些数学家就已经提出了平面上点的最佳分面是按六角网格分布的,并于90年代末实现了六角网格的显示系统,基于六角网格显示系统的图形生成已成为了发展的必然,本算法基于六角网格系统的矩形窗口圆裁剪给出了具体算法和分析,此算法可以适用于在矩形窗口裁剪椭圆及其它对称的图形.【总页数】3页(P64-66)
【作者】韩丽
【作者单位】辽宁师范大学,计算机与信息技术学院,辽宁,大连,116029
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.基于AutoCAD下圆形窗口裁剪法 [J], 尉朝闻
2.一个基于六角网格的圆形窗口的裁剪算法 [J], 孙长嵩;李丽洁;宋阳
3.六角网格上的圆与椭圆生成算法 [J], 刘勇奎;邹善举;米守防;李春时
4.六角网格下圆的双步生成算法 [J], 唐棣;邹黎黎
5.改进的六角网格系统上矩形窗口裁剪算法 [J], 付文超;张传林
因版权原因，仅展示原文概要，查看原文内容请购买。