1.凸包的例子

1.1.简单求解

当着手设计一个计算凸包的算法时，此前所给出的凸包定义对我们没有多少帮助。按照定义，需要计算出“包含 P 的所有凸集的交”，可是这种集合有无限多个。而我们所观察到的“CH§是一个凸多边形”这一事实，则更有帮助。下面就来看看，CH§是由哪些边构成的。

算法 S L O W C O N V E X H U L L ( P ) 输入：平面点集 P 输出：由 C H ( P ) 的顶点沿顺时针方向排成的队列 L E ← ∅ f o r ( 每一有序对 ( p , q ) ∈ P × P ， p ≠ q ) { v a l i d ← t r u e f o r ( 除 p 和 q 之外的所有点 r ∈ P ) { i f ( r 位于 p 和 q 所确定有向直线的左侧 ) { v a l i d ← f a l s e b r e a k } } i f ( v a l i d ) { 将有向边 p q 加入到 E } } 根据集合 E 中的各边，找出 C H ( P ) 的所有顶点，并按照顺时针方向将它们组织为列表 L \begin{align*} &算法 SLOWCONVEXHULL(P) \\ &输入：平面点集 P \\ &输出：由 CH(P)的顶点沿顺时针方向排成的队列 L \\ &E ← ∅ \\ &for (每一有序对(p, q) ∈ P × P，p ≠ 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×P，p=q){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，接下来，就可以继续处理下一个点⎯⎯pi+1。然而，若最后的三个点构成一个左拐（left-turn），就必须将中间的（即倒数第二个）顶点从上凸包中剔除出去。

若出现这种情况，需要做的可能还远不止这些⎯⎯因为，此时的最后三个点可能仍然构成一个左拐（如 图 1-12 所示）。果真如此，就必须再次将中间的顶点剔除掉。这一过程需要反复进行，直到位于最后的三个点构成一个右拐，或者仅剩下两个点。

下面将给出该算法的伪代码。这段代码既计算上凸包，也计算下凸包。在完成后一项工作时，只需将各点自右向左排列，后续的计算与上凸包都是相仿的。

算法 CONVEXHULL(P) 
输入：平面点集 P 
输出：由 CH(P)的所有顶点沿顺时针方向组成的一个列表
根据 x-坐标，对所有点进行排序，得到序列 p1, …, pn
在 Lupper 中加入 p1和 p2（p1在前）
for (i← 3 to n)
{在 Lupper 中加入 piwhile (Lupper中至少还有三个点，而且最末尾的三个点所构成的不是一个右拐){将倒数第二个顶点从 Lupper 中删去    }
}在 Llower中加入 pn和 pn-1（pn在前）
for (i← n-2 downto 1)
{在 Llower中加入 piwhile (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）的软件包，然而运行速度会因此变得很慢。另一种方法是对算法本身作适当调整，使之能够检测到可能出现的不一致问题，并采取适当的措施以避免程序崩溃。然而如此一来，就不能保证算法的输出一定正确，因此，确定其输出的精确性就变得很重要。最后，（后一方法）还可以根据具体的输入，以数值的形式预测出，为了得到问题的正确结果，究竟需要达到多高的精度。
，然而运行速度会因此变得很慢。另一种方法是对算法本身作适当调整，使之能够检测到可能出现的不一致问题，并采取适当的措施以避免程序崩溃。然而如此一来，就不能保证算法的输出一定正确，因此，确定其输出的精确性就变得很重要。最后，（后一方法）还可以根据具体的输入，以数值的形式预测出，为了得到问题的正确结果，究竟需要达到多高的精度。