改進的六角網(wǎng)格系統(tǒng)上矩形窗口裁剪算法*

付文超,張傳林

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

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

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

總體來說，六角網(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)提出了一種改進的矩形窗口圖形裁剪算法，算法的復(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)上的任何一個點的坐標(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)上的任何一個點的坐標(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)上麻煩,這是因為在傳統(tǒng)60°角六角網(wǎng)格系統(tǒng)上窗口的垂直邊界需要用一條斜線來表示，而不是用常數(shù)表達(dá)式來表示。

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

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

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

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

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

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

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

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

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

2.1 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 算法模擬實現(xià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)算法對該問題做了簡化，具有以下優(yōu)點：

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

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

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

在基于類直角坐標(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)上。此外，本文給出的算法具有一定通用性，只需將圖形方程進行變化，即可適用于其他圖形圖像的矩形窗口裁剪。

[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].計算機工程與設(shè)計,2000,21(1):61-64.

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

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

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

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