浏览量:823

8.2. 凸包算法综述

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

8.2. 凸包算法综述

8.2.1. 二维凸包

解决二维凸包问题,主要有Jarvis步进算法(Jarvis March),增量算法(Incremental Method),快速凸包算法(Quick Hull),分而治之算法(Divide and Conquer),Graham扫描算法,单调链算法(Monotone Chain),Kirkpatrick–Seidel算法,chan算法。

2015-3-24 10-13-28

图8.4 Jarvis步进法

Jarvis步进法是由Jarvis[6](1973)提出的,但是它只是比它更早的Chand&Kapur[3](1970)提出的礼物包裹(Gift Wrapping)算法在二维情况下的特例,Preparata&Shamos[4](1985),O'Rourke[1](1998)和Cormen el[5](2001)都有该算法更详细的描述。直观上,可以把Jarvis步进法看做是在集合Q的外面紧紧地包了一条线,线的一端固定在左下角的点上。把线向右拉使其绷紧,再拉高些,直到碰到一个点,这个点一定在凸包上。使线继续处于绷紧状态,查到下一个顶点,直至回来原点。更形式化的表示,是通过判断极角的大小,来确定下一个顶点,如图8.4(a)所示,先找到最左下角的点\({{p}_{0}}\)(点的X分量最小,若多个点X分量相同,选择其中Y分量最小的点,它一定是凸包的一个顶点,搜索过程需要\(O(n)\)的时间。接着相对于\({{p}_{0}}\),如图(b)所示,找到极角最小的点\({{p}_{1}}\),这一步搜索过程需要遍历点集中其它所有的点,算法复杂度是\(O(n)\)。接着是分别搜索\({{p}_{2}}\)\({{p}_{3}}\),直至回到起始点\({{p}_{0}}\),算法复杂度与输出的凸包的顶点相关。

2015-3-24 10-13-40

图8.5 增量凸包算法

增量算法另外一种求解凸包问题的算法,由Kallay[21](1984)提出,在O'Rourke[1](1998)中有该算法详细的描述,增量算法的复杂度是\(O({{n}^{2}})\)。它的基本思想是,随机选择若干个不共线的点,作为初始凸包,初始凸包可以是三角形也可以是四边形,为了使初始的凸包尽可能多的囊括非极点,可以选择最左、最右、最上、最下的四个点构成的四边形作为初始凸包。每次增加一个点,若该点在当前凸包内,则移除该点;否则,移除对该点可见的边,连接该点与当前凸包上和该点相切的点,产生新的凸包;重复上述步骤,直至点集中所有的点都处理为止。这里介绍两个重要的概念:可见与相切。若一个点\(p\)在凸多边形的边\(e\)指向外的法向量的一侧,称点\(p\)对边\(e\)可见或者称边\(e\)对点\(p\)可见。若点\(p\)在凸多边形外,那么对点\(p\)可见的边必然是连续的,它们可以表示为\(\overline{{{p}_{i}}{{p}_{i+1}}},\cdots ,\overline{{{p}_{j-1}}{{p}_{j}}}\),称点\({{p}_{i}},{{p}_{j}}\)为凸多边形上与点\(p\)相切的两个点。注意,这里的可见和相切的概念只限于点在凸多边形的情况。设凸多边形上一条边\(\overline{{{p}_{i}}{{p}_{i+1}}}\),该边指向外的法向量为\(\vec{n}\),若一个点\(p\)满足不等式\(\left( p-{{p}_{i}} \right)\cdot \vec{n}\succ 0\),则点\(p\)对边\(\overline{{{p}_{i}}{{p}_{i+1}}}\)可见,否则,不可见。以如图8.5(a)所示为例来解释下增量算法的基本过程,求点集 \(\left\{ {{p}_{0}},{{p}_{1}},{{p}_{2}},{{p}_{3}},{{p}_{4}} \right\}\)构成的凸包。首先随机选择三个不共线的点\(\left\{ {{p}_{0}},{{p}_{1}},{{p}_{4}} \right\}\),作为初始的凸包,如图(b)所示。接着,如图(c)所示,增加一个点\({{p}_{5}}\)\({{p}_{5}}\)在当前凸包内,是非极点,直接排除。如图(d)所示,增加一个点\({{p}_{2}}\),点\({{p}_{2}}\)对边\(\overline{{{p}_{4}}{{p}_{0}}}\)和边\(\overline{{{p}_{0}}{{p}_{1}}}\)不可见,但点\({{p}_{2}}\)对边\(\overline{{{p}_{1}}{{p}_{4}}}\)可见,与点\({{p}_{2}}\)相切的点就是\({{p}_{1}}\)\({{p}_{4}}\),移除\({{p}_{1}}\)\({{p}_{4}}\)之间的边,连接\({{p}_{1}}\)\({{p}_{2}}\)\({{p}_{2}}\)\({{p}_{4}}\),生成新的凸包。按照相同的方法处理点\({{p}_{3}}\),最后得到点集的凸包。搜索凸多边形上与点相切的两个顶点的暴力算法的复杂度是\(O(n)\),但是可以采用二分查找的方法进行优化,搜索的算法复杂度降低到\(O(logn)\),因此增量算法的复杂度可以从\(O({{n}^{2}})\)降低到\(O(nlogn)\)

