多邊形裁剪算法實現(xiàn)與改進(jìn)

王海濤++衛(wèi)文學(xué)

摘要：計算機圖形學(xué)是研究基于物理定律、經(jīng)驗方法以及認(rèn)知原理，使用各種數(shù)學(xué)算法處理二維或三維圖形數(shù)據(jù)，生成可視數(shù)據(jù)表現(xiàn)的科學(xué)，它是計算機科學(xué)的一個分支領(lǐng)域與應(yīng)用方向。往往在使用計算機處理圖像時，占用計算機內(nèi)部存儲空間往往比較大。為了提高效率，計算機往往采用裁剪的方式將圖片所需的部分顯示，這其中多邊形裁剪是重要的一種算法，該文將簡述多邊形裁剪算法的實現(xiàn)與改進(jìn)。

關(guān)鍵詞：計算機圖形學(xué)；多邊形裁剪；算法；改進(jìn)

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）20-0185-02

Abstract： Computer graphics is a kind of scientific research based on physical laws， empirical methods and cognitive principles， using various mathematical algorithms to deal with two-dimensional or three-dimensional graphics data， to generate visual data representation of the science. It is a branch of computer science and its application. Often in the use of computer image processing， the occupation of computer storage space is often relatively large. In order to improve the efficiency， the computer is often used to cut out the part of the image， which is an important part of the algorithm， the paper will summarize the implementation and improvement of polygon clipping algorithm.

Keywords： computer graphics； Polygon clipping； algorithm； improvement

1引言

隨著計算機的廣泛應(yīng)用以及計算機技術(shù)不斷地發(fā)展，作為計算機領(lǐng)域重要分支的可視化技術(shù)近年來也得到了長足的發(fā)展。在國外，可視化技術(shù)已經(jīng)較為成熟可以應(yīng)用于多個領(lǐng)域，比如教學(xué)領(lǐng)域，商業(yè)領(lǐng)域等。在國內(nèi)，可視化技術(shù)的研究還不太成熟，但是可視化技術(shù)已經(jīng)得到了長遠(yuǎn)的發(fā)展?？梢暬夹g(shù)在現(xiàn)階段擁有較為廣闊的發(fā)展空間。可視化技術(shù)主要分成兩類：二維平面圖像和三維立體圖像。該文在研究可視化技術(shù)的基礎(chǔ)上，對二維圖像裁剪算法進(jìn)行討論和優(yōu)化，生成相應(yīng)的結(jié)果。

要指出最新研究對這個問題存在的不足，以及改進(jìn)的思路。

2多邊形裁剪算法描述

使用計算機處理圖形時，往往占用較大的存儲空間，而當(dāng)真正使用或顯示的一般是圖形的一部分。所以我們就需要將使用到的部分圖形顯示出來，將其他部分排除在外，這樣不僅大大節(jié)省了內(nèi)存開支并且提高了使用和顯示效率。這樣的選擇過程稱為裁剪。最直接的裁剪方式是把圖形進(jìn)行掃描后轉(zhuǎn)化為點的集合，最后在判斷各點是否在所需部分之內(nèi)。但那樣太費時。所以一般采用的方法是先進(jìn)行裁剪再進(jìn)行掃描和轉(zhuǎn)化。

裁剪的算法主要包括線段裁剪算法，多邊形裁剪算法，字符裁剪算法等。[1]該文主要圍繞多邊形裁剪算法進(jìn)行研究。

多邊形可以比作是線段的集合，多邊形的裁剪可以相應(yīng)的轉(zhuǎn)化成每條線段的裁剪。當(dāng)一個封閉的多邊形作為線段的集合進(jìn)行裁剪時，原來封閉的主多邊形轉(zhuǎn)化成一條條由裁剪后的線段及裁剪多邊形的部分邊界線段構(gòu)成的邊的集合。[2]多邊形裁剪算法主要包括Sutherland -Hodgman算法和Weiler-Atherton算法等，其中S-H算法核心思想是通過對多邊形某一邊的裁剪，來完成對整體的裁剪，簡而言之就是每次將主多邊形的邊與裁剪完的邊進(jìn)行對比，然后輸出一個或兩個頂點或不輸出。這一算法適用于對凸、凹任意主多邊形進(jìn)行裁剪，裁剪多邊形為凸多邊形。算法輸出的結(jié)果是一個多邊形的頂點序列，所有頂點均位于裁剪多邊形的可見側(cè)。由于主多邊形的每一條邊與裁剪多邊形的每一條邊分別進(jìn)行比較，因此需要考慮每條邊與每個裁剪邊的相對位置關(guān)系。此算法還要考慮如何判別交點位于裁剪邊的哪一側(cè)以及如何求裁剪邊與主多邊形線段的交點。W-A算法首先是將主多變形與裁剪多邊形比較，標(biāo)記下二者的交點，然后處理不相交的多邊形邊界，通過建表分別記錄位于裁剪多邊形內(nèi)部和外部的邊界。同理建表分別記錄主多邊形進(jìn)入裁剪多邊形內(nèi)部的交點和離開內(nèi)部的交點。最后再從進(jìn)點表中依次取出一個交點，若該交點為空則結(jié)束。比較多邊形頂點表直到發(fā)現(xiàn)一個交點，將這一段主多邊形頂點表復(fù)制到內(nèi)表中。再根據(jù)交點位置，找到裁剪多邊形頂點表相應(yīng)位置，跟蹤裁剪多頂點表， 直到下一個交點為止，將這一段裁剪多邊形頂點表復(fù)制到內(nèi)表中， 再從頭開始直到結(jié)束，則獲得裁剪后的新多邊形。[3]

