自学教程：python Graham求凸包问题并画图操作

import matplotlib.pyplot as pltimport mathimport 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 < points[min_index].y or (points[i].y == points[min_index].y and           points[i].x < points[min_index].x):            min_index = i    return min_index  #计算角度def calc_angel(vec):    norm = math.sqrt(vec[0] * vec[0] + vec[1] * vec[1])    if norm == 0:        return 0    angel = math.acos(vec[0]/norm)    if vec[1] >= 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 ConvexHullpoints = np.random.rand(10, 2) # 30 random points in 2-Dhull = ConvexHull(points)import matplotlib.pyplot as pltplt.plot(points[:,0], points[:,1], 'o')for simplex in hull.simplices: plt.plot(points[simplex,0], points[simplex,1], 'k-')plt.show()