1.凸包的例子1.1.简单求解当着手设计一个计算凸包的算法时此前所给出的凸包定义对我们没有多少帮助。按照定义需要计算出“包含 P 的所有凸集的交”可是这种集合有无限多个。而我们所观察到的“CH§是一个凸多边形”这一事实则更有帮助。下面就来看看CH§是由哪些边构成的。算法SLOWCONVEXHULL(P)输入平面点集P输出由CH(P)的顶点沿顺时针方向排成的队列LE←∅for(每一有序对(p,q)∈P×Pp≠q){valid←truefor(除p和q之外的所有点r∈P){if(r位于p和q所确定有向直线的左侧){valid←falsebreak}}if(valid){将有向边pq加入到E}}根据集合E中的各边找出CH(P)的所有顶点并按照顺时针方向将它们组织为列表L \begin{align*} 算法 SLOWCONVEXHULL(P) \\ 输入平面点集 P \\ 输出由 CH(P)的顶点沿顺时针方向排成的队列 L \\ E ← ∅ \\ for (每一有序对(p, q) ∈ P × Pp ≠ q) \\ \{ \\ \quad valid ← true \\ \quad for (除 p 和 q 之外的所有点 r ∈ P) \\ \quad \{ \\ \quad \quad if (r 位于 p 和 q 所确定有向直线的左侧) \\ \quad \quad \{ \\ \quad \quad \quad valid ← false \\ \quad \quad \quad break \\ \quad \quad \} \\ \quad \} \\ \\ \quad if (valid) \\ \quad \{ \\ \quad \quad 将有向边pq加入到 E \\ \quad \} \\ \} \\ 根据集合 E 中的各边找出 CH(P)的所有顶点并按照顺时针方向将它们组织为列表 L \end{align*}算法SLOWCONVEXHULL(P)输入平面点集P输出由CH(P)的顶点沿顺时针方向排成的队列LE←∅for(每一有序对(p,q)∈P×Ppq){valid←truefor(除p和q之外的所有点r∈P){if(r位于p和q所确定有向直线的左侧){valid←falsebreak}}if(valid){将有向边pq加入到E}}根据集合E中的各边找出CH(P)的所有顶点并按照顺时针方向将它们组织为列表L根据 E可以按照如下方法构造出列表 L。E 中各边都是有向的因此可以定义它们的起点与终点。在指定每条边的方向时我们都使得其它的所有点都位于它的右侧⎯⎯这样如果按照顺时针方向遍历traverse所有顶点那么每条边的起点都会先于其终点被枚举出来。现在如 图 1-7 所示在E中任意删除一条边→e1将→e1的起点、终点分别做为第一、第二个点放入L从E中找出以→e1的终点为起点的边→e2将→e2从E中删去并将其终点插入到当前L的末尾再找出以→e2的终点为起点的边→e3将→e3从E中删去也将其终点插入到当前L的末尾……。不断重复上述过程直到E中只剩下最后一条边。至此已经大功告成⎯⎯因为最后这条边的终点必然就是→e1的起点而该点已经加入到L中了。若直截了当地实现这一过程需要O(n2 )时间。SLOWCONVEXHULL 算法的复杂度并不难分析。总共要检查 n 2 – n 对点。对每一对点要检查其它的 n – 2 个点看看它们是否都位于该点对所确定有向线段的右侧。这总共需要运行 O(n3 )时间。最后一步需要 O(n2 )时间故总体的时间复杂度为 O(n3 )。如 图 1-8 所示相对于由p和q所确定的直线一个点r的位置并不是非左即右⎯⎯有时可能正好落在这条直线上⎯⎯这就是所谓的“退化情况”degenerate case或者简称为“退化”degeneracy。在可能出现退化情况时为了保证算法始终运行正确就必须这样来重新表述上述准则某条有向边→pq是 CH§的一条边当且仅当相对于由 p 和 q 所确定的有向直线所有的其它点 r ∈ P 或者严格地位于其右侧或者落在开线段—pq上假定 P 中没有相互重合的点。精度误差如 图 1-9 所示试想有三个点p、q和r几乎共线而其它各点与它们都相距很远。按照上面的算法要分别对点对(p, q)、(r, q)和(p, r)进行测试。既然这三个点几乎共线则由于舍入误差的存在判断的结果很有可能是r位于直线—pq的右侧p位于直线—rq的右侧而q位于直线—pr的右侧。显然这种几何位置关系是不可能的⎯⎯然而浮点运算可不管这些在这种情况下算法将会把这三条边全都挑选出来。更糟糕的情况是这三次测试的结果也可能正好与上面相反这样如 图 1-10 所示算法就会将这三条边都排除掉于是在所生成的“凸包”边界上将会出现一个缺口。等到算法的最后一步⎯⎯将凸包的顶点组织为有序表⎯⎯时这将会导致严重的错误。实际上这一步有个假定在凸包的每一顶点处出边和入边都正好只有一条。然而受到舍入误差的影响某个顶点 p 可能会有两条出边也可能根本就没有出边。在上面那个简单的算法中最后一行并没有考虑到对不一致数据的处理因此若直接按照该算法编程实现程序就可能会崩溃。1.2.递增式求解我们将采用一种标准的算法设计模式⎯⎯递增式策略⎯⎯来设计一个递增式算法incremental algorithm。顾名思义我们将逐一引入 P 中各点每增加一个点都要相应地更新目前的解。这个递增式方法将沿用几何上的习惯按照由左到右的次序加入各点。于是首先需要根据 x-坐标对所有点进行排序产生一个有序的序列p1, …, pn。接下来我们将按照这一顺序将它们逐一引入。本来既然是自左而右地进行处理所以要是凸包上的顶点也能按照它们在边界上出现的次序自左向右地排列将会更加方便。然而情况并没有这样好。因此我们将首先计算出构成上凸包upper hull的那些顶点。如 图 1-11 所示所谓的上凸包就是从最左端顶点p1 出发沿着凸包顺时针行进到最右端顶点pn之间的那段。换而言之组成上凸包的就是从上方界定凸包的那些边。此后再自右向左进行一次扫描计算出凸包的剩余部分⎯⎯下凸包lower hull。该递增式算法的基本步骤就是在每次新引入一个点 pi 之后对上凸包做相应的更新。也就是说已知点 p1, …, pi-1 所对应的上凸包计算出 p1, …, pi 所对应的上凸包。可以按照如下方法进行。若按照顺时针方向沿着多边形的边界行进则在每个顶点处都要改变方向。若是任意的多边形则每次的转向既可能是向左也可能向右。然而若是凸多边形则必然每次都是向右转。根据这一点在新引入 pi之后可以进行如下处理。令 Lupper为从左向右存放上凸包各顶点的一个列表。首先将pi 接在 Lupper 的最后⎯⎯既然在目前已经加入的所有点中pi 是最靠右的则它必然是当前上凸包的一个顶点所以这样做无可厚非。然后再检查 Lupper中最末尾的三个点看看它们是否构成一个右拐right-turn。若构成右拐则大功告成此时更新后的Lupper 记录了组成上凸包的各个顶点 p1, …, pi接下来就可以继续处理下一个点⎯⎯pi1。然而若最后的三个点构成一个左拐left-turn就必须将中间的即倒数第二个顶点从上凸包中剔除出去。若出现这种情况需要做的可能还远不止这些⎯⎯因为此时的最后三个点可能仍然构成一个左拐如 图 1-12 所示。果真如此就必须再次将中间的顶点剔除掉。这一过程需要反复进行直到位于最后的三个点构成一个右拐或者仅剩下两个点。下面将给出该算法的伪代码。这段代码既计算上凸包也计算下凸包。在完成后一项工作时只需将各点自右向左排列后续的计算与上凸包都是相仿的。算法 CONVEXHULL(P) 输入平面点集 P 输出由 CH(P)的所有顶点沿顺时针方向组成的一个列表 根据 x-坐标对所有点进行排序得到序列 p1, …, pn 在 Lupper 中加入 p1和 p2p1在前 for (i← 3 to n) { 在 Lupper 中加入 pi while (Lupper中至少还有三个点而且最末尾的三个点所构成的不是一个右拐) { 将倒数第二个顶点从 Lupper 中删去 } } 在 Llower中加入 pn和 pn-1pn在前 for (i← n-2 downto 1) { 在 Llower中加入 pi while (Llower中至少还有三个点而且最末尾的三个点所构成的不是一个右拐) { 将倒数第二个顶点从 Llower中删去 } 将第一个和最后一个点从 Llower中删去以免在上凸包与下凸包联接之后出现重复顶点 } 将 Llower联接到 Lupper 后面将由此得到的列表记为 L return(L)与上回一样只要仔细分析就会发现上面的算法并不正确。不用说这里同样隐含了这样一个假设所有点的 x-坐标互异。一旦这个假设不成立根据 x-坐标所定义的次序就可能有歧义。幸运的是这一问题实际上并不严重。我们只需以一种合适的方式对这个次序进行推广⎯⎯使用字典序而不是仅仅根据各点的 x-坐标来确定其次序。也就是说首先按照 x-坐标排序倘若有多个 点的 x-坐标雷同则进而按照 y-坐标对它们排序。还有一种特殊情况被忽略了如 图 1-13 所示在对三个点进行比较以判断它们究竟是构成一个左拐还是右拐的时候有可能它们恰好共线。在这种情况下居中的那个那些点不应该出现在最后的凸包上⎯⎯因此应该将共线的点看成是构成一个左拐。也就是说只有在三个点的确构成一个右拐的时候我们的测试子程序才应返回“真”而在其它情况下都应返回“假”。经过如此修改我们的算法就能够正确地计算出凸包⎯⎯如 图 1-14 所示经过第一趟扫描构造出上凸包根据现在的定义它是从按字典序最小的顶点出发按照顺时针方向沿着凸包到达字典序最大顶点之间的一段路径第二趟扫描则构造出凸包的剩余部分。如果由于采用浮点运算而出现舍入误差这个算法又将如何若果真发生这类错误原本应该属于凸包的某个点就有可能被遗漏掉。不过该算法输出的结构完整性还不致于受到破坏⎯⎯也就是说它依然能够计算出一个封闭的多边形链。无论如何算法所输出的顶点列表总是可以被理解为某个多边形各顶点沿顺时针方向的一个枚举而且前后相邻的任何三个点都构成一个右拐或者由于存在舍入误差它们近似地构成一个右拐。另外P 中的每个点都不可能与计算出的凸包相距太远。现在只可能出现一种问题⎯⎯当某三个点相距很近时尽管它们构成一个很明显的左拐却可能会被判断为一个右拐。其后果是计算出的多边形的边界上可能会出现一处凹陷。解决该问题的一种方法就是要比如借助舍入误差确保相距极近的输入点都能被当成同一个点来处理。这样尽管最终得到的结果不见得肯定分毫不差但这种结果毕竟是有意义的⎯⎯实际上既然我们采用的本来就是不精确的运算自然就不可能指望做到百分之百的准确。对许多应用问题而言这样已经足够好了。正确性证明这里只证明对上凸包的计算是正确的下凸包计算正确性的证明相仿。证明的方法是对处理的点数进行归纳。在for-循环开始之前Lupper只包含p1 和p2 两个点这是平凡的情况因为{p1, p2}的上凸包就是由这两个点自己确定的。假定Lupper中已经存放了{p1, …, pi-1}对应的上凸包现在来考虑加入pi。在执行完while-循环之后由归纳假设可知Lupper中的各点依次组成一条链而且该链始终都是右拐。此外该链起始于{p1, …, pi}中字典序最小的点终止于字典序最大的点⎯⎯也就是pi。为了证明Lupper中存放的点就是正确的结果只需证明{p1, …, pi}中的各点要么在Lupper中要么就位于该链的下方。我们可做归纳假设在引入pi之前没有任何点位于此前多边形链的上方。由于此前那条链必定位于新链的下方故倘若有某个点位于新链的上方它只可能出现在由pi-1和pi界定的垂直条形区域中如 图 1-15 所示。然而这是不可能的⎯⎯因为果真如此该点的字典序必然介于pi-1与pi之间。你需要按照类似的思路自行验证一下在pi-1、pi或者其它点的x-坐标相同时这个结论依然成立。时间复杂度分析为了证明其时间复杂度的上界upper bound请首先注意到按照字典序对各点进行排序需要 O(nlogn)时间。接下来考虑上凸包的计算。for-循环要执行的趟数是线性的。这样只需要考虑其中while-循环的执行趟数。在每一趟for-循环中while-循环至少要执行一趟。而如果还要额外地执行while-循环则每趟都会将某个点从凸包中剔除出去。在构造上凸包的整个过程中每个点至多只能被删除一次因此在所有for-循环中while-循环额外的执行趟数加起来不会超过 n。可以类似地证明下凸包的计算也至多消耗 O(n)时间。因此整个计算凸包算法的时间复杂度取决于排序那一步即 O(nlogn)。1.3.退化及鲁棒性正如在前一节中已经看到的一个几何算法的建立过程往往要经过三个阶段。在第一个阶段需要理解我们正在处理的几何概念。然而我们的思路总是会被一些问题打乱因此要尽力去忽略这些问题。这类令人讨厌的问题有的来自多点共线有的来自垂直线段。在设计或理解算法的最初阶段暂且将这些退化情况搁到一边是一种十分有益的策略。接下来的第二个阶段必须对前一阶段所设计的算法进行调整使之即使对退化情况也依然能正确处理。在完成这一任务时初学者往往会将一大堆的特殊情况引入到算法之中。然而在很多情况下还有更好的办法⎯⎯通过对问题的几何性质做再次的分析往往可以将各种特例集成到一般情况当中。例如在凸包算法中只要使用字典序来代替 x-坐标顺序就可以处理多个点具有相同 x-坐标的问题。这种方式叫做集成式处理方式。最后一个阶段是具体的实现。这时需要考虑到基本的操作比如测试某个点究竟是位于一条有向直线的左侧、右侧还是落在其上。在具体实现的阶段还会出现另一个问题⎯⎯企图“对实数进行精确运算”是不现实的⎯⎯因此对于其后果我们不可不有所了解。在几何算法的实现过程中所遇到的种种麻烦究其根源往往可以归结为鲁棒性robustness的问题。这类问题非常棘手。有一种方法就是借助于某个根据具体的问题可能采用整数、有理数甚至代数数来支持精确运算exact arithmetic的软件包然而运行速度会因此变得很慢。另一种方法是对算法本身作适当调整使之能够检测到可能出现的不一致问题并采取适当的措施以避免程序崩溃。然而如此一来就不能保证算法的输出一定正确因此确定其输出的精确性就变得很重要。最后后一方法还可以根据具体的输入以数值的形式预测出为了得到问题的正确结果究竟需要达到多高的精度。然而运行速度会因此变得很慢。另一种方法是对算法本身作适当调整使之能够检测到可能出现的不一致问题并采取适当的措施以避免程序崩溃。然而如此一来就不能保证算法的输出一定正确因此确定其输出的精确性就变得很重要。最后后一方法还可以根据具体的输入以数值的形式预测出为了得到问题的正确结果究竟需要达到多高的精度。
