多边形裁剪算法
多边形裁剪算法
刚参加工作就跟多边形刚上了，对于多边形的裁剪做一些简单的总结。 多边形裁剪主要有四种算法
- Greiner-Hormann裁剪算法
- Sutherland-Hodgman算法
- Vatti裁剪算法
- Weiler-Atherton裁剪算法
作为一名想要成为优秀算法工程师的程序员，我们不能只会使用，而不知道其原理，倘若如此，我们无法做到应用于本身业务上的定制化的修改。
一.Greiner–Hormann算法
Greiner–Hormann算法的性能要比 Vatti裁剪算法的性能高，但无法处理退化问题，它可以处理自相交和非凸多边形。可以简单地推广计算多边形上的其他布尔运算，例如并集和差集。
我们看如图4的实例，我们的任务是使用用虚线围成的多边形C裁剪我们的虚点围成的多边形S。
我们首先确定S多边形边界的哪些部分位于C多边形内.如图5。
我们可以通过考虑以下类比情况：想象一下沿着S多边形边界推动粉笔车。我们从S多边形的某个顶点开始，如果该顶点位于C多边形内，则在开始处用粉笔画。然后，我们沿着s多边形推动推车，每当我们穿过c多边形的边缘时，就会切换是否用粉笔画（打开/关闭）。当我们到达起始顶点时停止。然后，s多边形中位于c多边形内的部分将用粉笔标记。 完美！
我们使用相同的技术，但这次沿着c多边形运行粉笔车，以发现c多边形中位于s多边形内的那些部分（图6）。
一旦我们找到了位于另一个多边形内的多边形边缘的所有部分，我们就合并这些部分以获得最后裁剪过的多边形（图7）。
merge过程很容易，考虑到将在结果中的s多边形的每个部分都由s多边形和c多边形的两个交点限定。这些顶点也是在c多边形的一个相关部分的开始或结束。因此，如果您跟踪交叉点和它们来自的部位，那么以正确的顺序连接支撑部位很容易。
二.Sutherland–Hodgman algorithm
Sutherland-Hodgman算法也叫逐边裁剪法，该算法是萨瑟兰德(I．E．Sutherland)和霍德曼(Hodgman)在1974年提出的。这种算法采用了分割处理、逐边裁剪的方法。
它的基本思想是什么呢，首先我们将c多边形的每一条边在两个方向上无限延伸，将整个空间一分为二。其中，空间中有一侧是我们要保留的可见侧，还有一侧是我们不需要的。
如果s多边形的顶点位于c多边形边上线的可见侧，则保留他们，生成新的多边形。 对每个c多边形边重复此过程，使用一个阶段的输出作为下一个阶段的输入。处理完c多边形的所有边后，最终生成的顶点列表将定义一个完全可见的多边形。请注意，如果s多边形在c多边形外的顶点处是凹形的，则新多边形可能有重合（即重叠）的边-这对于渲染是可以接受的，但对于其他应用程序（如计算阴影）则不是。
三.Vatti裁剪算法
与Sutherland-Hodgman和Weiler-Atherton多边形裁剪算法不同，Vatti算法不限制可用作s或c的多边形类型。甚至可以处理复杂（自相交）多边形和带孔的多边形。
目前来说，我使用的三方库Clipper就是使用的Vatti算法。所以这个方法非常的重要。 但是，文献要钱，网上找不到相关介绍，暂时算了，以后补上。
四.Weiler-Atherton
说实话，我本来就是要说剖析一下Clipper里用的布尔运算的算法，由于Vatti的原因，心情很沮丧，所以没心情了，放个链接把 https://blog.csdn.net/yangxi_pekin/article/details/37738219/