计算几何 —— 凸包

假设颜色的定义为$C = (R, G)$，现在手上有两种颜料$X = (x1, x2), Y = (y1, y2)$，是否可以混合出颜料$Z = (z1,z2)$?这个问题的解可以从几何角度来分析。想象一个二维直角坐标系X轴表示Red、Y轴表示Green，在图上做出点$X$与点$Y$的连线，通过判断点$Z$是否在线段$XY$上来确定是否可以混合到$Z$和混合的比例。假如有三种颜料$X,Y,Z$去混合颜料$U$,在几何角度看就是判断点$U$是否在三角形$XYZ$中，前提是三种颜料不共线也就是无法通过其中两种颜料混合得到第三种颜料。

凸相关

多增一种颜料但可由前几种颜料线性组合而得。

凸无关

多增一种颜料且这种颜料不可由前几种颜料线性组合而得。

由上述例子可以引出凸包的相关定义，其中多增的颜料点如果是凸无关的，它就是目前图中多边形的极点；在图中选出最少的颜色点可以通过线性组合求得图中所有的颜色点，由这些颜料围成的多边形即为凸包，这些颜料点称为极点，它们之间的连线即为极边。

定义

凸包（Convex Hull）

在平面上能包含所有给定点的最小凸多边形叫做凸包。

极点（Extreme Point）

存在一条线穿过该点，平面上所有给定点在线的同一侧。

极边（Extreme Edge）

由两个极点连接形成的边称为极边，平面上所有给定点在极边的同一侧。

算法

Excluding Non-extreme Points

时间复杂度：$O(n^4)$

由于凸包本身由极点构成，所以求出所有极点即可得到凸包。极点的判别方式为是否包含于某个三角形内部，遍历所有三角形的时间复杂度为$O(n^3)$，再乘上遍历所有点的时间$O(n)$，最终的时间复杂度为$O(n^4)$，接下来的问题是如何判断点是否在三角形的内部。

To Left Test

判断一个点是否在三角形的内部的充要条件为该点同时位于三角形三条边的左侧，其中三角形边的方向为逆时针。判断一个点是否在一条有向边的左侧的算法称为$ToLeftTest$。

$ToLeftTest$的具体实现来自三角形的有符号面积计算公式：$2 * S = \begin{vmatrix} p.x & p.y & 1 \\ q.x & q.y & 1 \\ s.x & s.y & 1 \end{vmatrix}$，当点$s$位于向量$\mathbf{pq}$左侧时面积为正数，当点$s$位于向量右侧时面积为负数，当点$s$位于向量$\mathbf{pq}$上时面积为0。

ToLeftTest代码实现

bool toLeftTest(Point p, Point q, Point s){
    return area2(p,q,s) > 0;
}
int area2(Point p, Point q, Point s){
    return 
        p.x * q.y - p.y * q.x
        + q.x * s.y - q.y * s.x
        + s.x * p.y - s.y * p.x;
}

ENP伪代码

Mark all points s of S as EXTREME
For each triangle(p, q, r)
    For each s ∈ S
        If s ∈ A(p, q, r) then
            mark s as NON_EXTREME

Excluding Non-extreme Edges

时间复杂度：$O(n^3)$

求出所有的极边也是一个的方法。由极边的定义可得判断一条极边的方法为判断图中所有点是否位于边的同一侧。遍历所有边的复杂度为$O(n^2)$，再乘上遍历所有点的时间$O(n)$，最终的时间复杂度为$O(n^3)$。

ENE伪代码

Let EE = Ø
For each directed segment pq
    If points in S lie to the same side of pq then
    Let EE = EE U {pq}

Incremental Construction

时间复杂度：$O(n^2)$

逐次将点加入，然后检查之前的点是否在新的凸包上。该过程分为两步，第一步是$InConvexPolygonTest$，判断点是否位于现有的凸包中，如果不是则需要进行第二步，将点添加入凸包并排除伪极点。

In Convex Polygon Test

可以通过计算点与凸包所有边的关系来判断。如果点都在所有边的“同一侧”（例如，对于逆时针顺序的凸包，都在所有边的右侧），则它在内部。

Tangents

排除伪极点的秘诀就是$Tangents$。点$x$ 不在凸包中则可以在原有的凸包上找到点$t$与点$s$，它们与点$x$相连即为新的凸包，它们的连线与原有凸包相切。原凸包上的点可以分为四类，点$t$、点$s$、位于$ts$上还有位于$st$上，区别它们的方法还是我们的老朋友$ToLeftTest$。遍历原凸包上的点将它们与$x$连线构建向量$\mathbf{xv}$，判断前一个点和后一个点位于向量$\mathbf{xv}$的方向，下面简称位于点$x$的左边与右边为$L$与$R$。如果在$InConvexPolygonTest$中判断所有边均为$R$，则点$s$为$LL$，点$t$为$RR$，$ts$上的点为$LR$，$st$上的点为$RL$，$st$与点$x$构成新的凸包。若$InConvexPolygonTest$中判断所有边均为$L$，则前面的结论相反。

Jarvis March

时间复杂度$O(kn)$

首先通过$LowestThenLeftmost$算法求出第一个极点，再从已知极点$x$出发，首先选择任意一个点$y$构建一个向量$\mathbf{xy}$判断剩余所有未判断的点与向量的位置关系，如果位于向量的右边则更新点$y$，不断往前推进找到下一个极点，直到回到第一个极点。假如凸包上一共有$k$个顶点，那么时间复杂度即为$O(kn)$。

Lowest Then Leftmost

对平面构造直角坐标系，纵坐标最小的点即为极点，如果存在多个这样的点取横坐标最小的点。

Graham Scan

时间复杂度$O(n\log n)$

第一步还是根据$LowestThenLeftmost$求出第一个极点，它跟其他各点的连线和x轴正向的角度，按小至大将这些点排序。这里的时间复杂度可达$O(n\log⁡n)$。

之后构造两个栈，栈$s1$存入当前的极点，按照编号由小到大将未判定点存入栈$s2$中。每次将$s2$的栈顶元素$x$弹出，去计算栈$s1$前两个元素构成的向量与点$x$的位置关系，如果再左边则将点$x$压入栈$s1$中，反之则不断弹出栈$s1$的栈顶元素直到仅剩一个元素为止或者点$x$位于向量的左侧，再将点$x$压入栈$s1$中，当栈$s2$不存在元素后算法停止。

Moosy'Blog

为生命干杯。