凸包问题

Introduction

这篇笔记的主题是 如何构造一个凸包。要解决这个问题,我们首先要知道什么是 凸包

在线性代数中,我们定义一组基向量,就可以以此为基础生长出一个线性空间。我们可以用这组基向量去表示空间中的其他任意向量,表示的方法就是线性组合(linear combination)。

类似的,我们可以定义凸组合(convex combination)。与线性组合不同的是,凸组合中每个“基底”的数乘倍数一定要是非负数,并且数乘倍数之和一定要是1。

我们用更为数学的语言表示如下:

\[ \begin{equation} \left\{ \begin{array}{**lr**} let \; \lambda = \; <\lambda_1,...,\lambda_n>^T \in \epsilon^2; \\ \lambda_1 + \lambda_2 + ... + \lambda_n = 1; \\ min \; {\lambda_i}\geq 0; \end{array} \right. \end{equation} \]

这样的一个凸组合所覆盖的区域,我们就称为一个凸包(Convex Hull

现在我们把目光转向如何构造一个凸包以及如何高效率地构造。

Algorithm

Definition

我们先定义一下基本的数据结构,以便后续程序使用。

Point

Exterme Point

所谓的 Exterme Point(极点)。并非微积分中的极点。在这里,是指凸包最外的点,也是构成凸包的基本单位。 我们一个很朴素的想法是,遍历所有的极点,使得找到其中不被其他所有极点构成的任意三角形包围的点,那些点就一定是极点。

这是一个很自然的想法,我们知道一个凸包的极点,一定是在最外层的,很自然地不应该被其他极点所构成的三角形所包围。(否则,选择可以包围它的三角形中适当的一个点替换掉它,可以使得凸包的面积更大)

于是我们有如下的思路:

1
2
3
4
5
Make all points of S as extreme \\O(n)
for each triangle Δ(p,q,r) \\ O(n^3)
for each s belongs to S\{p,q,r} \\O(n)
if s belongs Δ(p,q,r)
mark s as non_extreme_point

可运行的代码如下(typescript):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function extremPoint(S:Array<Point>){
let n = S.length;
for(var i=0;i<n;i++){
S[i].extreme = true;
}
for(var p=0;p<n;p++) {
for(var q=p+1;q<n;q++){
for(var r=q+1;r<n;r++){
for(var s=0;s<n;s++){
if(s==p || s==q || s==r || !S[s].extreme)
continue;
else{
if(inTriangle(S[p],S[q],S[r],S[s])){
S[s].extreme = false;
}
}
}
}
}
}
return S;
}

我们通常有这样的经验,越是简单的算法时间复杂度也就越高。是的,这个算法的时间复杂度并不低:\(O(n^4)\)。 我们根据点去遍历所有可行的三角形,本身就需要\(O(n^3)\)的时间。这在实际的问题中,往往是很难接受的。

Exterme Edge

很自然地,我们可以通过边之间的关系来思考另一种算法。即:遍历所有的边,其中所有能够成为极边的边一定满足 点集中所有的点,一定位于这条边的同侧。这是很显然的,如果一条边能够位于凸包的中间,那么它一定是非极边(non-extreme-edge)

于是,我们可以给出伪代码如下:

1
2
3
4
5
6
mark all points of S as non_extreme_point
for s and t belong to S:
let e = (s,t) as an edge
if all points belong to S\{s,t} lie to same side of e:
mark e as extreme_edge
mark s,t as extreme_point

现在,我们想要解决的问题就变成了如何判断一个点集中的所有点都位于一条直线的同侧。 这件事情也是非常容易的,我们只需要遍历点集中的所有点,所有点只出现在这条边的同侧,那么这条边就是极边。

1
2
3
4
5
6
7
8
当前判定的边 e(s,t)
对于点集S中,所有除s、t外的点p:
如果 p 与 s、t形成的有向面积大于0:
直线左边区域不为空
否则:
直线右边区域为空
如果 直线左右至少有一个为空:
s、t为极点

可执行的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
function checkEdge(S:Array<Point>,p:number,q:number){
let LEmpty:boolean = true;
let REmpty:boolean = true;
let n = S.length;
for(let k=0;k<n && (LEmpty || REmpty);k++){
if(k!=p && k!=q){
ToLeftTest(S[p],S[q],S[k])?LEmpty=false:REmpty=false;
}
}
if(LEmpty || REmpty)
S[p].extreme = S[q].extreme = true;
}

我们可以看到,这样的一个基于极边判断的算法,其时间复杂度为\(O(n^3)\)。尽管这个算法的时间复杂度相对基于极点判断的算法快了一个线性因子,但这还不足以满足我们的需求。下面我们将介绍其他的更快的算法。

Incremental Strategy

前面介绍的两种算法,无论是基于极点还是极边判断,都是一种暴力算法。它的原理很简单,去遍历所有可能的情况,满足的就留下来,不满足的就剔除。也因为它遍历了所有的情况,自然时间复杂度会很低下。

这里我们介绍 Incremental Strategy,也就是 增量策略。所谓的 Incremental Strategy,实质上就是 Decrease and Conquer(减而治之)。我们在数据结构中学到的一个很典型的减治算法插入排序。插入排序和这里这里要介绍的凸包构造算法有着很多相似处。

在插入排序中,我们假设已经有一段有序的序列,下面要做的事情就是把无序序列中的第一个元素插入到有序序列中的适当位置。这样逐步蚕食,我们一定可以断定:最终序列会成为整体有序的。

同样, Incremental Construction 也是假设我们已经有了一些极点,紧接着去遍历其他的点,如果遍历到的点能够使得凸包的面积增大,则把它作为极点,否则略过。

那么,我们如何判断面积将会增加呢?自然,在凸包外的点才有可能使得凸包面积增加。

In-Convex-Polygon Test

In-Convex-Polygon Test 的流程如上图。我们判断一个点是否在当前凸包内部,往往是通过判断它是否在所有极边的同侧,如果是,那么就一定是凸包内部的点。否则,一定是凸包外部的点。

这个流程图里给出了一个二分的方法,看似能够把判断的时间复杂度优化到 \(O(logn)\)。但是很遗憾的是,这里与插入排序类似,因为 “有序”的部分是动态的,每次插入或者删除某些极点,一定会改变这个动态的结构。因此就算引入了二分的方法,在最坏时间复杂度的角度考虑,这种改进是没有意义的。

我们在这里就简单地线性判断就好了。

通过判断,我们知道了点 x 是落在凸包外部的。并且可以得到它的两条切线对应的凸包上的切点:t、s

下一步,我们要做的工作就是把t、s、x连接起来,使得凸包的面积变得更大。显然,这里我们只需要选择远离x的那条连接t、s两点的折线保留下来。

一个很核心的问题: 如何确定切线?

我们观察得到:切点与 x 的连线,一定满足切点的前驱与后继在同侧。通过这个方法,我们就可以确定好两个切点了。我们称凸包上的极点的 pattern 为其前驱与后继节点相对其的 toLeft 关系。

我们如何定义切点的前驱(prev)与后继(succ)呢?我们把所有的节点按照逆时针(ccw)的方向排序,由此定义前驱与后继。

比如 pattern 为 L+L,就说明这个极点的前驱与后继都在它的左边。这个极点也理应作切点。

一个很幸运的事情是: 我们其实无需把判断点在凸包内外与寻找切点分开,因为 只要点在凸包内部,一定有它的 pattern 是“L+R” 或者 "R+L"

最终,我们通过 Incremental Strategy一定能保证最终得到的极点序列就是正确的极点序列。

Jarvis March

Jarvis 算法基于这样的一个事实:如果存在极边(k,i),所有相对于有向线段(k,i)的射线中角度最小的一个一定是极边。 很显然,leftest-and-lowest的点一定是极点。

我们来看这样的一段可执行代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function Jarvis(S:Array<Point>){
let n = S.length;
for(let i=0;i<n;i++)
S[i].extreme = false;
let ltl:number = LTL(S);
let k = ltl;
do{
S[k].extreme = true;
let s = -1;
for(let t=0;t<n;t++){
if(t != k &&
(s == -1 || !ToLeftTest(S[k],S[s],S[t]))
)
s = t;
}
S[k].succ = s;
k = s;
}while(ltl != k)
}

凸包问题的优化算法 (leetcode)连续整数求和-题解

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×