付文超,張傳林

(暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院，廣東 廣州 510632)

裁剪是計(jì)算機(jī)圖形學(xué)中的一個(gè)重要內(nèi)容，它能對(duì)圖形做出正確的判斷，去除不可見部分，選取可見信息提供給顯示系統(tǒng)進(jìn)行顯示。目前研究的裁剪算法很多，矩形窗口的圖形裁剪算法更是使用最廣泛的一類算法，但這些算法都是基于方形網(wǎng)格系統(tǒng)提出和實(shí)現(xiàn)的。而早在20世紀(jì)60年代初,數(shù)學(xué)家們就已經(jīng)提出了平面上點(diǎn)的最佳分布是按六角網(wǎng)格分布的[1]，這種分布就是用正六邊形來覆蓋整個(gè)平面，每個(gè)像素對(duì)應(yīng)著一個(gè)正六邊形，將正六邊形的中心點(diǎn)作為網(wǎng)格點(diǎn)。相比于方形網(wǎng)格系統(tǒng)，六角網(wǎng)格系統(tǒng)具有更好的圖形圖像顯示特性[2-4]，因此基于六角網(wǎng)格顯示系統(tǒng)的圖形生成和處理算法的研究已成為了發(fā)展的必然。

本文給出了一種基于類直角坐標(biāo)系的六角網(wǎng)格系統(tǒng)，并將其在方形網(wǎng)格顯示設(shè)備上進(jìn)行模擬顯示，以作為六角網(wǎng)格系統(tǒng)上相關(guān)算法實(shí)現(xiàn)的模擬平臺(tái)。

總體來說，六角網(wǎng)格上的裁剪操作要比方形網(wǎng)格上麻煩，參考文獻(xiàn)[5]和參考文獻(xiàn)[6]中分別給出了一種基于六角網(wǎng)格的矩形窗口的線段和圓裁剪算法，參考文獻(xiàn)[7]給出了一種基于六角網(wǎng)格的圓形窗口的裁剪算法。這幾種算法都是基于傳統(tǒng)60°角六角網(wǎng)格系統(tǒng)提出的，算法處理比較復(fù)雜，導(dǎo)致六角網(wǎng)格系統(tǒng)優(yōu)于方形網(wǎng)格系統(tǒng)的特性不再明顯。本文基于類直角坐標(biāo)系的六角網(wǎng)格系統(tǒng)提出了一種改進(jìn)的矩形窗口圖形裁剪算法，算法的復(fù)雜程度遠(yuǎn)遠(yuǎn)低于基于傳統(tǒng)60°角六角網(wǎng)格系統(tǒng)的相關(guān)算法。

1 兩種六角網(wǎng)格系統(tǒng)的比較

傳統(tǒng)60°角六角網(wǎng)格系統(tǒng)與方形網(wǎng)格系統(tǒng)的關(guān)系：傳統(tǒng)60°角六角網(wǎng)格系統(tǒng)上的任何一個(gè)點(diǎn)的坐標(biāo)(x′,y′),都可以通過變換：

轉(zhuǎn)換成方形網(wǎng)格坐標(biāo)(x,y)。

在方形網(wǎng)格顯示設(shè)備上模擬顯示傳統(tǒng)60°角六角網(wǎng)格系統(tǒng)，如圖1所示。

基于類直角坐標(biāo)系的六角網(wǎng)格系統(tǒng)與方形網(wǎng)格系統(tǒng)的關(guān)系：基于類直角坐標(biāo)系的六角網(wǎng)格系統(tǒng)上的任何一個(gè)點(diǎn)的坐標(biāo)(x′,y′)，都可以通過變換：

轉(zhuǎn)換成方形網(wǎng)格坐標(biāo)(x,y)，其中 r0=mod(y′,2)。

在方形網(wǎng)格顯示設(shè)備上模擬顯示基于類直角坐標(biāo)系的六角網(wǎng)格系統(tǒng)，如圖2所示。

在傳統(tǒng)60°角六角網(wǎng)格系統(tǒng)上設(shè)矩形窗口裁剪算法要比在方形網(wǎng)格系統(tǒng)上麻煩,這是因?yàn)樵趥鹘y(tǒng)60°角六角網(wǎng)格系統(tǒng)上窗口的垂直邊界需要用一條斜線來表示，而不是用常數(shù)表達(dá)式來表示。

在基于類直角坐標(biāo)系的六角網(wǎng)格系統(tǒng)上，設(shè)矩形窗口左下角點(diǎn)的坐標(biāo)為(xl,yb)，右上角點(diǎn)的坐標(biāo)為(xr,yt)，則矩形窗口的上邊界和下邊界表達(dá)式為 y=yt和y=yb。至于矩形窗口的左邊界和右邊界，可基于類直角坐標(biāo)系的六角網(wǎng)格的排布特點(diǎn)（如圖3所示）來確定。

