Weiler-Atherton多边形裁剪

当修剪的多边形具有两个或多个单独的部分时, 则为该算法处理的凹多边形。修改了窗口边界的顶点处理过程, 以便显示凹面多边形。

最初将裁剪窗口称为“裁剪多边形”, 然后将其裁剪为主题多边形。我们从主题多边形的任意顶点开始, 并沿其边界沿顺时针方向跟踪, 直到遇到与剪贴多边形相交的地方：

1.如果边缘进入剪辑多边形, 则记录相交点并继续跟踪主题多边形。

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

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

例如, 图（a）中的数字表示跟踪边缘和边缘部分的顺序。我们从起始顶点开始, 并沿着主题多边形进入剪贴多边形的同一边（从1到2）继续。当我们沿着离开剪辑多边形的边缘移动时, 我们在剪辑多边形上右转（从4到5）, 现在将其视为主题多边形。遵循相同的逻辑将导致下一个右转弯（从5到6）进入当前的剪辑多边形, 这是原始主题多边形。以同样的方式完成下一步（从7到8）后, 我们在图（b）中有了一个输出的子多边形。然后, 我们从记录的相交点（最初改变航向）开始对原始主题多边形的遍历。从9到10到11不会产生任何输出。跳过已经遍历的6和7之后, 我们继续进行12和13并结束。无花果（b）是最终结果。