改进的六角网格系统上矩形窗口裁剪算法*

付文超,张传林

(暨南大学 信息科学技术学院，广东 广州 510632)

裁剪是计算机图形学中的一个重要内容，它能对图形做出正确的判断，去除不可见部分，选取可见信息提供给显示系统进行显示。目前研究的裁剪算法很多，矩形窗口的图形裁剪算法更是使用最广泛的一类算法，但这些算法都是基于方形网格系统提出和实现的。而早在20世纪60年代初,数学家们就已经提出了平面上点的最佳分布是按六角网格分布的[1]，这种分布就是用正六边形来覆盖整个平面，每个像素对应着一个正六边形，将正六边形的中心点作为网格点。相比于方形网格系统，六角网格系统具有更好的图形图像显示特性[2-4]，因此基于六角网格显示系统的图形生成和处理算法的研究已成为了发展的必然。

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

总体来说，六角网格上的裁剪操作要比方形网格上麻烦，参考文献[5]和参考文献[6]中分别给出了一种基于六角网格的矩形窗口的线段和圆裁剪算法，参考文献[7]给出了一种基于六角网格的圆形窗口的裁剪算法。这几种算法都是基于传统60°角六角网格系统提出的，算法处理比较复杂，导致六角网格系统优于方形网格系统的特性不再明显。本文基于类直角坐标系的六角网格系统提出了一种改进的矩形窗口图形裁剪算法，算法的复杂程度远远低于基于传统60°角六角网格系统的相关算法。

1 两种六角网格系统的比较

传统60°角六角网格系统与方形网格系统的关系：传统60°角六角网格系统上的任何一个点的坐标(x′,y′),都可以通过变换：

转换成方形网格坐标(x,y)。

在方形网格显示设备上模拟显示传统60°角六角网格系统，如图1所示。

基于类直角坐标系的六角网格系统与方形网格系统的关系：基于类直角坐标系的六角网格系统上的任何一个点的坐标(x′,y′)，都可以通过变换：

转换成方形网格坐标(x,y)，其中 r0=mod(y′,2)。

在方形网格显示设备上模拟显示基于类直角坐标系的六角网格系统，如图2所示。

在传统60°角六角网格系统上设矩形窗口裁剪算法要比在方形网格系统上麻烦,这是因为在传统60°角六角网格系统上窗口的垂直边界需要用一条斜线来表示，而不是用常数表达式来表示。

在基于类直角坐标系的六角网格系统上，设矩形窗口左下角点的坐标为(xl,yb)，右上角点的坐标为(xr,yt)，则矩形窗口的上边界和下边界表达式为 y=yt和y=yb。至于矩形窗口的左边界和右边界，可基于类直角坐标系的六角网格的排布特点（如图3所示）来确定。

根据左下角的点(xl,yb)，可以知道矩形窗口左边界的方程为x=xl，是一个常数表达式。但是，如果纵坐标yb为偶数，则左边界x=xl直线上六角网格的排布就如图4(a)所示；如果纵坐标 yb为奇数，则左边界 x=xl直线上六角网格的排布就如图4(b)所示。

同样地，根据右上角的点(xr,yt)，矩形窗口的右边界的方程为x=xr，也是一个常数表达式。如果纵坐标 yt为偶数，则右边界x=xr直线上六角网格的排布就如图5(a)所示；如果纵坐标yt为奇数，则右边界 x=xr直线上六角网格的排布就如图5(b)所示。

综上所述，可以在模拟实现的基于类直角坐标系的六角网格系统平台上生成一个矩形窗口，如图6所示。

2 基于类直角坐标系的六角网格上的矩形窗口裁剪算法

前面已经在六角网格系统模拟平台生成了矩形窗口，下面讨论基于类直角坐标系的六角网格上的矩形窗口裁剪算法，并给出一个在矩形窗口中裁剪圆的操作实例。

圆在基于类直角坐标系的六角网格系统中的方程为：

其中，(x0,y0)为圆心坐标，(x,y)和(x0,y0)均为六角网格系统中的坐标，R为圆的半径。

圆与矩形窗口的位置关系，有包含、相离、相交三种。对于包含和相离的情况，裁剪操作很容易处理。对于相交的情况，必须求出交点坐标，并且把交点分为入点和出点两类：入点即圆在该点处进入矩形窗口,出点即圆在该点处离开矩形窗口。由于圆是封闭曲线，因此如果圆在某一个点处进入矩形窗口，那么在它再次进入矩形窗口之前，中间必须有一个第三点使得圆先离开矩形窗口，即：在矩形窗口的边界上，不会有相邻的两个入点；同理，在矩形窗口的边界上，也不会有相邻的两个出点。

2.1 算法描述

在基于类直角坐标系的六角网格系统上使用矩形窗口裁剪圆曲线的流程是：先判断圆与矩形窗口是否包含或者相离，如果是，则裁剪算法结束；否则，求出圆与矩形窗口边界的交点，并进行裁剪操作。

2.1.1 整个圆在矩形窗口内部(包含关系)

如果x坐标的最大值、最小值和y坐标的最大值、最小值满足：

