python Graham求凸包问题并画图操作

 import matplotlib.pyplot as plt import math import numpy as np class Node: def __init__(self): self.x = 0 self.y = 0 self.angel = 0 #和最左下的点连成的直线，与x轴正半轴的夹角大小 #按照角度从小到大排序 def cmp(x): return x.angel def bottom_point(points): min_index = 0 n = len(points) #先判断y坐标，找出y坐标最小的点，x坐标最小的点 for i in range(1, n): if points[i].y = 0: return angel else: return math.pi * 2 - angel def multi(v1, v2): return v1[0] * v2[1] - v1[1] * v2[0] point = [] n = 30 #生成30个点的坐标，n可以修改 for i in range(n): temp = Node() temp.x = np.random.randint(1, 100) temp.y = np.random.randint(1, 100) point.append(temp) index = bottom_point(point) for i in range(n): if i == index: continue #计算每个点和point[index]所连成的直线与x轴正半轴的夹角 vector = [point[i].x - point[index].x, point[i].y - point[index].y] #vector是向量 point[i].angel = calc_angel(vector) #排序 point.sort(key=cmp) #答案存入栈中 stack = [] stack.append(point[0]) stack.append(point[1]) #for循环更新答案 for i in range(2, n): L = len(stack) top = stack[L - 1] next_top = stack[L - 2] vec1 = [point[i].x - next_top.x, point[i].y - next_top.y] vec2 = [top.x - next_top.x, top.y - next_top.y] #一定要大于等于零，因为可能在一条直线上 while multi(vec1, vec2) >= 0: stack.pop() L = len(stack) top = stack[L - 1] next_top = stack[L - 2] vec1 = [point[i].x - next_top.x, point[i].y - next_top.y] vec2 = [top.x - next_top.x, top.y - next_top.y] stack.append(point[i]) #画出图像 for p in point: plt.scatter(p.x, p.y, marker='o', c='g') L = len(stack) for i in range(L-1): plt.plot([stack[i].x, stack[i+1].x], [stack[i].y, stack[i+1].y], c='r') plt.plot([stack[0].x, stack[L-1].x], [stack[0].y, stack[L-1].y], c='r') plt.show()

 from scipy.spatial import ConvexHull points = np.random.rand(10, 2) # 30 random points in 2-D hull = ConvexHull(points) import matplotlib.pyplot as plt plt.plot(points[:,0], points[:,1], 'o') for simplex in hull.simplices: plt.plot(points[simplex,0], points[simplex,1], 'k-') plt.show()