本發明公開了一種解決交點退化問題的復雜多邊形裁剪方法，首先，對實體多邊形的外環邊界構成的多邊形與裁剪多邊形進行求交；然后，若實體多邊形含有孔洞，則對結果多邊形與孔洞構成的多邊形進行求差；得到的裁剪結果再與下一個孔洞多邊形進行求差，直至所有孔洞多邊形處理完畢，整個裁剪過程結束，最終得到一般多邊形的裁剪結果。本發明適用于任意凸的、凹的或帶孔洞的多邊形裁剪，可實現實體多邊形與裁剪多邊形的求交、求差以及求并，在交點退化情況下也能夠得到正確的裁剪結果；減少了多邊形的求交次數和生成裁剪結果時頂點遍歷次數，加快了裁剪算法運行速度；在空間消耗和時間消耗上的性能要優于Greiner?Hormann算法。

技術領域

本發明涉及計算機圖形學以及地理信息系統(GIS)技術，特別是涉及一種解決交點退化問題的復雜多邊形裁剪方法。

背景技術

多邊形裁剪算法被廣泛應用于地理信息系統（GIS）、計算機圖形學、機器人運動學等領域，是計算機圖形學許多重要問題的基礎，其主要目的是裁剪掉被裁減多邊形（又稱實體多邊形）位于裁剪多邊形之外的部分。

目前，對于多邊形裁剪國外已有很多經典算法，例如Sutherland-Hodgeman算法、Liang-Barsky算法、Maillot算法等算法，可是以上算法要求裁剪多邊形是矩形，被裁剪多邊形（也稱實體多邊形）是凸多邊形。而在實際應用中，實體多邊形為一般多邊形時裁剪算法才具有普遍意義和實際應用價值。在這類算法中Weiler-Atherton算法（簡稱W-A算法）和Greiner-Hormann算法（簡稱G-H算法）是公認的比較具有代表性、成熟的任意多邊形裁剪算法。其中，W-A算法使用的是樹形結構，而G-H算法使用的是雙向線性鏈表結構，所以后者在復雜性和運行速度方面都優于前者。國內學者大多數從優化數據結構、減少交點判斷和交點求取的計算量等方面展開研究，進一步提高了裁剪算法效率。但是上述算法都沒有具體描述在重合邊和兩多邊形在頂點處相切（又稱交點退化）這兩種特殊情況下多邊形裁剪的解決方案。王慧青等采用交點關聯線段間的交點進出性判別方法，用于處理重點和重邊問題，但是該算法將交點插入到實體多邊形和裁剪多邊形的頂點鏈表，在生成裁剪結果多邊形時，需要在實體多邊形和裁剪多邊形的兩個頂點鏈表之間來回切換遍歷，其工作量很大。因此，需要研究一種新的解決交點退化問題的復雜多邊形裁剪方法。

發明內容

為了解決上述存在的問題，本發明提供一種解決交點退化問題的復雜多邊形裁剪方法，在頂點處相切這兩種交點退化情況下也能夠得到正確裁剪結果的復雜多邊形裁剪方法，為達此目的，本發明提供一種解決交點退化問題的復雜多邊形裁剪方法，所述步驟包括：

（1）假設被裁剪多邊形即實體多邊形為S，裁剪多邊形為C，將含孔洞的復雜實體多邊形分解成多個由外環和N個內環構成的不含孔洞的簡單多邊形，其中N≧0；

（2）對實體多邊形的外環邊界構成的多邊形與裁剪多邊形進行求交即S∩C操作，得到裁剪結果；

（3）若S不含孔洞，則直接輸出這個裁剪結果；否則，繼續步驟4；

（4）將結果多邊形視為裁剪多邊形，某一孔洞構成的多邊形視為實體多邊形，對結果多邊形與孔洞構成的多邊形進行求差即C－S操作，得到裁剪結果；

（5）取下一個孔洞構成的多邊形，繼續步驟4，直至所有孔洞構成的多邊形處理完畢，輸出最終的裁剪結果。

進一步的，所述步驟（2）中對實體多邊形的外環邊界構成的多邊形與裁剪多邊形進行求交操作步驟為：

（21）設計了一個合理的數據結構，用于存儲入點、出點以及裁剪多邊形頂點；

（22）將實體多邊形S和裁剪多邊形C的頂點按順時針方向分別以單向線性鏈表形式存儲；

（23）判斷實體多邊形和裁剪多邊形的最小外包矩形框MBR是否相交：若不相交，則輸出裁剪結果多邊形為空；若相交，繼續步驟（24）；