Question

Convex Hull

中译“凸包”或“凸壳”。在多维空间中有一群散佈各处的点，“凸包”是包覆这群点的所有外壳当中，表面积暨容积最小的一个外壳，而最小的外壳一定是凸的。

p = RandomInteger[10, {50, 3}]; Show[HighlightMesh[ConvexHullMesh[p], {Style[1, Black, Thick], Style[2, Opacity[0.7]]}], Graphics3D[{PointSize[0.03], Point[p]}]]

至于“凸”的定义是：图形内任意两点的连线不会经过图形外部。“凸”并不是指表面呈弧状隆起，事实上凸包是由许多平坦表面组成的。

以下讨论比较简单的情况：替二维平面上散佈的点，找到凸包。

二维平面上的凸包是一个凸多边形，在所有点的外围绕一圈即得凸包。另外，最顶端、最底端、最左端、最右端的点，一定是凸包上的点。

计算凸包时需考虑一些特殊情况：一、凸包上多点重叠；二、凸包上多点共线；三、凸包呈一条线段、一个点、没有点。通常我们会简化资讯，以最少的点来记录凸包，去掉重叠、共线的点。

UVa 109 132 218 361 596 675 681 811 819 10002 10065 10078 10135 10173 10256 10625 11168 11626 ICPC 4450

UVa 802 10089 ICPC 7585

任意图形的凸包

任意图形都能求出凸包。例如一个多边形的凸包、大量三角形的凸包、大量线段的凸包。这些问题都可以简化为一群点的凸包。

圆形、曲线的凸包，我们以下不讨论。

Convex Hull: Jarvis' March（Gift Wrapping Algorithm）

演算法

从一个凸包上的顶点开始，顺著外围绕一圈，顺时针或逆时针都可以。

每当寻找下一个要被包覆的点，则穷举平面上所有点，找出最外围的一点来包覆。可以利用叉积运算来判断。

时间複杂度为 O(N*M)，N 为所有点的数目，M 为凸包的顶点数目。

实作时请多多运用指标、索引值，儘量避免搬动原本资料。此处的程式码是不良示范，仅供参考。

如果想找出凸包上重叠的点与共线的点，则改为寻找离上一点最近的点，并且标记目前已包过的点。

Convex Hull: Graham's Scan

演算法

由前面章节可知：凸包上的顶点很有顺序的沿著外围绕行一圈，这个顺序是时针顺序。

Graham's Scan 尝试先将所有点依照时针顺序排好，再来做绕行一圈的动作，绕行途中顺便扫除凸包内部的点，如此就不必以穷举所有点的方式来寻找最外围的点。

要让所有点依照时针顺序排好，只要将中心点设定在凸包内部或者凸包上，然后让各点依照角度排序即可。如果把中心点设定在凸包外部，结果就不见得是时针顺序了。包覆时必须按照时针顺序，才能确保结果正确。

一般来说，选择凸包上的顶点当作中心点是比较好的，因为角度排序时的夹角皆小于 180°，可以使用叉积运算来排序（大于 180°叉积得负值、等于 180°叉积等于零，导致排序错误）。另一个好处是，中心点也可以作为包覆的起点。

角度排序时，遇到角度相同的情况，要小心排序。通常是让距离中心点较近的点排前面。也可以排后面，但是不能乱排。

扫除的过程当中，经常株连许多点。使用 stack 资料结构来储存凸包，逐一判断 stack 顶端的点，逐一弹出凹陷的点。凹陷的点必定不是凸包上的顶点。

Convex Hull: Andrew's Monotone Chain

演算法

前面章节採用时针顺序，此处改为座标顺序。以 X 座标大小排序，当 X 座标相同则以 Y 座标大小排序。

先从起点开始，按照顺序扫描，找到下半凸包。再从终点开始，按照相反顺序扫描，找到上半凸包。合起来就是完整的凸包。

一口气解决了凸包有重叠的点、共线的点、退化成线段和点的问题，是相当优美的演算法。

时间複杂度为排序的时间 O(NlogN)，加上包覆的时间 O(N)。总共是 O(NlogN)。

Convex Hull: Quick Hull Algorithm

演算法