根據(jù)左下角的點(diǎn)(xl,yb)，可以知道矩形窗口左邊界的方程為x=xl，是一個(gè)常數(shù)表達(dá)式。但是，如果縱坐標(biāo)yb為偶數(shù)，則左邊界x=xl直線上六角網(wǎng)格的排布就如圖4(a)所示；如果縱坐標(biāo) yb為奇數(shù)，則左邊界 x=xl直線上六角網(wǎng)格的排布就如圖4(b)所示。

同樣地，根據(jù)右上角的點(diǎn)(xr,yt)，矩形窗口的右邊界的方程為x=xr，也是一個(gè)常數(shù)表達(dá)式。如果縱坐標(biāo) yt為偶數(shù)，則右邊界x=xr直線上六角網(wǎng)格的排布就如圖5(a)所示；如果縱坐標(biāo)yt為奇數(shù)，則右邊界 x=xr直線上六角網(wǎng)格的排布就如圖5(b)所示。

綜上所述，可以在模擬實(shí)現(xiàn)的基于類直角坐標(biāo)系的六角網(wǎng)格系統(tǒng)平臺(tái)上生成一個(gè)矩形窗口，如圖6所示。

2 基于類直角坐標(biāo)系的六角網(wǎng)格上的矩形窗口裁剪算法

前面已經(jīng)在六角網(wǎng)格系統(tǒng)模擬平臺(tái)生成了矩形窗口，下面討論基于類直角坐標(biāo)系的六角網(wǎng)格上的矩形窗口裁剪算法，并給出一個(gè)在矩形窗口中裁剪圓的操作實(shí)例。

圓在基于類直角坐標(biāo)系的六角網(wǎng)格系統(tǒng)中的方程為：

其中，(x0,y0)為圓心坐標(biāo)，(x,y)和(x0,y0)均為六角網(wǎng)格系統(tǒng)中的坐標(biāo)，R為圓的半徑。

圓與矩形窗口的位置關(guān)系，有包含、相離、相交三種。對(duì)于包含和相離的情況，裁剪操作很容易處理。對(duì)于相交的情況，必須求出交點(diǎn)坐標(biāo)，并且把交點(diǎn)分為入點(diǎn)和出點(diǎn)兩類：入點(diǎn)即圓在該點(diǎn)處進(jìn)入矩形窗口,出點(diǎn)即圓在該點(diǎn)處離開矩形窗口。由于圓是封閉曲線，因此如果圓在某一個(gè)點(diǎn)處進(jìn)入矩形窗口，那么在它再次進(jìn)入矩形窗口之前，中間必須有一個(gè)第三點(diǎn)使得圓先離開矩形窗口，即：在矩形窗口的邊界上，不會(huì)有相鄰的兩個(gè)入點(diǎn)；同理，在矩形窗口的邊界上，也不會(huì)有相鄰的兩個(gè)出點(diǎn)。

2.1 算法描述

在基于類直角坐標(biāo)系的六角網(wǎng)格系統(tǒng)上使用矩形窗口裁剪圓曲線的流程是：先判斷圓與矩形窗口是否包含或者相離，如果是，則裁剪算法結(jié)束；否則，求出圓與矩形窗口邊界的交點(diǎn)，并進(jìn)行裁剪操作。

2.1.1 整個(gè)圓在矩形窗口內(nèi)部(包含關(guān)系)

如果x坐標(biāo)的最大值、最小值和y坐標(biāo)的最大值、最小值滿足：

則整個(gè)圓在矩形窗口內(nèi)部，如圖7所示，這種情況下不需要裁剪，整個(gè)圓在矩形窗口中都得到顯示。

2.1.2 整個(gè)圓在矩形窗口外部（相離關(guān)系）

如果x坐標(biāo)的最大值、最小值和y坐標(biāo)的最大值、最小值滿足：則整個(gè)圓在矩形窗口外部，如圖8所示，這種情況下不需要裁剪，整個(gè)圓在矩形窗口中都沒有顯示。

2.1.3 圓部分在矩形窗口內(nèi)部,部分在矩形窗口外部（相交關(guān)系）

圓與矩形窗口相交是裁剪算法中最復(fù)雜的部分，這種情況下需要求出圓與矩形窗口的交點(diǎn)，并將窗口外的部分裁剪掉，顯示窗口內(nèi)的部分。

將矩形邊界 方程 x=xl、x=xr、y=yb和 y=yt與 圓 的 方程聯(lián)立，求出所有交點(diǎn)坐標(biāo)，寫入交點(diǎn)集合I。如果某個(gè)邊界與圓相切，只有一個(gè)交點(diǎn)，則該點(diǎn)不寫入交點(diǎn)集合。

(1)矩形窗口與圓有 8個(gè)交點(diǎn)，如圖 9所示，記最下方交點(diǎn)中靠左的交點(diǎn)為I1，然后按照逆時(shí)針順序依次記其他交點(diǎn)為 I2,I3,…,I8。