2015-3-24 10-13-52

图8.6 快速凸包算法

快速凸包算法的思想,很早是由多个研究者[15,16]独立提出的,由于该算法与快速排序的思想很相似,因此Preparata&Shamos[4](1985)把它命名为快速凸包算法,并做了详细地描述,在O'Rourke[1](1998)中也有该算法的伪码表述。快速凸包算法在最好情况下,复杂度能达到\(O(nlogn)\),但是在最坏情况下复杂度是\(O({{n}^{2}})\),平均复杂度为\(O(nlogn)\)。以图8.6(a)所示为例,求点集\(\{{{p}_{0}},...,{{p}_{10}}\}\)的凸包。首先,找到点集中最左、最右、最上、最下的四个点,作为初始的凸包,尽可能多地舍弃初始凸包内的非极点,即舍弃点\({{p}_{8}}\)和点\({{p}_{9}}\)。现在考虑当前凸包外侧还未处理的点,先考虑边\(\overline{{{p}_{2}}{{p}_{3}}}\),从边的外侧点集中,找到与边距离最远的点,如图(b)所示,边\(\overline{{{p}_{2}}{{p}_{3}}}\)的外侧点集\(\{{{p}_{4}},{{p}_{5}},{{p}_{6}},{{p}_{7}}\}\)中,点\({{p}_{4}}\)与边的距离最远,找到当前凸包上与点\({{p}_{4}}\)相切的两个顶点,即顶点\({{p}_{2}}\)\({{p}_{3}}\),删除当前凸包上\({{p}_{2}}\)\({{p}_{3}}\)之间的边,连接\({{p}_{2}}\)\({{p}_{4}}\)\({{p}_{4}}\)\({{p}_{3}}\),生成新的凸包。如图(c)所示,舍弃在新的凸包内的点,即舍弃点\({{p}_{5}}\)和点\({{p}_{6}}\)。接着,只有边..和\({{p}_{3}}{{p}_{0}}\)的外侧还存在未处理的点集,按照前面的操作进行处理,如图(d)和(e)所示,最终得到由\({{p}_{0}},{{p}_{1}},{{p}_{2}},\)\({{p}_{4}},{{p}_{7}},{{p}_{3}},{{p}_{10}}\)共7个点构成的凸包,如图(f)所示。

2015-3-24 10-14-06

图8.7 分而治之凸包算法

