计算几何(一)——凸包(Convex Hull)

凸包问题是计算几何(Computational Geometry)的一个重点,同样,如何构造凸包也是一个重要的研究方向,生活中许多问题都会用到构造凸包的知识,比如颜料混合,即如何从已有的颜料中通过混合得到未知的颜料。在这篇文章中,我将介绍5种重要的凸包构造算法,分别是极点算法极边算法增量式策略Jarvis MarchGraham Scan等,同时也将通过归约得到凸包构造算法时间复杂度的下界。

极点算法(Extreme Points)

顾名思义,极点就是凸包边上的点,严格的说,如果一个点被称为极点,那么必然存在一条直线通过这一点,并且使得其他所有的点都落在这条直线的同一侧。那么极点与凸包又有什么关系呢,回顾我们之前的排序算法,我们知道如果一个序列是有序的,当且仅当它的每一个元素都是有序的。同样,如果一个多边形是凸的,当且仅当它的每一个顶点都是极性的。所以,现在的问题就变成了我们应该如何识别一个点是不是极点呢?

通过观察可以发现,所有的非极点必然都落在某一个潜在三角形中,我们可以通过列举每一个潜在三角形,并确认一个点是否在其内部,以此来判别这个点是不是极点,这种方法称为In-Triangle Test。它的伪代码如下:

至此,我们就得到了完整的极点算法的实现,如下:

很遗憾,这个算法里的四重For循环,使得其时间复杂度为O(n4),这是很不理想的。我们不妨先放下对其时间复杂度的讨论,转而观察一个细节的实现,就是In-Triangle Test的具体实现方法。如果一个点s在一个按照逆时针(CCW)(或顺时针(CW))排列的三角形内部,当且仅当3次To-Left Test返回True(或False)。因此,InTriangle的实现方式可如下:

也就是说,做1次In-Triangle Test就要相应的做3次To-Left Test。另外我们可以发现,3条线将平面分为7个区域,而每一个区域都对应着3次TLT的组合,然而3次TLT的组合共有8种,而那多出来的一种就在三角形的内部,CCW时,无FFF组合,CW时,无TTT组合。最后我们来考虑To-Left Test的实现方式,基于行列式会更简单的实现:

          |p.x   p.y   1|

2*S = |q.x   q.y   1|

          |s.x   s.y   1|

Area2算的是pqs三点构成的三角形的有向面积的2倍,通过值的正负来判断其是否在左侧,具体实现如下:

极边算法(Extreme Edges)

凡是对最终的凸包有贡献的那些边都称之为极边,反之为非极边。同样的,观察可得,如果一条边为极边,当且仅当其余所有的点都在这条边的同一侧。根据这条性质,我们可以得到甄别极边的伪代码:

很显然,这个算法的时间复杂度应该为O(n * (n-1) * (n-2)) = O(n3),相对于极点算法,有了明显的改进。算法的具体实现如下:

增量式策略(Incremental Construction)

回到我们的排序算法,在插入排序中,我们采用了减而治之(Decrease and Conquer)的思想,即一次接一次的从未排序部分中选出一个数插入到已排序部分中,同样可以将这种思想运用到凸包构造算法中,即一次接一次的从剩余的点集中选出一个点插入到已有凸包上。然而,如何确定接下来要插入的那个点就是极点呢?不妨采用In-Convex-Polygon Text,即如果新插入的那个点是极点,当且仅当它落在当前所构造的凸包的外部。如果ICPT返回true,那么仅仅抛弃这个点就可以;如果返回false,我们又将如何将这个新的点加入到凸包上呢?如果一个点x位于凸包的外部,那么必定有两个切点s和t,如下所示:

更新这个凸包,我们会发现,应该舍弃掉ts段,同时将x分别与s和t连接,即做了两条支撑线(Support-Lines)xt、xs。接下来的问题是,如何确定这两条支撑线呢?给定一个位于凸包外部的点x,当前凸包的所有极点都可以被分为4种状态:即对于每一个极点v,我们考虑ToLeft(x, v, v.pred())与ToLeft(x, v, v.succ())。这样我们就可以得到每一个极点的关于拐向的模式(Pattern Of Turns),显然,位于st上的极点都为R+L,位于ts上的极点都为L+R,切点s为L+L,切点t为R+R。如下:

这样我们就确定了两个切点s、t,幸运的是,我们其实可以不用判断x是否位于凸包的内部,实际上,如果x落在凸包的内部,当且仅当ts为空,即所有的极点都是R+L。因此我们只需要判断每个极点的Pattern即可:

通过上面的算法,插入一个点需要花费O(n)的时间,然而总共有n个点需要插入,则总的时间复杂度为O(n2)。

Jarvis March(Gift Wrapping)

回顾之前的极边算法,我们可以发现,在那个算法中,我们需要列举所有可能的边,这不得不花费O(n2)的时间,实际上,Jarvis注意到,所有的极边必然围绕成一个环状,并且,每一个随后的极边必然连着之前某一个极边的端点。

已知ik是一条极边,则下一条极边ks必然是左拐角最小的那条边,一旦ik被确定,则ks只需要检查O(n)次候选者即可找到。有了这样的发现,我们就不难写出Jarvis March的伪代码:

还有一个问题,就是应该如何确定第一个EP和EE,我们采用Lowest-Then-Leftmost来确定第一个EP,不失一般性,我们假设第一条EE是水平的。Jarvis March的具体实现如下:



发表评论

电子邮件地址不会被公开。 必填项已用*标注