凸包
凸包（Convex Hull）是一个计算几何（图形学）中的概念。点集Q的凸包是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。
正式探讨凸包问题之前，这里先引入一个辅助概念——“方向”。
有序点的方向
一个立体内有序点的方向（Orientation）能够有三种：
- 逆时针 CounterClockwise
- 顺时针 Clockwise
共线 Colinear
对于点 \(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}$$
- 若\(sigma < \tau\)，方向是逆时针（向左转）
- 若\(sigma = \tau\)，方向是共线
- 若\(sigma > \tau\)，方向是顺时针（向右转）
因而，三个有序点的方向依赖于表达式（通分失去）
$$(y_2 - y_1) \times (x_3 - x_2) - (y_3 - y_2) \times (x_2 - x_1)$$
- 若表达式为负，方向是逆时针
- 若表达式为0，方向是共线
- 若表达式为正，方向是顺时针
Graham Scan
算法能够分为两个次要局部：
预处理
- 找到最左下方的点。使该点 p0 作为输入凸包的第一个元素 points[0]。
- 将剩下的 n - 1 个点依照与p0的极角序排序，若有角度雷同，仅保留间隔 p0 最远的那个点
承受或回绝点
- 创立空栈 S，将 【栈顶的下一个点、位于栈顶的点 】 入栈。
- 解决残余的每个 points[i]：
追踪以后的三个点：栈顶的下一个点、位于栈顶的点，以后剖析的点points[i]。三点之间有两条连线，看作是两个向量，计算他们之间的叉积，返回三点之间的关系：
<0，阐明第三个点是向左转，则保留第二个点（栈顶元素），将第三个点进栈
\>0，阐明第三个点是向右转，则删除第二个点（栈顶元素），再将第三个点进栈
=0，阐明三点共线（可采纳>0的解决形式）
算法的第 1.1 步（找到最左下方的点）花 O(n) 工夫，第 1.2 步（点的排序）花 O(n * logn) 工夫。
第 2 个步骤中，每个元素入栈和出栈最多一次，假如栈操作 O(1) 工夫，则第 2 步总共花 O(n) 工夫。因而总体的工夫复杂度是 O(n * logn)。
代码
import randomimport matplotlib.pyplot as pltimport matplotlib.animation as animationimport math# 在（start,end)区间内，随机生成具备 n 个点的点集（return: list [(x1,y1)...(xn,yn)]）def sample(n, start=0, end=101): return list(zip([random.randint(start, end) for _ in range(n)], [random.randint(start, end) for _ in range(n)])) '''# 计算两个向量之间的叉积。返回三点之间的关系：<0，阐明第三个点是向左转，则保留第二个点（栈顶元素）,再退出第三个点>0，阐明第三个点是向右转，则删除第二个点（栈顶元素）,再退出第三个点=0，阐明三点共线''' def ccw(a, b, c): return ((b[1] - a[1]) * (c[0] - b[0])) - ((c[1] - b[1]) * (b[0] - a[0]) )# 别离求出前面n-1个点与出发点的斜率，借助sorted实现从小到大排序def compute(next): start = points[0] # 第一个点 # 按极角序排列的办法，但当初输出的坐标点是笛卡尔坐标点。不适宜用这个 # angle = math.atan2( start[2] - next[2], start[1] - next[1] ) # return angle # 按斜率排列的办法 if start[0] == next[0]: # 如果x坐标雷同，那么求斜率时会呈现分母为0的状况,间接返回斜率无穷大 return 99999 slope = (start[1] - next[1]) / (start[0] - next[0]) return slopedef Graham_Scan(points): # # 找到最右边且最上面的点作为出发点，和第一位调换 Min=9999 for i in range(len(points)): # 寻找最右边的点 if points[i][0]<Min: Min = points[i][0] index = i # 如果同在最右边，可取y值更小的 elif points[i][0]==Min: if points[i][1]<=points[index][1]: Min = points[i][0] index = i # 和第一位调换地位 temp = points[0] points[0] = points[index] points[index] = temp # 排序：从第二个元素开始，按与第一个元素的斜率排序 points = points[:1] + sorted(points[1:], key=compute) # 前半部分是出发点 ； 后半局部是通过按斜率排序之后的n-1个坐标点 留神： “+”是拼接的含意，不是数值相加 # 用列表模仿一个栈。（最先退出的是前两个点，前两次while必然不成立，从而将点加进去） convex_hull = [] for p in points: ''' # 如果能顺时针方向（右转）连贯第三个顶点，就删除栈顶元素再退出这个顶点 ； 否则（向左转才达到第三个顶点），间接退出这个顶点 convex_hull[-2]：栈顶元素上面的元素 convex_hull[-1]：栈顶元素 p：要剖析的第三个顶点 ''' while len(convex_hull) > 1 and ccw(convex_hull[-2], convex_hull[-1], p) >= 0: convex_hull.pop() convex_hull.append(p) return convex_hulldef show_result(points, results): """ 画图 :param points: 所有点集 :param results: 所有边集 :return: picture """ all_x = [] all_y = [] for item in points: a, b = item all_x.append(a) all_y.append(b) for i in range(len(results)-1): item_1=results[i] item_2 = results[i+1] # 横坐标,纵坐标 one_, oneI = item_1 two_, twoI = item_2 plt.plot([one_, two_], [oneI, twoI]) plt.scatter(all_x, all_y) plt.show()if __name__ == '__main__': # points = [(101, 47), (32, 40), (21, 90), (65, 100), (98, 64), (81, 43), (51, 20), (75, 82), (90, 34), (38, 101)] points = sample(100) hull = Graham_Scan(points) print(hull) # 可视化，有利于查看后果的正确性 hull.append(hull[0]) # 把最初一个点和源点连起来，绘制成闭合连线（仅在画图时这样解决） show_result(points, hull) 程序运行后果
连接点的程序：
[(2, 5), (21, 0), (91, 1), (101, 9), (99, 62), (91, 88), (75, 101), (27, 98), (12, 96), (2, 92), (2, 53)]可视化：
https://ysw1912.github.io/pos...
https://en.wikipedia.org/wiki...