多边形裁剪算法

多边形裁剪算法

刚参加工作就跟多边形刚上了,对于多边形的裁剪做一些简单的总结。 多边形裁剪主要有四种算法

  1. Greiner-Hormann裁剪算法
  2. Sutherland-Hodgman算法
  3. Vatti裁剪算法
  4. 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年提出的。这种算法采用了分割处理、逐边裁剪的方法。 https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQud2lraW1lZGlhLm9yZy93aWtpcGVkaWEvY29tbW9ucy81LzUzL1N1dGhlcmxhbmQtSG9kZ21hbl9jbGlwcGluZ19zYW1wbGUuc3Zn?x-oss-process=image/format,png 它的基本思想是什么呢,首先我们将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/