凸包凸包（ConvexHull）是计算几何（图形学）中的一个概念。点集Q的凸包是指一个最小凸多边形，它满足Q中点在多边形边上或在多边形内。在正式讨论凸包问题之前，这里先介绍一个辅助概念——“方向”。有序点的方向平面中有序点的方向可以有三种：counterclockwiseCounterClockwiseclockwiseClockwisecollinearColinear对于点\(a(x_1,y_1)\),\(a(x_2,y_2)\),$c(x_3,y_3)$,线段ab的斜率为$$\sigma=\frac{y_2-y_1}{x_2-x_1}$$线段bc的斜率为$$\tau=\frac{y_3-y_2}{x_3-x_2}$$If\(sigma<\tau\),方向为逆时针（左转）If\(sigma=\tau\),方向共线If\(sigma>\tau\),方向为顺时针（右转）因此三个有序点的方向取决于表达式（常用分）$$(y_2-y_1)\times(x_3-x_2)-(y_3-y_2)\times(x_2-x_1)$$如果表达式为负数，则方向为逆时针。如果表达式为0，则方向共线。如果表达式为正，则方向为顺时针。格雷厄姆扫描算法可以分为两个主要部分：预处理找到左下角的点。使点p0成为输出凸包points[0]的第一个元素。将剩余的n-1个点按照极角与p0的顺序排序。如果角度相同，只保留距离p0最远的点接受或拒绝该点创建一个空栈S，将[栈顶的下一个点，栈顶的点]为推入堆栈。处理每个剩余的points[i]：跟踪当前的三个点：栈顶旁边的点，栈顶的点，以及当前分析的点points[i]。三点之间有两条连线，看成是两个向量，计算它们之间的叉积，返回三点关系：<0，表示第三点向左转，则保留第二点(栈顶元素)，将第三个点入栈\>0，说明第三个点是右转，然后删除第二个点(栈顶元素)，再将第三个点入栈stack=0，说明三个点共线（可以用>0的处理方法）算法的第1.1步（找左下角点）耗时O(n)，第1.2步（点排序）耗时O(n*登录））时间。第二步，每个元素最多被压入和弹出一次。假设入栈操作耗时O(1)，则第二步一共耗时O(n)。所以整体的时间复杂度是O(n*logn)。代码importrandomimportmatplotlib.pyplotaspltimportmatplotlib.animationasanimationimportmath#在（开始，结束）区间内，随机生成一个点集，有n个点（return:list[(x1,y1)...(xn,yn)])defsample(n,start=0,end=101):returnlist(zip([random.randint(start,end)for_inrange(n)],[random.randint(start,end)for_inrange(n)]))'''#计算两个向量之间的叉积。返回三个点的关系：<0，表示第三个点是左转，然后保留第二个点（栈顶元素），再添加第三个点>0，表示第三个点是向右转，删除第二个点（栈顶元素），然后加上第三个点=0，表示三点共线'''defccw(a,b,c):return((b[1]-a[1])*(c[0]-b[0]))-((c[1]-b[1])*(b[0]-a[0]))#计算后面的n-1点的斜率和起始点借助sorteddefcompute(next)从小到大排序:start=points[0]#firstpoint#按极序排列，但是现在输入坐标点为笛卡尔坐标点。不适合这个#angle=math.atan2(start[2]-next[2],start[1]-next[1])#returnangle#斜率排序的方法ifstart[0]==next[0]:#如果x坐标相同，则计算斜率时分母为0，直接返回斜率return99999slope=(start[1]-next[1])/(start[0]-next[0])returnslopedefGraham_Scan(points):##找到最左边和底部的点作为起点，与第一个Min=9999交换foriinrange(len(points)):#找到最左边的点ifpoints[i][0]