则整个圆在矩形窗口内部，如图7所示，这种情况下不需要裁剪，整个圆在矩形窗口中都得到显示。

2.1.2 整个圆在矩形窗口外部（相离关系）

如果x坐标的最大值、最小值和y坐标的最大值、最小值满足：则整个圆在矩形窗口外部，如图8所示，这种情况下不需要裁剪，整个圆在矩形窗口中都没有显示。

2.1.3 圆部分在矩形窗口内部,部分在矩形窗口外部（相交关系）

圆与矩形窗口相交是裁剪算法中最复杂的部分，这种情况下需要求出圆与矩形窗口的交点，并将窗口外的部分裁剪掉，显示窗口内的部分。

将矩形边界 方程 x=xl、x=xr、y=yb和 y=yt与 圆 的 方程联立，求出所有交点坐标，写入交点集合I。如果某个边界与圆相切，只有一个交点，则该点不写入交点集合。

(1)矩形窗口与圆有 8个交点，如图 9所示，记最下方交点中靠左的交点为I1，然后按照逆时针顺序依次记其他交点为 I2,I3,…,I8。

判断I1是出点还是入点，方法是：如果I1在矩形窗口的下边界上，则将I1=(x,yb)的横坐标增加1并代入圆的方程，可求出相应的纵坐标y′有两个，取圆弧上I1沿逆时针方向的下一个点 I1′=(x+1,y′)，如果 y′>yb，则 I1为入点，否则 I1为出点；如果I1在矩形窗口的右边界上，则将I1=(xr,y)的纵坐标增加1并代入圆的方程，求出圆弧上I1沿逆时针方向的下一个点 I1′=(x′,y+1)，如果 x′xl，则 I1为入点，否则 I1为出点。

如果 I1为出点 ， 则圆弧 I2I3、I4I5、I6I7、I8I1位于窗口内部，将其余部分裁剪掉；如果I1为入点，则圆弧 I1I2、I3I4、I5I6、I7I8位于窗口内部， 将其余部分裁剪掉。

(2)矩形窗口与圆的交点少于8个，如图10所示，仍然记最下方靠左的交点为I1，如果不存在这样的I1，则按照逆时针顺序，将遇到的第一个交点记为I1，其余交点顺次标记。然后按照(1)中的步骤进行裁剪操作。

2.2 算法模拟实现

对本文提出的算法进行模拟,结果如图11～图14所示。

2.3 算法分析

由于六角网格系统的特殊性，一些在方形网格系统中比较简单的公式在六角网格系统下就变得比较复杂，本文给出的基于类直角坐标系的六角网格系统的相关算法对该问题做了简化，具有以下优点：

(1)矩形窗口的左右边界也是一条简单的垂直线，可以用常数表达式来表示，这样就可以大大降低算法的计算量;

(2)算法处理速度快。本算法分三种情况来讨论圆与矩形窗口的关系，前期先判断圆与矩形窗口是否为包含或者相离的关系，通过简单的比较运算来替代复杂的求交运算，减少了计算量;

(3)简化了入点和出点的判断。本算法利用封闭图形的入点和出点在矩形窗口边界上交互出现，只需判断一个起始点为入点或出点，然后按照逆时针顺序，根据入点和出点交互分布的原则依次判断其他点是入点或出点。

在基于类直角坐标系的六角网格系统上，矩形窗口的边界可以用常数表达式来表示，这大大简化了六角网格系统上图形裁剪算法的研究。由于这类六角网格系统上矩形窗口边界表达式与方形网格系统上矩形窗口表达式形式一致，可以将方形网格系统上的其他图形图像处理算法直接或间接地移植到该类六角网格系统上。此外，本文给出的算法具有一定通用性，只需将图形方程进行变化，即可适用于其他图形图像的矩形窗口裁剪。

[1]ROGERS C A.Packing covering[M].Cambridge：Cambridge University Press,1964.

[2]TIRUNELVELI G,GORDON R,PISTORIUS S.Comparison of square-pixel and hexagonal-pixel resolution in image processing[J].Proceedings of the 2002 IEEE Canadian Conference On Electrical&Computer Engineering.

[3]CONDAT L,Dimitri Van De Ville,BLU T.Hexagonal versus orthogonal lattices:a new comparison using approx-imation theory[J].ICIP:IEEE International Conference on Image Processing,2005,3:11-14.

[4]刘勇奎,邹善举.六角网格上的图像算法及几何量定义[J].计算机工程与设计,2000,21(1):61-64.

[5]赵慧杰,晏俊德,刘勇奎,等.六角网格单色显示器及图形算法研究[J].沈阳工业大学学报,1997,19(5):66-71.

[6]韩丽.基于六角网格的矩形窗口的圆裁剪算法[J].锦州师范学院学报(自然科学版),2003,24(4):64-66.

[7]孙长嵩,李丽洁,宋阳.一个基于六角网格的圆形窗口的裁剪算法[J].交通科技与经济，2006,33(1):78-80.

[8]付文超,罗小华,张文争,等.改进的六角网格下椭圆绘制算法[J].暨南大学学报(自然科学与医学版).已录用，待刊登.