大法真香
卷包裹算法
可以说是一个很朴素的算法,其时间复杂度最坏情况为O(n^2),其实现原理非常简单。就像是拿了一根绳子,以最左下方的点开始,围着所有点的外围围了一圈。
先找到横坐标最小的点中纵坐标最小的点,然后以该点作为基准点,对剩余的所有点找到相对当前点的最外侧的点,然后再次以该点作为当前点继续重复直到形成完整的凸包为止。
如何寻找最外侧的点?利用二维向量的叉积公式<x1,y1>*<x2,y2>=x1*y2-x2*y1,向量A乘以向量B 如果为正则为A逆时针旋转向B 否则为顺时针。如下图所示,向量JK和JI的叉积为负数,因此JI在外侧。这样得到的凸包是按照逆时针方向排序的。H代表凸包上点的数目,这样时间复杂度为O(HN)。