3 S-H算法應(yīng)用

下面用一個示例演示一下S-H算法的實現(xiàn)。設(shè)多邊形由如下頂點D1，D2，D3，D4，D5構(gòu)成，主多邊形與裁剪多邊形如圖1所示。

用程序?qū)崿F(xiàn)算法，主要程序段描述：

裁剪后的多邊形如圖2所示。

4 實現(xiàn)對S-H算法的改進(jìn)

S-H算法是一種較為方便實用的方法，但該算法也存在一些缺點和不足，比如對多邊形進(jìn)行裁剪后，會出現(xiàn)一些不屬于裁剪多邊形的邊。一種方法是將主多邊形分成更多的凸多邊形，然后依次處理各個凸多邊形，然而這樣會使得效率降低。另一種方法是在Sutherland-Hodgman算法基礎(chǔ)上進(jìn)行優(yōu)化，查找頂點表，然后將表中的頂點各個連接起來也比較麻煩。基于上述問題，本文提出了一種算法。此算法的思想為：用最直接的直線段的裁剪算法即依次對多邊形的每條邊進(jìn)行裁剪。然后處理主多邊形與裁剪多邊形的交點，如果該點是裁剪后可見部分的起始點，記為入點，如果該點是可見部分的終止點，記為出點。然后對主多邊形的個邊順序逐個裁剪，得到非封閉多邊形。顯然得到的交點中入點與出點的個數(shù)應(yīng)該相等，且入點與出點沿多邊形方向相同的排列，要使裁剪后的多邊形封閉，只需要把所有出點與入點進(jìn)行連接。入點與出點的位置與該多邊形邊界的關(guān)系主要有如下幾種：

以圖7為例將該算法與常規(guī)算法進(jìn)行比較。

從表1中可以看出，本文介紹的算法，具有思想簡單，易于編程的特點，減少了交點判斷次數(shù)和存儲量，整個算法速度快、效率高。

5 總結(jié)

計算機圖形學(xué)所包含的算法有很多，本文所研究的裁剪算法是計算機圖形學(xué)中比較基礎(chǔ)的算法，是其他諸多重要問題的基礎(chǔ)。該文簡單闡述了國內(nèi)外計算機圖形學(xué)的發(fā)展情況，接著對基本的裁剪算法Sutherland-Hodgman算法和Weiler-Atherton算法進(jìn)行了簡單的介紹，并且通過一個例子描述了Sutherland-Hodgman算法的具體應(yīng)用，又分析了一下S-H算法的不足?；谏鲜鰡栴}在S-H算法的基礎(chǔ)上加以優(yōu)化和改進(jìn)，提出了一種更為方便快捷的算法。減少了交點判斷的次數(shù)和存儲量，在應(yīng)用中效率更高。

參考文獻(xiàn)：

[1] 孫家廣，胡事民.計算機圖形學(xué)基礎(chǔ)教程[M]. 2版.北京：清華大學(xué)出版社，2009.

[2] 常明，朱林.計算機圖形學(xué)[M]. 2版.華中科技大學(xué)出版社，2001.

[3] 付迎春，袁修孝.一種有效的任意多邊形裁剪算法[J] .計算機工程，2006（7）.

[4] 譚浩強.C程序設(shè)計[M]. 2版.北京：清華大學(xué)出版社，1999.

[5] 夏德麟，汪應(yīng)風(fēng).多邊形裁剪的一種新的方法[J].計算機應(yīng)用軟件，1991（1）：60-64.