凸包的学习之路

学习视频选择的是：清华大学邓俊辉教授的《计算几何》课程

关于我为什么学习凸包（Convex Hull）？

——在学习过程中遇到了凸包问题，凸包在CV领域的基础性，使我觉得深入了解凸包是必要的。此外，我发现了《计算几何》这一宝藏课程，对我目前涉足的领域犹如前进的灯塔。而凸包又正是《计算几何》的第一课。

菜鸡还是很菜，但进步空间大呀。

什么是凸包？（如果面试官问你这一问题，你该如何作答）

二维平面上有一个点集，点集中有若干个点，就好像将一些钉子钉在桌子上，现在手里有一个橡皮筋，用手拿着，将它套在这些钉子的外面。然后，松手，橡皮筋就会套在“最外面”的那些钉子上，会呈现出一个轮廓，这个轮廓构成的形状，就是凸包。

凸的概念，是几何中常见的概念。如何判定“凸”？如果轮廓内任意两点的连线都在轮廓区域内，那么这个形状就是凸的。

下面，要记录的几种【由平面中一组点集，生成凸包】的算法

在此之前，两个概念——极点（相当于“边界点”）、极边（相当于“边界”）

1.算法策略1： In-Triangle Test

原理：非极点一定在某一或某些三角形的内部，而极点不在任一三角形内部。

思路：（1）先将所有点都标记为极点；（2）对于每一个三角形（p,q,r），如果点s位于其内部，则将s标记为非极点。

四层循环：

for(int p=0;p<n;p++)

        for(int q=p+1;q<n;q++)

                for(int r=q+1;r<n;r++)

                        for(int s=0;s<n;s++){

                                if(s==p || s==q || s==r || !S[s].extreme ) continue;

                                if(Intriangle(S[p],S[q],S[r],S[s]) S[s].extreme = false;

                                }

下面的重点是：

InTriange()这个函数的实现，我首先想到的是向量的叉乘（多学一点是一点，总是没错的）。这里给出的是点的坐标，可将其转化为三个ToleftTest。沿三角形CW方向或者CCW方向，三角形内的点对于三条边的ToleftTest都会返回同一个值（同是ture,或者同是flase,视方向而定）。ToleftTest在后续其他凸包算法中也有着广泛的应用。

OK，在学习了算法思想后，有种手痒的感觉，于是乎在Code::Blocks中实现了一下。

实现效果如下：

我使用了opencv将点绘制了一下，其中，红色点为极点，黄色点为非极点。

2.算法策略2：Extreme Edges

第一个算法根据极点的特性（不在点集中任三点构成的三角形中）来识别极点和非极点，下面这个算法策略则从极边入手。非极点与非极点之间肯定不存在极边，极点与非极点之间也肯定不存在极边，此外，极点与极点之间也不一定存在极边。那极边的特性是，除了构成该极边的两个极点之外，剩下所有的点都在该极边的一边。

amazing

思路：（1）定义极边EE为空集；（2）对于点集中任两点(p,q)构成的边，判断其他点是否都在该边的同一侧。如果是，那么将p,q标记为极点，将pq加入极边中。

解释一下这边具体的思路：对于p,q构成的边，先定义布尔类型LEmpty和REmpty为true，对其他点进行ToleftTest。如果pq是极边，那么其他点k会将LEmpty或者REmpty中的一个赋值为flase，另一个还是true。但如果pq不是极边，那么LEmpty和REmpty都会被重新赋值为flase，那么下面那个if(LEmpty || REmpty)不会执行。

实现效果如下：

还是用opencv绘制，这里不仅绘制了点，把极边也绘制上去了。

3. 算法策略3：decrease and conquer（减治法：减少、征服）

插入法排序：

5 1 4 2 3

（5） 1 4 2 3

（1 5） 4 2 3

（1 4 5 ）2 3

（1 2 4 5 ）3

（1 2 3 4 5）

策略：“减而治之，逐步蚕食”

这里凸包的构建也可以采取这一策略。先是任取三个点构成三角形作为凸包，然后从点集中取点，判断该点是否在多边形的内部/外部？如果是外部点，那就要思考插入的位置了。就这样，逐渐将剩下的点加入，最终构建好凸包。

思路：设置两个指针结构，一个就是指向点集，另一个指向极点集合（在不断变化中）。对于扫描到的点，依次连接它与极点集合的点（循环），判断其前驱和后继是否在一边，还是使用ToleftTest。如果是在一边（同为true或者同为flase)，则要记录一下位置，方便后续插入；如果不在一边，就continue再判断下一个；要是都不在一边，那说明这是个内部点了。

实现效果如下：

4.算法策略4： Jarcis March算法

凸包是首尾相连的凸多边形。根据这一特性，如果我们找到了一条极边（ki)，那么就可以从这条极边出发缩小下一步查找极边的范围。如果是逆时针转的话，下一个极边从极点k出发，对其他点 l 进行搜索，如果新的 l 在kl的右侧，则更新极点。

那么如何确定最初的那个极点呢，这里采用Lowest-then-Leftmost策略，实际上是两条准则，先找最低的点（也就是y值最小的点），如果存在多个y值相同的点，那么在找那个最左的点（也就是x值最小的点）。其实这样找到的点是符合要求的，我主要是从直观感觉上来。找到这个点 ltl,下面再从它出发来寻找极边。就可以了。