Weiler-Atherton剪裁算法

計算規則

無論是被裁剪的多邊形，還是裁剪區域多邊形，都用邊界的有向頂點序列表示，並約定外環（由多邊形的外部邊界構成）取順時針方向，內環（由多邊形的內部邊界構成）取逆時針方向。

該算法的基本思想是：沿作被裁剪多邊形的邊的方向來處理頂點，並採用如下規則：

1) 對於由外到內穿入裁剪區域的頂點對V1V2，從線段V1V2與裁剪邊界的交點V1′開始，繼續沿作多邊形的方向V1′V2前進。這種"由外到內"的交點稱為"入點"。

2) 對於由內到外穿出裁剪區域的頂點對V3V4，從線段V3V4與裁剪邊界的交點V3′開始，按順時針沿作裁剪邊界的方向前進。這種"由內到外"的交點稱為"出點"。在轉向裁剪邊界的方向前進之前，保存V3′V4作為恢復多邊形搜尋的入口。

3) "入點"和"出點"總是交替地成對出現，形成一個結果多邊形。

4) 轉到前一個"出點"的入口V3′V4，重複上述步驟1）到3）。如此繼續，直到最初的開始點V1為止。

1、裁剪視窗可以是矩形、任意凸多邊形、任意凹多邊形。

2、可實現被裁剪多邊形相對裁剪視窗的內裁或外裁，即保留視窗內的圖形或保留視窗外的圖形，因此在三維消隱中可以用來處理物體表面間的相互遮擋關係。

3、裁剪思想新穎，方法簡潔，裁剪一次完成，與裁剪視窗的邊數無關。