Weiler-Atherton多边形裁剪

当裁剪后的多边形有两个或多个独立部分时，该算法可以处理凹多边形。窗口边界的顶点处理过程经过修改，可以显示凹多边形。

假设裁剪窗口最初被称为裁剪多边形，要裁剪的多边形称为主题多边形。我们从主题多边形的任意顶点开始，沿顺时针方向沿着其边界追踪，直到遇到与裁剪多边形的交点。

1. 如果边进入裁剪多边形，则记录交点并继续追踪主题多边形。

2. 如果边离开裁剪多边形，则记录交点，然后右转，以相同的方式沿着裁剪多边形（即，将裁剪多边形视为主题多边形，并将主题多边形视为裁剪多边形，然后像以前一样进行）。

每当我们的遍历路径形成一个子多边形时，我们就将该子多边形作为整体结果的一部分输出。然后，我们继续从记录的交点追踪原始主题多边形的其余部分，该交点标记着尚未追踪的边或边的某个部分的开始。当原始主题多边形的整个边界都被精确地追踪一次时，算法终止。

例如，图 (a) 中的数字表示追踪边和边的部分时的顺序。我们从起始顶点开始，沿着主题多边形的同一条边（从 1 到 2）继续，因为它进入裁剪多边形。当我们沿着离开裁剪多边形的边移动时，我们向右转（从 4 到 5）到裁剪多边形上，现在将其视为主题多边形。遵循相同的逻辑导致下一个右转（从 5 到 6）到当前的裁剪多边形，即原始主题多边形。完成下一步（从 7 到 8）后，我们得到了图 (b) 中要输出的子多边形。然后，我们从记录的交点恢复对原始主题多边形的遍历，在那里我们第一次改变了我们的路线。从 9 到 10 到 11 不产生输出。跳过已经遍历的 6 和 7 之后，我们继续进行 12 和 13，然后结束。图 (b) 是最终结果。