一、找出最左点与最右点，连线，所有点分为上半部与下半部。
　　上半部与下半部分开求解。
二、处理上半部，找出上半凸包：
　甲、找到距离底线最远的点，形成一个三角形区域。
　　　（如果有许多点，就找最靠近左端点的那一点。避免凸包上多点共线。）
　乙、运用叉积运算，找出三角形外部的点，分为左、右两份。
　　　至于三角形内部、三角形上的点，不会是凸包顶点，尽数剔除之。
　丙、左、右两份分别递迴求解，直到找出上半凸包。
　　　三角形的两翼，分别做为左、右两份的底线。
三、处理下半部，找出下半凸包。

儘管时间複杂度是 O(N^2)，却是实务上最有效率的演算法。此演算法的好处是：预先剔除凸包内部大部分的点，而且不必预先排序所有点。

排序的时间複杂度是 O(NlogN)，空间複杂度是 O(N)。当点的数量很大时，例如一千万，时间约是一千万的 23 倍。又由于记忆体不足，必须採用外部排序，需要更多时间。

此演算法一开始扫描一次所有点，找到三角形外部的点，时间约是一千万的 1 倍。如果三角形外部的点很少，例如一千点，那麽接下来的步骤得以节省许多时间。因此，总时间通常远低于一千万的 23 倍。

递迴呼叫函数很花时间。当递迴一两次后，点数变少，此时可以直接套用其他凸包演算法，节省时间，例如 Andrew's Monotone Chain。

Convex Hull: Divide and Conquer

演算法

一开始将所有点以 X 座标位置排序。
Divide：将所有点分成左半部和右半部。
Conquer：左半部和右半部分别求凸包。
Combine：将两个凸包合併成一个凸包。

合併凸包，找到两条外公切线即可。从左凸包最右点、右凸包最左点开始，固定左端顺时针转、固定右端逆时针转，轮流前进直到卡死，就得到下公切线，时间複杂度为 O(N)。

注意到，下公切线并不见得是左右两凸包的最低点连线，所以就算一开始抓的是左右凸包的最低点，运气不好时，仍需要 O(N) 时间才能找到下公切线。况且抓最低点有可能已经衝过头了。

附带一提，内公切线也可如法炮制，改为从左凸包最左点、右凸包最右点开始。如果一个取内侧、一点取外侧，找公切线有可能衝过头。

正确性证明：找外公切线的过程中绝对不会与两凸包相交、找内公切线的过程中一定会与两凸包相交，卡死时即是相交与不相交的分际，分际即是公切线。

时间複杂度为下述两项总和：一、一次排序的时间，通常为 O(NlogN)；二、Divide and Conquer 向下递迴 O(logN) 深度，合併凸包需要 O(N) 时间，总共为 O(NlogN)。

不预先排序

一开始可以不必排序，只要把所有点分成两等份即可。两个凸包合併成一个凸包时，两个凸包可能会重叠，仍然可以用 O(N) 时间解决，不过演算法较複杂，此处省略之。

Convex Hull: Incremental Method

演算法

这是 online 演算法，随时维护一个凸包。每当输入一点，如果此点在凸包内部就直接捨弃；不然就计算此点与当前凸包的两条切线，然后更新凸包。

要找切线，穷举切点即可。切点的左右邻点都在切线同侧，反之则否，判断仅需 O(1) 时间。要小心切线与边重叠的情况。

凸包的资料结构採用 circular list，找到两个切点后，移除其间的连续凹点仅需 O(1) 时间。总时间複杂度是 O(N^2)。

改进

换个角度想，想要找到新凸包，直接穷举新凸包的顶点不就好了？

以试误法尝试旧凸包的每个顶点。以当前输入点为基准，若为凸面、切点，则留下；若为凹面，则捨弃。最后就得到新凸包。

如此一来就不需要特殊资料结构了。时间複杂度是 O(N^2)。

加速

以当前输入点为基准，切点的一侧是凸面，另一侧是凹面，切点恰为凹凸分际。故可用 Binary Search 找切点。

凸包的资料结构可以採用 Splay Tree，找切点、移除连续顶点仅需 O(logN) 均摊时间。总时间複杂度是 O(NlogN)。