判斷I1是出點(diǎn)還是入點(diǎn)，方法是：如果I1在矩形窗口的下邊界上，則將I1=(x,yb)的橫坐標(biāo)增加1并代入圓的方程，可求出相應(yīng)的縱坐標(biāo)y′有兩個(gè)，取圓弧上I1沿逆時(shí)針方向的下一個(gè)點(diǎn) I1′=(x+1,y′)，如果 y′>yb，則 I1為入點(diǎn)，否則 I1為出點(diǎn)；如果I1在矩形窗口的右邊界上，則將I1=(xr,y)的縱坐標(biāo)增加1并代入圓的方程，求出圓弧上I1沿逆時(shí)針方向的下一個(gè)點(diǎn) I1′=(x′,y+1)，如果 x′xl，則 I1為入點(diǎn)，否則 I1為出點(diǎn)。

如果 I1為出點(diǎn) ， 則圓弧 I2I3、I4I5、I6I7、I8I1位于窗口內(nèi)部，將其余部分裁剪掉；如果I1為入點(diǎn)，則圓弧 I1I2、I3I4、I5I6、I7I8位于窗口內(nèi)部， 將其余部分裁剪掉。

(2)矩形窗口與圓的交點(diǎn)少于8個(gè)，如圖10所示，仍然記最下方靠左的交點(diǎn)為I1，如果不存在這樣的I1，則按照逆時(shí)針順序，將遇到的第一個(gè)交點(diǎn)記為I1，其余交點(diǎn)順次標(biāo)記。然后按照(1)中的步驟進(jìn)行裁剪操作。

2.2 算法模擬實(shí)現(xiàn)

對(duì)本文提出的算法進(jìn)行模擬,結(jié)果如圖11～圖14所示。

2.3 算法分析

由于六角網(wǎng)格系統(tǒng)的特殊性，一些在方形網(wǎng)格系統(tǒng)中比較簡單的公式在六角網(wǎng)格系統(tǒng)下就變得比較復(fù)雜，本文給出的基于類直角坐標(biāo)系的六角網(wǎng)格系統(tǒng)的相關(guān)算法對(duì)該問題做了簡化，具有以下優(yōu)點(diǎn)：

(1)矩形窗口的左右邊界也是一條簡單的垂直線，可以用常數(shù)表達(dá)式來表示，這樣就可以大大降低算法的計(jì)算量;

(2)算法處理速度快。本算法分三種情況來討論圓與矩形窗口的關(guān)系，前期先判斷圓與矩形窗口是否為包含或者相離的關(guān)系，通過簡單的比較運(yùn)算來替代復(fù)雜的求交運(yùn)算，減少了計(jì)算量;

(3)簡化了入點(diǎn)和出點(diǎn)的判斷。本算法利用封閉圖形的入點(diǎn)和出點(diǎn)在矩形窗口邊界上交互出現(xiàn)，只需判斷一個(gè)起始點(diǎn)為入點(diǎn)或出點(diǎn)，然后按照逆時(shí)針順序，根據(jù)入點(diǎn)和出點(diǎn)交互分布的原則依次判斷其他點(diǎn)是入點(diǎn)或出點(diǎn)。

在基于類直角坐標(biāo)系的六角網(wǎng)格系統(tǒng)上，矩形窗口的邊界可以用常數(shù)表達(dá)式來表示，這大大簡化了六角網(wǎng)格系統(tǒng)上圖形裁剪算法的研究。由于這類六角網(wǎng)格系統(tǒng)上矩形窗口邊界表達(dá)式與方形網(wǎng)格系統(tǒng)上矩形窗口表達(dá)式形式一致，可以將方形網(wǎng)格系統(tǒng)上的其他圖形圖像處理算法直接或間接地移植到該類六角網(wǎng)格系統(tǒng)上。此外，本文給出的算法具有一定通用性，只需將圖形方程進(jìn)行變化，即可適用于其他圖形圖像的矩形窗口裁剪。

[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]劉勇奎,鄒善舉.六角網(wǎng)格上的圖像算法及幾何量定義[J].計(jì)算機(jī)工程與設(shè)計(jì),2000,21(1):61-64.

[5]趙慧杰,晏俊德,劉勇奎,等.六角網(wǎng)格單色顯示器及圖形算法研究[J].沈陽工業(yè)大學(xué)學(xué)報(bào),1997,19(5):66-71.

[6]韓麗.基于六角網(wǎng)格的矩形窗口的圓裁剪算法[J].錦州師范學(xué)院學(xué)報(bào)(自然科學(xué)版),2003,24(4):64-66.

[7]孫長嵩,李麗潔,宋陽.一個(gè)基于六角網(wǎng)格的圓形窗口的裁剪算法[J].交通科技與經(jīng)濟(jì)，2006,33(1):78-80.

[8]付文超,羅小華,張文爭,等.改進(jìn)的六角網(wǎng)格下橢圓繪制算法[J].暨南大學(xué)學(xué)報(bào)(自然科學(xué)與醫(yī)學(xué)版).已錄用，待刊登.