分而治之算法最早是由Preparata&Hong[9](1977)提出的,它的基本思想,就是把点集分割成左右或者上下两半,分别求出两半点集的凸包,再把它们合并,合并操作的算法复杂度是\(O(n)\),用\(T(n)\)表示算法的复杂度,则有\(T(n)=2T(n/2)+O(n)\),因此分而治之算法的复杂度是\(O(nlogn)\)。以图8.7(a)所示为例,求点集\(\{{{p}_{0}},...,{{p}_{9}}\}\)的凸包。可以把点集分成左右两半,如图(b)所示,左半点集产生一个子凸包\(C{{H}_{1}}\),右半点集产生另一个凸包\(C{{H}_{2}}\);接着,需要把这两个子凸包合并成一个大凸包,找到两个凸包的切线\(\overline{{{p}_{4}}{{p}_{8}}}\)\(\overline{{{p}_{2}}{{p}_{5}}}\),删除切线之间两个子凸包相对可见的边,连接两个子凸包的切线,完成子凸包的合并。相对于其它算法来说,分而治之算法的实现难度较大,Schneider& Eberly [11](2002)对二维分而治之凸包算法的实现有详细的表述。

Graham扫描算法最早是由Graham[7]在1972年提出的,该算法最好和最坏的算法复杂度都是\(O(nlogn)\),实现也比较简单,能有效地处理各种退化情况,能有效的解决二维凸包问题,但是它无法扩展到三维,甚至于更高维的情况,因此对其它凸包算法的研究还是很有必要的,在后面的章节中将详细介绍该算法的思想和实现伪码。

单调链算法是由Andrew[17]在1979年提出的,它与Graham扫描算法相似,首先对点集进行排序,然后再利用有序的点集生成凸包,排序需要\(O(nlogn)\)时间,生成凸包需要\(O(n)\),算法的复杂度也是\(O(nlogn)\)。不同的是:(1)单调链算法排序是根据点的x,y坐标的字典序进行;(2)根据有序点集生成凸包时,它会把点集分为上下两半,上点集生成凸包的上顶点链,下点集生成凸包的下顶点链,两个顶点就构成了一个完整的凸包,算法是以构造凸包的两个单调链为目的,这就是为什么称该算法是单调链算法的原因。从效率上与Graham扫描算法相比较,单调链算法在排序中点的对比操作较简单,减少了计算量,但是增加了把点集划分为上下两半的操作。

首先对点集按照\(x,y\)递增的顺序排序,得到新的点集\(S=\left\{ {{p}_{0}},{{p}_{1}},\cdots ,{{p}_{n-1}} \right\}\),设\({{x}_{\min }},{{x}_{\max }}\)分别是点集上\(x\)坐标最小的和最大的值,显然有\({{p}_{0}}.x={{x}_{\min }}\)。设\({{p}_{\min ,\min }}\)表示点的\(x\)坐标等于\({{x}_{\min }}\)时,\(y\)坐标取最小值的点;同理\({{p}_{\min ,\max }}\)表示点的\(x\)坐标等于\({{x}_{\min }}\)时,\(y\)坐标取最大值的点。若点集\(S\)上存在多个不同点的\(x\)坐标都是\({{x}_{\min }}\),那么\({{p}_{\min ,\min }}\)\({{p}_{\min ,\max }}\)表示不同的点,否则它们表示相同的点。对于点\({{p}_{\max ,\min }},{{p}_{\max ,\max }}\)的定义也是类似的。如图8.8所示,连接\({{p}_{\min ,min}},{{p}_{max,\min }}\)\({{p}_{\min ,\max }},{{p}_{max,\max }}\),分别用\({{L}_{\min }}\)\({{L}_{\max }}\)表示。在直线\({{L}_{\max }}\)上方的点集称为上点集,构成凸包的上顶点链;同理,在直线\({{L}_{\min }}\)下方的点集称为下点集,由它构成凸包的下顶点链。上(下)点集构造单调链也是基于对栈的操作,跟Graham扫描算法相似。更详细的算法思想介绍和C++实现可以参考Dan Sunday[19]

