1、凸性(Convexity)

  • 以颜色为例
    假设x,y,z是三种颜色，如果仅以x,y就能调出来的颜色，那么如u所示它一定会落在x,y中；若需要x,y,z三种 一起，那么如v所示会落在以x,y,z三点连成的三角形内部。

2、极点(Extreme Point)

在一组点中，沿着这个点作直线，必然能找到一条直线，使得其他所有点都在该直线的一侧。

  • 判断一个点是否为极点：看该点是否存在于其中的三个点围成的三角形的内部

s点就不是极点

  • To-Left Test：判断一个点是否存在于三个点围成的三角形内部，那么就对该三个点以逆时针方向两两连成有向边，如果该点在这三条直线的左侧，那么成立。（复杂度为O(n^4)）
1
2
3
4
5
6
bool InTriangle(Point p, Point q, Point r, Point s) 
{ bool pqLeft = ToLeft(p, q, s); 
  bool qrLeft = ToLeft(q, r, s); 
  bool rpLeft = ToLeft(r, p, s); 
return (pdLeft == qrLeft) && (qrLeft == rqLeft); 
}

这个ToLeft函数我们可以用海伦公式

1
2
3
4
5
6
7
8
9
10
bool ToLeft(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; 
    }

3、极边(Extreme Edge)

两个极点连成的边，剩余的所有点均会在该边的一侧。同样可利用此来判断是否是极点（复杂度为O(n^3)）

极边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void markEE(Point S[], int n) //n>2
{
    for(int k = 0; k <n; k ++)
        S[k].extreme = False; //先假设所有的点都不是极点
    for(int p = 0; p < n; p ++)
        for(int q = p + 1; q < n; q ++)
            checkEdge(S, n, p, q);
}

void checkEdge(Point S[], int n, int p, int q)
{
    bool LEmpty = True, REmpty = True;
    for(int k = 0; k < n && (LEmpty || REmpty); k ++)
    {
        if(k != p && k != q)
        {
            ToLeft(S[p], S[q], S[k]) ? LEmpty = False : REmpty = False;
        }
    }
    if(LEmpty || REmpty)
        S[p].extreme = S[q].extreme = True;
}

4、增量构造(Incremental Construction)

  • 有三种情况：点在内部无法增加；点在外部使得凸包大小变大；点在外部使得凸包大小变小

通过判断这个新的点是否在凸包外部，若在外部则可以增加进新的凸包里

在这里我们依然可以利用之前的ToLeft原则，如图所示是退化到最后的三角形后判断。

然而这个方法并不是想象中像二分法一样用减而治之的方式在O(nlog n)时间内就能达到，因为凸包是在不断变化中，所以不可能类似二分那样达到O(log n)的状态。

我们在实际操作中使用的方法是通过找切线来将这个点加入到凸包中。

这样一来，对于x点与原凸包的任意一个点v的做一个射线，那么v存在一个前驱和后继，如果前驱和后继都在射线右边或左边，那么它是一条切线。（在这里定义逆时针为正方向，一个点的前驱就是指该点在逆时针方向的下一个点，后继是顺时针方向的下一个点）

如果找不到这样的切线，那么该点在凸包内部。

5、Javis March

这个是减而治之的思想

我们首先确定一条极边，然后在以该极边的endpoint为起点随机的找其他点做射线，判断这条射线与之前的极边的ToLeft程度。然后不停地比较不同的点的射线，取程度最小的那个点。

在这里不考虑那种一条射线上有多个点的情况。

