完整版)Weiler-Atherton任意多邊形裁剪算法

1、Weiler Atherton 任意多邊形裁剪Sutherland Hodgeman 算法解決了裁剪窗口為凸多邊形窗口的問題， 但一些應(yīng)用需要涉及 任意多邊形窗口（含凹多邊形窗口）的裁剪。 Weiler-Atherton 多邊形裁剪算法正是滿足這種要 求的算法。一、 Weiler Atherton 任意多邊形裁剪算法描述：在算法中，裁剪窗口、被裁剪多邊形可以是任意多邊形：凸的、凹的（內(nèi)角大于180 o）、甚至是帶有內(nèi)環(huán)的（子區(qū)），見下圖裁剪窗口和被裁剪多邊形處于完全對(duì)等的地位，這里我們稱：1 、被裁剪多邊形為主多邊形，記為A；2 、裁剪窗口為裁剪多邊形，記為 B主多邊形 A 和裁剪多邊形 B

2、的邊界將整個(gè)二維平面分成了四個(gè)區(qū)域：1 、 AB（交：屬于 A 且屬于 B）；2 、 A B （差：屬于 A 不屬于 B ）；3 、 B A （差：屬于 B 不屬于 A ）；4 、 AB（并：屬于 A 或?qū)儆?B，取反；即：不屬于 A 且 不屬于 B ）。內(nèi)裁剪 即通常意義上的裁剪，取圖元位于窗口之內(nèi)的部 分，結(jié)果為 A B。外裁剪 取圖元位于窗口之外的部分，結(jié)果為A B。觀察右圖不難發(fā)現(xiàn)裁剪結(jié)果區(qū)域的邊界由被裁剪多邊形的 部分邊界和裁剪窗口的部分邊界兩部分構(gòu)成，并且 在交點(diǎn)處邊 界發(fā)生交替 ，即由被裁剪多邊形的邊界轉(zhuǎn)至裁剪窗口的邊界， 或者反之。由于多邊形構(gòu)成一個(gè)封閉的區(qū)域，所以，如果被裁

3、剪多邊形和裁剪窗口有交點(diǎn)，則 交點(diǎn)成對(duì)出現(xiàn) 。這些交點(diǎn)分成兩類：一類稱 “入 ”點(diǎn)，即被裁剪多邊形由此點(diǎn)進(jìn)入裁剪窗口，如圖中a、 c、 e；一類稱 “出”點(diǎn)，即被裁剪多邊形由此點(diǎn)離開裁剪窗口，如圖中b 、d、f。Weiler Atherton 任意多邊形裁剪算法思想：假設(shè)被裁剪多邊形和裁剪窗口的頂點(diǎn)序列都按順時(shí)針方向排列。 當(dāng)兩個(gè)多邊形相交時(shí)， 交點(diǎn) 必然成對(duì)出現(xiàn)，其中一個(gè)是從被裁剪多邊形進(jìn)入裁剪窗口的交點(diǎn)，稱為“入點(diǎn) ”，另一個(gè)是從被裁剪多邊形離開裁剪窗口的交點(diǎn)，稱為“出點(diǎn) ”。算法從被裁剪多邊形的一個(gè)入點(diǎn)開始， 碰到入點(diǎn)， 沿著被裁剪多邊形按順時(shí)針方向搜集頂點(diǎn) 序列；而當(dāng)遇到出點(diǎn)時(shí)，則沿著

4、裁剪窗口按順時(shí)針方向搜集頂點(diǎn)序列。按上述規(guī)則，如此交替地沿著兩個(gè)多邊形的邊線行進(jìn)， 直到回到起始點(diǎn)。 這時(shí)， 收集到的全 部頂點(diǎn)序列就是裁剪所得的一個(gè)多邊形。由于可能存在分裂的多邊形， 因此算法要考慮： 將搜集過的入點(diǎn)的入點(diǎn)記號(hào)刪去， 以免重復(fù) 跟蹤。將所有的入點(diǎn)搜集完畢后算法結(jié)束。三、Weiler Atherton 任意多邊形裁剪算法步驟：1、順時(shí)針輸入被裁剪多邊形頂點(diǎn)序列放入數(shù)組1 中2 、順時(shí)針輸入裁剪窗口頂點(diǎn)序列放入數(shù)組2 中。入”、“出”標(biāo)記3 、求出被裁剪多邊形和裁剪窗口相交的所有交點(diǎn)，并給每個(gè)交點(diǎn)打上然后將交點(diǎn)按順序插入序列得到新的頂點(diǎn)序列，并放入數(shù)組3 中；同樣也將交點(diǎn)按順序插

