首页 > 代码库 > 凸包-Graham扫描法
凸包-Graham扫描法
RT,Graham扫描法求凸包分为3步:
1.找到y最小的点
2.以y最小的点O为原点,求其余所有点相对O的极角并按极角从小到大排序
3.对于排序后的点集,配合栈,完成Graham扫描。
ConvexHull.py
#coding=utf-8 import math import numpy import pylab as pl #画原始图 def drawGraph(x,y): pl.title("The Convex Hull") pl.xlabel("x axis") pl.ylabel("y axis") pl.plot(x,y,'ro') #画凸包 def drawCH(x,y): #pl.plot(x,y1,label='DP',linewidth=4,color='red') pl.plot(x,y,color='blue',linewidth=2) pl.plot(x[-1],y[-1],x[0],y[0]) lastx=[x[-1],x[0]] lasty=[y[-1],y[0]] pl.plot(lastx,lasty,color='blue',linewidth=2) #存点的矩阵,每行一个点,列0->x坐标,列1->y坐标,列2->代表极角 def matrix(rows,cols): cols=3 mat = [[0 for col in range (cols)] for row in range(rows)] return mat #返回叉积 def crossMut(stack,p3): p2=stack[-1] p1=stack[-2] vx,vy=(p2[0]-p1[0],p2[1]-p1[1]) wx,wy=(p3[0]-p1[0],p3[1]-p1[1]) return (vx*wy-vy*wx) #Graham扫描法O(nlogn),mat是经过极角排序的点集 def GrahamScan(mat): #print mat points=len(mat) #点数 """ for k in range(points): print mat[k][0],mat[k][1],mat[k][2] """ stack=[] stack.append((mat[0][0],mat[0][1])) #push p0 stack.append((mat[1][0],mat[1][1])) #push p1 stack.append((mat[2][0],mat[2][1])) #push p2 for i in range(3,points): #print stack p3=(mat[i][0],mat[i][1]) while crossMut(stack,p3)<0:stack.pop() stack.append(p3) return stack #main max_num = 30 #最大点数 x=100*numpy.random.random(max_num)#[0,100) y=100*numpy.random.random(max_num) drawGraph(x,y) mat = matrix(max_num,3) #最多能存50个点 minn = 300 for i in range(max_num): #存点集 mat[i][0],mat[i][1]=x[i],y[i] if y[i]<minn: #(x[tmp],y[tmp])-->y轴最低坐标 minn=y[i] tmp = i d = {} #利用字典的排序 for i in range(max_num): #计算极角 if (mat[i][0],mat[i][1])==(x[tmp],y[tmp]):mat[i][2]=0 else:mat[i][2]=math.atan2((mat[i][1]-y[tmp]),(mat[i][0]-x[tmp])) d[(mat[i][0],mat[i][1])]=mat[i][2] lst=sorted(d.items(),key=lambda e:e[1]) #按极角由小到大排序 for i in range(max_num): #装排序后的矩阵 ((x,y),eth0)=lst[i] mat[i][0],mat[i][1],mat[i][2]=x,y,eth0 stack=GrahamScan(mat) x,y=[],[] for z in stack: x.append(z[0]) y.append(z[1]) drawCH(x,y) pl.show()ps: Graham的复杂度为O(nlogn)
求平面最远的点对可转化为先求凸包+旋转卡壳(可以证明,平面上最远的点对一定都在凸包上。)
凸包-Graham扫描法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。