Splay Tree 作排序时，可以参考凸包最左下点，以角度排序。

预先排序

预先按照 XY 座标排序所有点（平移的扫描线），此演算法便与 Andrew's Monotone Chain 大同小异，时间複杂度为 O(NlogN)。

预先排序之后，当前输入点必在凸包外部（点不重複时）、必有两条切线。

预先随机排列

随机排列、排序，两者概念相反。

预先随机排列所有点，则第 i 回合固定新增两点、平均扫描 N/i 点，平均时间複杂度为 O(NlogN)。推广到三维空间仍然如此。

Convex Hull: Chan's Algorithm

演算法

原理是 Trial and Error 与 Divide and Conquer。

一、假设凸包最多有 M 个点。
二、使用试误法，依序尝试 2^(2^0)、2^(2^1)、2^(2^2)、……这些数值作为 M。
　甲、每 M 个点为一组，所有点被分作⌈N/M⌉组。
　　　O(N)。
　乙、每一组各自求凸包，一共得到⌈N/M⌉个凸包。《Graham's Scan》
　　　O(MlogM * ⌈N/M⌉) = O(NlogM)。
　丙、尝试求出这些凸包的凸包。《Jarvis' March》
　　　O(3 * ⌈N/M⌉ * M) = O(N)。
　　子、每个凸包各用一个指标，指著各自的最低点。
　　　　O(N)。
　　丑、找出所有凸包的最低点，从最低点开始包覆。
　　　　O(N)。
　　寅、每当寻找下一个要被包覆的点：
　　　回、各凸包各自找出最靠外面的一点，一共得到⌈N/M⌉个点。
　　　　　由指标处继续往后找，指标只进不退。要预览下一点。
　　　　　O(3 * ⌈N/M⌉)，均摊。
　　　回、再从这⌈N/M⌉个点当中，看看哪一点最靠外面。
　　　　　O(⌈N/M⌉)。
　　卯、若包了 M 个点还未形成凸包，则马上停止，回到步骤二！
　　　　如果途中形成凸包，即是正解。演算法结束。

时间複杂度

步骤二的时间複杂度是 O(NlogM)，M 每次都不同。对 M 进行试误时，谨慎的选择 M 的数值，可以将所有步骤二的时间複杂度总和，强压在 O(NlogM) 以内。

对 M 进行试误时，
用 0、1、2、……、M，整体的时间複杂度为：
O(Nlog0 + Nlog1 + Nlog2 + ... + NlogM) = O(N * logM * M)

用 2^0、2^1、2^2、……、M，整体的时间複杂度为：
O(N*0 + N*1 + N*2 + ... + NlogM) = O(N * logM * logM)

用 2^(2^0)、2^(2^1)、2^(2^2)、……、M，整体的时间複杂度为：
O(N*1 + N*2 + N*4 + ... + NlogM) = O(N * logM)

用 N，直接就找到答案，不过整体的时间複杂度，不是我们所要的：
O(NlogN)

选择 M 的原理，其实就是“ 倍增搜寻 ”。

总时间複杂度是 O(NlogM)，N 为所有点的数目，M 为凸包的顶点数目，是目前时间複杂度最低的演算法。然而实际执行起来，比先前介绍的演算法来得慢。

Convex Hull of Simple Polygon: Melkman's Algorithm

演算法

求出一简单多边形的凸包。

http://cgm.cs.mcgill.ca/~athens/cs601/Melkman.html

时间複杂度为 O(N)。是相当优美的演算法。

Convex Layers

Convex Layers（Onion）

由外往内，一层一层的凸包，每一层都是一个 Convex Layer。全部的 Convex Layer 合称为一个“洋葱”。

最内部的 Convex Layer 可能退化成一个点或是一条线段。

演算法

使用 Jarvis' March 一直绕圈，时间複杂度为 O(N^2)。

排序所有点之后，不断找出剩馀诸点的凸包，最多找 O(N) 次凸包。可以採用 Graham's Scan 或者 Andrew's Monotone Chain。总时间複杂度为 O(NlogN) + O(N^2) = O(N^2)。

ICPC 3655