python Graham求凸包并画图
python写Graham没有c++那么好写，但是python画图简单。只需要用matplotlib里的pyplot，c++画图太难了。
Graham算法写起来比较简单，只需要想办法对最小点和其他的点所连成的直线，与x轴正半轴的夹角进行排序，然后其他的就直接套用Graham算法模板就好了，因为c++可以重载排序函数sort，不用计算角度（用其他的数学方法），但是python不行（也许是我不知道而已，菜）。
python必须要在结构体里面加上角度这个变量，然后才能按照角度排序。排好序后就变得容易了，用stack栈存放答案，算完答案后，用scatter（散点图）画出点，用plt（折线图）画边界就好了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
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() |
Python 找到凸包 Convex hulls
图形学可以说经常遇到这东西了，这里给出一个库函数的实现
|
1
2
3
4
5
6
7
8
|
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() |
以上为个人经验，希望能给大家一个参考，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/qq_43552826/article/details/104632831
