第pythonGraham求凸包問題并畫圖操作pythonGraham求凸包并畫圖

python寫Graham沒有c++那么好寫，但是python畫圖簡單。只需要用matplotlib里的pyplot，c++畫圖太難了。

Graham算法寫起來比較簡單，只需要想辦法對最小點和其他的點所連成的直線，與x軸正半軸的夾角進行排序，然后其他的就直接套用Graham算法模板就好了，因為c++可以重載排序函數(shù)sort，不用計算角度（用其他的數(shù)學(xué)方法），但是python不行（也許是我不知道而已，菜）。

python必須要在結(jié)構(gòu)體里面加上角度這個變量，然后才能按照角度排序。排好序后就變得容易了，用stack棧存放答案，算完答案后，用scatter（散點圖）畫出點，用plt（折線圖）畫邊界就好了。

importmatplotlib.pyplotasplt

importmath

importnumpyasnp

classNode:

def__init__(self):

self.x=0

self.y=0

self.angel=0

#和最左下的點連成的直線，與x軸正半軸的夾角大小

#按照角度從小到大排序

defcmp(x):

returnx.angel

defbottom_point(points):

min_index=0

n=len(points)

#先判斷y坐標，找出y坐標最小的點，x坐標最小的點

foriinrange(1,n):

ifpoints[i].ypoints[min_index].yor(points[i].y==points[min_index].yand

points[i].xpoints[min_index].x):

min_index=i

returnmin_index

#計算角度

defcalc_angel(vec):

norm=math.sqrt(vec[0]*vec[0]+vec[1]*vec[1])

ifnorm==0:

return0

angel=math.acos(vec[0]/norm)

ifvec[1]=0:

returnangel

else:

returnmath.pi*2-angel

defmulti(v1,v2):

returnv1[0]*v2[1]-v1[1]*v2[0]

point=[]

n=30

#生成30個點的坐標，n可以修改

foriinrange(n):

temp=Node()

temp.x=np.random.randint(1,100)

temp.y=np.random.randint(1,100)

point.append(temp)

index=bottom_point(point)

foriinrange(n):

ifi==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循環(huán)更新答案

foriinrange(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]

#一定要大于等于零，因為可能在一條直線上

whilemulti(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])

#畫出圖像

forpinpoint:

plt.scatter(p.x,p.y,marker='o',c='g')

L=len(stack)

foriinrange(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找到凸包Convexhulls

圖形學(xué)可以說經(jīng)常遇到這東西了，這里給出一個庫函數(shù)的實現(xiàn)

fromscipy.spatialimportConvexHull

points=np.random.rand(10,2)#30randompointsin2-D

hull=ConvexHull(points)

importmatplotlib.pyplotasplt

plt.plot(points[:,0],points[:,1