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 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 < 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 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()
|
以上为个人经验,希望能给大家一个参考,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/qq_43552826/article/details/104632831