平面点集的凸包问题

平面点集的凸包可理解为包含所有点的最小凸多边形（点可以在多边形边上或在其内）。这里给出一种求解方法。

一、基本思路

先找所有点中 y 坐标最大最小的点P_max、P_min，所找点必定是凸包上的点；

找距离直线P_maxP_min两侧最远的点P₁,P₀，构成初始三角形, ；

再对每个三角形新生成的边（、和、）继续找与改变对应顶点（）不在同一侧的最远点。

二、算法流程

1 找所有点中 y 坐标最大和最小的点

     1.1 若找到的点少于两个,return,输出（无凸包结构）

     1.2 若y坐标最大最小点各只有一个记为Pmax,Pmin,找直线PmaxPmin两侧最远的点P₁,P₀,将构成的三角形, 放入堆栈TriStack

     1.3 若找到的点大于两个,把这些点能组成的三角形放入堆栈TriStack

2 若TriStack不为空

     2.1 三角形出栈，找三角形前两个顶点的对边与该点异侧的最远点

     2.2 若点存在,边与点组成三角形放入TriStack

     2.3 若点不存在,该边存入Boundary,返回2

3 返回 Boundary

 参考：https://www.cnblogs.com/nobodyzhou/p/5243929.html