平面点集的凸包可理解为包含所有点的最小凸多边形（点可以在多边形边上或在其内）。这里给出一种求解方法。
先找所有点中 y 坐标最大最小的点Pmax、Pmin，所找点必定是凸包上的点；
找距离直线PmaxPmin两侧最远的点P1,P0，构成初始三角形
, 
；
再对每个三角形新生成的边（
、
和
、
）继续找与改变对应顶点（
）不在同一侧的最远点。
|
1 找所有点中 y 坐标最大和最小的点 1.1 若找到的点少于两个,return,输出（无凸包结构） 1.2 若y坐标最大最小点各只有一个记为Pmax,Pmin,找直线PmaxPmin两侧最远的点P1,P0,将构成的三角形 1.3 若找到的点大于两个,把这些点能组成的三角形放入堆栈TriStack 2 若TriStack不为空 2.1 三角形出栈，找三角形前两个顶点的对边与该点异侧的最远点 2.2 若点存在,边与点组成三角形放入TriStack 2.3 若点不存在,该边存入Boundary,返回2 3 返回 Boundary |
原文：https://www.cnblogs.com/cy0628/p/13953729.html
