第四课 二维点集的凸包

特征描述：

应用：

类似于游戏的命中判定、碰撞箱。

题目的标准定义

如何提高效率：
1、已经判断出不可能是极点的的应不再参与循环。
2、序号123的点、231的点、312的点都会作为三角形参与判断，这是冗余的



1、找最下面最右面的点
2、以各个线段与最低点水平线的夹角排序并依次处理。
3、让前两个点进站。
4、如果下一个点a在栈中最后两个点的左侧，让它进站。
5、如果下一个点a在栈中最后两个点的右侧，让栈中最后一个点出站。仍然是对点a进行判断，反复进行（5）直到出现（4）的情况。
6、循环至程序结束
说明：
1、nlogn的复杂度出自排序部分
2、利用栈判断的部分复杂度为n，因为每个点只可能进出栈1次。


已经排好的数据用冒泡排序最快。
实际工程中有很多东西不是唯一的，要根据工程需要、工程情况决定。