2015-3-24 10-14-22

图8.8 单调链算法

Kirkpatrick–Seidel算法是由Kirkpatrick&Seidel[18]在1986年提出的算法,以他们的名字来命名该算法,算法是分而治之(Divide and Conquer)算法的逆过程,分而治之算法是先把问题分解为一个个子问题(Divide),依次解决完每个问题后(Conquer),合并子问题的结果(Marry)。KS算法则是先确定所有的子问题的结果是如何合并的,再考虑去解决每个子问题,Kirkpatrick&Seidel称之为“Marriage-Before-Conquest”法则。算法复杂度为\(O(n\log h)\),其中\(n\)表示点集的个数,\(h\)表示凸包的顶点个数,它的复杂度不仅与输入的点集相关,也与输出凸包的顶点个数相关。

Chan[20](1996)提出了另外一种实现更为简单、复杂度也是\(O(n\log h)\)的算法。

最后,对二维凸包算法进行总结,如表8.2所示:

       表8.2 二维凸包算法

2015-3-24 10-14-35

8.2.2. 三维凸包算法

解决三维凸包问题,主要有礼物包裹算法、增量算法、快速凸包算法、分而治之算法。

礼物包裹算法最早由Chand和Kapur[3] (1970)提出的,它不仅可以实现二维、三维凸包,还可以实现更高维的凸包,算法复杂度是\(O(nh)\)\(h\)表示输出的面的数量,\(n\)表示点集的个数,复杂度与输出凸包的面相关。直观上,三维的礼物包裹算法,可以看做是在点集的外面包围了一张纸,每次更新一个新的顶点,用纸覆盖住它,就像包裹礼物一样,直至包裹整个点集为止。

三维凸包的增量算法的复杂度是\(O({{n}^{2}})\),Clarkson&Peter[9](1989)提出了随机增量算法,它是增量算法的一种变种,通过把输入的点集进行随机化的操作,使算法的期望复杂度降为\(O(n\log n)\),O'Rourke[1](1998)提供了对增量算法C语言实现的详细描述,在开源的计算几何库CGAL[14]提供了三维凸包的随机增量算法的实现。

Barber et al[10](1996)对三维的快速凸包算法进行了描述,并且通过实验证明快速凸包算法比随机增量算法的速度更快,需要的存储空间更小,但是没有理论上的依据,算法的平均复杂度为\(O(n\log n)\),最坏情况下的复杂度为\(O({{n}^{2}})\)。其实,三维的快速凸包算法也可以看成是增量算法的一种变种,与随机增量算法相比,它们的不同就在于每次迭代从面的外部点集中选择的点不同。随机增量算法从外部点集中随机的选择一个点,但是快速凸包算法是选择距离最远的一个点。快速凸包算法已经有很广的应用,现在网上也有人提供有快速凸包算法健壮的算法实现,例如软件包Qhull[12]就提供了健壮的快速凸包的算法实现,还比如开源的计算几何库CGAL[13]也提供了快速凸包算法的实现,在后续的小节中将会详细介绍快速凸包算法。

凸包的分而治之算法最早由Preparata&Hong[8](1977)提出,该方法理论上能实现二维、三维甚至于更高维的凸包,算法的复杂度达到\(O(n\log n)\),是三维凸包算法中理论上最快的。但是这种算法的应用并不广泛,最根本的原因就在于算法实现的难度比较大。Day[14](1990)提供了对三维凸包分而治之算法的pascal语言的实现,但是它实现的算法的复杂度是\(O({{n}^{2}})\),并没有达到\(O(n\log n)\)。引用O'Rourke[1](1998)的一句话来对该算做一个简单的表述:“This Algorithm is both theoretically important, and quite beautiful. It is, however, rather difficult to implement and seems not used as frequently in practice as other asymptotically slower algorithms”。

spacer

Leave a reply