凸包
wangyicheng · · 个人记录
1. 凸包（Convex Hull）是一个计算几何（图形学）中的概念。
在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所点(X1，...Xn)的凸组合来构造.
简单来说，就是平面中给定n个点，求出这n个点最大围成面积的图形
解决凸包的方法有很多（数学大佬不断扩展得到的） 这里介绍基础和实用的两种
2.斜率逼近法
这是一种简单易懂的方法
(1)首先在所有点中找出一个y值最小的点，记为P1
(2)从P1 出发，刚开始k=0，即为水平状态。然后按照上图的示意沿逆时针方向寻找。即开始在k>0k>0且(x_2>x1,y_2>y_1)中找k最小的点P2 ，以此类推。
Q:如果过程中有多个点符合要求怎么办？
A:那么就取距离P1 最远的点，因为这样能保证划定的范围最大。
（3）P2出发，用（2）的方法找P3
(4)最后直到Pm=P1 （已形成凸包）。
Q:为什么要刚开始找y值最小的点？
A:易证y值最小的点一定在凸包上。
时间复杂度：O(nm）
n为点的数量 m为在凸包上点的数量
由此可知 当n个点恰好构成一个凸包时 时间复杂度为O（n2） 且实现的代码复杂度较高 不为常用
3.Graham算法
既然那么麻烦，那么各位数学大佬和noi选手们肯定不能忍，于是出现了Graham算法。
Graham算法不在加入一个点后进行排序
而是在开始将n个点排序
同样选择y最小的点，若y相等，便选择x小的作为第一个点，记作p1.再将剩余点按照极角大小逆时针排序p2-pn（是不是跟上一个算法有点类似）
然后从p1依次扫描p2-pn看是否满足凸包形成条件