多邊形裁剪算法實現與改進

王海濤++衛文學

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

關鍵詞：計算機圖形學；多邊形裁剪；算法；改進

中圖分類號：TP301 文獻標識碼：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引言

隨著計算機的廣泛應用以及計算機技術不斷地發展，作為計算機領域重要分支的可視化技術近年來也得到了長足的發展。在國外，可視化技術已經較為成熟可以應用于多個領域，比如教學領域，商業領域等。在國內，可視化技術的研究還不太成熟，但是可視化技術已經得到了長遠的發展。可視化技術在現階段擁有較為廣闊的發展空間。可視化技術主要分成兩類：二維平面圖像和三維立體圖像。該文在研究可視化技術的基礎上，對二維圖像裁剪算法進行討論和優化，生成相應的結果。

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

2多邊形裁剪算法描述

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

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

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

3 S-H算法應用

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

用程序實現算法，主要程序段描述：

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

4 實現對S-H算法的改進

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

以圖7為例將該算法與常規算法進行比較。

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

5 總結

計算機圖形學所包含的算法有很多，本文所研究的裁剪算法是計算機圖形學中比較基礎的算法，是其他諸多重要問題的基礎。該文簡單闡述了國內外計算機圖形學的發展情況，接著對基本的裁剪算法Sutherland-Hodgman算法和Weiler-Atherton算法進行了簡單的介紹，并且通過一個例子描述了Sutherland-Hodgman算法的具體應用，又分析了一下S-H算法的不足。基于上述問題在S-H算法的基礎上加以優化和改進，提出了一種更為方便快捷的算法。減少了交點判斷的次數和存儲量，在應用中效率更高。

參考文獻：

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

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

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

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

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