对于第一个点的确立我们是使用Lowest-then-leftmost策略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void Jarvis(Point S[], int n)
{
    for(int k = 0; k < n; k ++)
        S[k].extreme = false;  //假设所有的点都不是极点
    int ltl = LTL(S, n); int k = ltl;  //先利用LTL算法找到第一个极点,k是起点
    do
    {
        P[k].extreme = true; int s = -1;  //s是要找的下一个极点，用t去循环找
        for(int t = 0; t < n; t ++)
        {
            if(t != k && t != s && (s == -1 || !ToLeft(P[k], P[s], P[t])) 
                s = t; //如果t在pq的右边，更新s
        }
        P[k].succ = s; k = s; //新的极边pq确定
    }while(ltl != k); //如果循环回到了原点，结束
}

int LTL(Point S[], int n)
{
    int ltl = 0;
    for(int k = 1; k < n; k ++)
    {
        if(P[k].y < P[ltl].y || (P[k].y == P[ltl].y && P[k].x < P[ltl].x)
            ltl = k;
    }
    return ltl;
}

Javis March算法是输出敏感的，它的复杂性会随着凸包的规模变化而变化

6、下界(Lower Bound)

如果A问题 is reducssible to B，那么A的问题下界一定也是B的问题下界，但不一定是紧的。

则我们的凸包问题规约成一个排序问题。

对于二维凸包，点可以落在一条抛物线上。在形成凸包后的那个图像，每个点投影在x轴上必然有序的。最左边的极点x值最小，最右的最大。所以相当于是一个排序问题。因此凸包问题的下界与排序问题相同，都是O(nlogn)

7、Graham Scan

首先先有一条极边（LTL），然后在根据极角将剩下的点由小到大排序。有S栈和T栈，初始时点1和点2在S栈中，其他的点依次在T栈栈顶到栈底。
核心代码：如果T栈顶的点在S栈顶次栈顶的两个点的左边，那么就把T栈顶的点push进S栈，否则就把S栈顶的点pop出来。

1
2
3
4
while(!T.empty())
{
    toLeft(S[1],S[0],T[0]) ? S.push(T.pop()) : S.pop();
}

这个算法的正确性可以由数学归纳法证明。

对于这个算法而言，预处理（即对点的排序是很重要的不可跳过）

  • 关于它的复杂度：

LTL O(n)

presorting O(nlogn)

scan O(n)

  • 关于扫描部分的复杂度：

如图所示，我们过程中的那些边互不相交，整体构成一个平面图，因此至多就是o(3n)条边

更精确的来看，假设A=S.size() +2 * T.size()；那么算法过程每经过一个循环，A的值就减小一个单位。因此算法的规模不会超过2n-5。

  • 关于排序部分的问题：

当我们得到一系列点以x坐标排序时，如图所示，可以相当于是在y轴负方向无穷处有一个极点，然后就相当于是以那个为一个起点，从右到左来搜寻极点，这样我们可以构造出上凸包upper hull；反之构造下凸包。

因为在足够远的距离的时候那这些射线就相当于是平行边。

8、分而治之(Divided-And-Conquer)

分而治之，然后Merge

对于若干个点进行适当的分组，分别构造子凸包，然后再把它们合并成一个凸包

  • 关于Merge的问题

如图，可以是相当于对于两个凸包找到一个公共的核，然后这些点关于这个核有序。然后就可以进行Graham Sort。

  • 然而可能有以下三种情况：

我们算法的第一步是找到核。对于其中一个子凸包，可以任意取三个点，计算这个三角形的中心，然后判断这个点是否在另一个子凸包中（n次 ToLeft测试来判断）。

对于上图是属于比较好的情况，因为两个子凸包的极点都分别于核有序，那么只需要二路归并将这些点变成整体有序，然后在进行Graham Scan。

但如果在一个子凸包里找到的核是在另一个子凸包的外面的话：

我们就找出两个切点，那么ts段是无用的。然后舍弃完ts后就对st段的点和另外一个子凸包进行2-way merge，然后再进行Graham Scan。

  • 另外一种算法

首先两个子凸包构建的时候就让他们是可以通过一条垂线分开的。我们只需要找到两条切线就可以把这两个子凸包合并。

在这里要注意我们并不是把子凸包的最上面的点和最下面的点连接起来就行，有很多不是的情况。如下：

我们的实际操作是首先找到左边的子凸包的最右边的点，然后找到右边子凸包最左边的点。在这里的寻找方法只要之前在一步步构造子凸包的时候对他们的最左最右点进行记录，那么在需要的时候只需花费O(1)的时间就能找到，不然的话就需要用O(n)的时间来寻找这两个点。

把两个点连线后，然后选其中一个点作为是类似另一个子凸包的外部点，然后寻找相应的切线，直到找到后再以另外那个点作为之前的凸包的外部点找这一半的切线，找到后再反过来看是否还是另外一个凸包的切线，循环往复，直到这条切线同时是两个子凸包的切线为止。

这个步骤需要花费O(n+m)的时间