5、入序列得到新的頂點(diǎn)序列，放入數(shù)組4 中；4、初始化輸出數(shù)組 Q，令數(shù)組 Q為空。接著從數(shù)組 3中尋找 “入”點(diǎn)。如果 “入”點(diǎn)沒找到，程序結(jié)束。5、如果找到 “入”點(diǎn)，則將 “入”點(diǎn)放入 S 中暫存。6 、將“入”點(diǎn)錄入到輸出數(shù)組 Q中。并從數(shù)組 3中將該 “入”點(diǎn)的“入”點(diǎn)標(biāo)記刪去7 、沿?cái)?shù)組 3 順序取頂點(diǎn)：如果頂點(diǎn)不是 “出點(diǎn)”，則將頂點(diǎn)錄入到輸出數(shù)組 Q中，流程轉(zhuǎn)第 7 步 否則，流程轉(zhuǎn)第 8 步。8 、沿?cái)?shù)組 4 順序取頂點(diǎn)：如果頂點(diǎn)不是 “入點(diǎn)”，則將頂點(diǎn)錄入到輸出數(shù)組 Q中，流程轉(zhuǎn)第 8 步 否則，流程轉(zhuǎn)第 9 步。9、如果頂點(diǎn)不等于起始點(diǎn) S，流程轉(zhuǎn)第 6 步，繼續(xù)跟蹤數(shù)組 3

6、。否則，將數(shù)組 Q 輸出；流程轉(zhuǎn)第 4 步，尋找可能存在的分裂多邊形。算法在第 4 步：滿足 “入 ”點(diǎn)沒找到的條件時(shí)，算法結(jié)束。算法的生成過程見下圖所示。四、Weiler Atherton 任意多邊形裁剪算法實(shí)現(xiàn)：1、算法在實(shí)現(xiàn)中，需要用到六個(gè)數(shù)組，分別用來存放：被裁剪多邊形、裁剪窗口、交點(diǎn)數(shù) 組、插入交點(diǎn)后的被裁剪多邊形、插入交點(diǎn)后的裁剪窗口、輸出多邊形。2 、由于交點(diǎn)具有 “入”、“出”標(biāo)記，因此凡與交點(diǎn)有關(guān)的數(shù)組都要采用結(jié)構(gòu)數(shù)組類型：struct pointdouble x ；double y ；int flag ； 交點(diǎn)數(shù)組，數(shù)組 3 ，數(shù)組 4 ；標(biāo)記 flag 有三種狀態(tài)：0：非

7、交點(diǎn)；1：“入”點(diǎn)；-1：“出”點(diǎn)。3 、求交點(diǎn)時(shí)，利用被裁剪多邊形的各邊去對(duì)裁剪窗口的各邊求交點(diǎn)：for （被裁剪多邊形的各邊）；for （裁剪窗口的各邊）求有效交點(diǎn)；放入交點(diǎn)數(shù)組；4 、交點(diǎn)的 順序插入 ，意味著要對(duì)交點(diǎn)數(shù)組排序后再分別插入到數(shù)組1、數(shù)組 2 的相應(yīng)位置上。5、所謂找“入”點(diǎn)、“出”點(diǎn)，必須根據(jù) flag 找尋滿足條件的頂點(diǎn)位置。 不光數(shù)組 3中要找 “入 點(diǎn)、 “出 ”點(diǎn)，而且找到后還要轉(zhuǎn)到數(shù)組 4 的相應(yīng)頂點(diǎn)位置處。對(duì)數(shù)組 4 的處理也同上。這種處理 在本算法中大量遇到。五、Weiler Atherton 任意多邊形裁剪算法演示： （略）六、Weiler Atherto

8、n 任意多邊形裁剪算法特點(diǎn)：1、裁剪窗口可以是矩形、任意凸多邊形、任意凹多邊形。2 、可實(shí)現(xiàn)被裁剪多邊形相對(duì)裁剪窗口的內(nèi)裁或外裁，即保留窗口內(nèi)的圖形或保留窗口外的 圖形，因此在三維消隱中可以用來處理物體表面間的相互遮擋關(guān)系。3、裁剪思想新穎，方法簡(jiǎn)潔，裁剪一次完成，與裁剪窗口的邊數(shù)無關(guān)。七、Weiler Atherton 任意多邊形裁剪算法小結(jié)：前面介紹的是內(nèi)裁算法，即保留裁剪窗口內(nèi)的圖形。而外裁算法（保留裁剪窗口外的圖形） 同內(nèi)裁算法差不多。外裁算法與內(nèi)裁算法不同的是：1、從被裁剪多邊形的一個(gè) “出點(diǎn) ”開始，碰到出點(diǎn)，沿著被裁剪多邊形按順時(shí)針方向搜集頂 點(diǎn)序列；2、而當(dāng)遇到 “入點(diǎn) ”時(shí)，則沿著裁剪窗口按逆時(shí)針方向搜集頂點(diǎn)序列。按上述規(guī)則，如此交替地沿著兩個(gè)多邊形的邊線行進(jìn)， 直到回到起始點(diǎn)為止。這時(shí)，收集到 的全部頂點(diǎn)序列就是裁剪所得的一個(gè)多邊形。由于可能存在分裂的多邊形，因此算法要考慮：將搜集過的 “出點(diǎn) ”的出點(diǎn)記號(hào)刪去，以免重 復(fù)跟蹤。將所有的出點(diǎn)搜集完畢后算法結(jié)束。Weiler Atherton 算法的的設(shè)計(jì)思想很巧妙，裁剪是一次完成，不象 Sutherland-Hodgman 多邊形裁剪算法