Graham扫描算法 ： 大体思路是将不是凸包顶点的点从点集中去掉。



找出S中具有最小y坐标的点p（通过选取最左边的点打破平局）



根据点和p的连线 与 x轴正方向所成的角度，对S中的点进行排序（由小到大），并将p放在最前面。



从p点开始扫描排序后的S集合。如果这些点都在凸包上，则每三个相继的点p1,p2,p3满足以下性质：p3在向量<p1,p2>的左边.如果出现相继的三个点p1,p2,p3不满足上述性质，则p2点一定不是凸包的顶点，应立即去除。-Graham scan algorithm: the general idea is not a convex hull vertex points from a point focus on remove.



Identify S with the minimum y coordinate of the point p (select the left-most point to break a tie)



According to the connection point and p x-axis positive direction into the angle, sort the points in S (small to large), and p up front.



Scan sorted S-collection from p. These points on the convex hull of every three successive points p1, p2, p3, meet the following properties: p3, in vector <p1,p2> the left side if the successive three points p1 is p2, p3 does not meet the the above properties, then p2 is definitely not the vertex of the convex hull should be immediately removed.