Python求凸包的函数 python凸包检测
2021-02-16 Python OpenCV convexHull()函数
此函数利用Sklansky's算法在一个二维点集中找到凸包。时间复杂度为 。
网站的建设创新互联专注网站定制,经验丰富,不做模板,主营网站定制开发.小程序定制开发,H5页面制作!给你焕然一新的设计体验!已为小搅拌车等企业提供专业服务。
其中,points和hull应该为不同的数组,该函数不支持原地处理。
OpenCV-Python系列八:提取图像轮廓
当你完成图像分割之后,图像轮廓检测往往可以进一步筛选你要的目标,OpenCV中可以使用cv2.findContours来得到轮廓。
补充 :
再不少场景中,找轮廓的最小外接矩形是基本需求,opencv中minAreaRect得到的是一个带有旋转角度信息的rect,可以使用cv2.boxPoints(rect)来将其转为矩形的四个顶点坐标(浮点类型).你也可以使用cv2.polylines来绘制这样的轮廓信息
注意findContours参数的变化,在opencv4中,返回值只有contours和hierarchy ,这一点与opencv3中不同。对与轮廓的层级结构,比较难用,虽然可以通过轮廓的层级结构来进行索引你需要的轮廓,不过对于大部分机器视觉应用场景,二值化的结果有时候很难预料,单单通过这种层级关系索引,非常容易出错。所以,只找最外部结构的 cv2.RETR_EXTERNAL 是不是真香呢?
处理cv2.approxPolyDP()外,你也可以使用cv2.convexHull来求轮廓的近似凸包,其中凸形状内部--任意两点连线都在该形状内部。
clockwise :默认为False,即轮廓为逆时针方向进行排列;
returnPoints :设置为False会返回与凸包上对应的轮廓的点索引值,设置为True,则会返回凸包上的点坐标集,默认为True
对于opencv-python的提取图像轮廓部分有问题欢迎留言, Have Fun With OpenCV-Python, 下期见。
凸包的平面求法
这个算法是由数学大师葛立恒(Graham)发明的,他曾经是美国数学学会(AMS)主席、ATT首席科学家以及国际杂技师协会(IJA)主席。
问题
给定平面上的二维点集,求解其凸包。
过程
⒈ 在所有点中选取y坐标最小的一点H,当作基点。如果存在多个点的y坐标都为最小值,则选取x坐标最小的一点。坐标相同的点应排除。然后按照其它各点p和基点构成的向量H,p;与x轴的夹角进行排序,夹角由大至小进行顺时针扫描,反之则进行逆时针扫描。实现中无需求得夹角,只需根据余弦定理求出向量夹角的余弦值即可。以下图为例,基点为H,根据夹角由小至大排序后依次为H,K,C,D,L,F,G,E,I,B,A,J。下面进行逆时针扫描。
⒉ 线段H,K;一定在凸包上,接着加入C。假设线段K,C;也在凸包上,因为就H,K,C三点而言,它们的凸包就是由此三点所组成。但是接下来加入D时会发现,线段K,D;才会在凸包上,所以将线段K,C;排除,C点不可能是凸包。
⒊ 即当加入一点时,必须考虑到前面的线段是否会出现在凸包上。从基点开始,凸包上每条相临的线段的旋转方向应该一致,并与扫描的方向相反。如果发现新加的点使得新线段与上线段的旋转方向发生变化,则可判定上一点必然不在凸包上。实现时可用向量叉积进行判断,设新加入的点为pn + 1,上一点为pn,再上一点为pn - 1。顺时针扫描时,如果向量pn - 1,pn;与pn,pn + 1;的叉积为正(逆时针扫描判断是否为负),则将上一点删除。删除过程需要回溯,将之前所有叉积符号相反的点都删除,然后将新点加入凸包。
在上图中,加入K点时,由于线段H,C要旋转到H,K的角度,为顺时针旋转,所以C点不在凸包上,应该删除,保留K点。接着加入D点,由于线段K,D要旋转到H,K的角度,为逆时针旋转,故D点保留。按照上述步骤进行扫描,直到点集中所有的点都遍历完成,即得到凸包。
复杂度
这个算法可以直接在原数据上进行运算,因此空间复杂度为O⑴。但如果将凸包的结果存储到另一数组中,则可能在代码级别进行优化。由于在扫描凸包前要进行排序,因此时间复杂度至少为快速排序的O(nlgn)。后面的扫描过程复杂度为O(n),因此整个算法的复杂度为O(nlgn)。 对于一个有三个或以上点的点集Q,过程如下:
计算点集最右边的点为凸包的顶点的起点,如上图的P3点。
Do
For i = 0 To 总顶点数
计算有向向量P3-Pi
If 其余顶点全部在有向向量P3-Pi的左侧或右侧,则Pi点为凸包的下一顶点
Pi点加入凸包列表
GoTo 1
End If
Next
Exit Do
1:
Loop
此过程执行后,点按极角自动顺时针或逆时针排序,只需要按任意两点的次序就可以了。而左侧或右侧的判断可以用前述的矢量点积性质实现。 const pi=3.1415926575; zero=1e-6; maxn=1000; maxnum=100000000;var ans,temp:extended; n,tot:longint; x,y:array[0..maxn] of extended; zz,num:array[0..maxn]of longint;procedure swap(var ii,jj:extended); var t:extended; begin t:=ii;ii:=jj;jj:=t; end;procedure init;var i,j:longint; begin readln(n); for i:=1 to n do readln(x[i],y[i]); end;function ok(x,midx,y,midy:extended):longint;beginif abs(x-midx)=zero then begin if abs(midy-y)=zero then exit(0); if midyy then exit(1) else exit(2); endelse begin if xmidx then exit(1) else exit (2); end;end;procedure qsort(head,tail:longint);var i,j:longint; midx,midy:extended; begin i:=head; j:=tail; midx:=x[(head+tail)div 2]; midy:=y[(head+tail)div 2]; repeat while ok(x[i],midx,y[i],midy)=1 do inc(i); while ok(x[j],midx,y[j],midy)=2 do dec(j); if i=j then begin swap(x[i],x[j]); swap(y[i],y[j]); inc(i); dec(j); end; until ij; if itail then qsort(i,tail); if jhead then qsort(head,j);end;function Plot(x1,y1,x2,y2:extended):extended; begin Plot:=x1*y2-x2*y1; end;function check(first,last,new:longint):boolean;varax,ay,bx,by:extended;Pt:extended;begin ax:=x[last]-x[first];ay:=y[last]-y[first]; bx:=x[new]-x[first];by:=y[new]-y[first]; if Plot(ax,ay,bx,by)=0 then exit(true) else exit(false);end;procedure Tbao;vari,j,tail:longint;begin tot:=0; zz[1]:=1;tail:=1; for i:=2 to n do begin while(zz[tail]1)and check(zz[tail-1],zz[tail],i) do dec(tail); inc(tail); zz[tail]:=i; end; inc(tot,tail-1); for i:=1 to tail-1 do num[i]:=zz[i]; zz[1]:=n;tail:=1; for i:=n-1 downto 1 do begin while (zz[tail]n) and check(zz[tail-1],zz[tail],i) do dec(tail); inc(tail); zz[tail]:=i; end; for i:=1 to tail-1 do num[tot+i]:=zz[i]; inc(tot,tail-1);end;function dist(a,b:longint):extended; begin dist:=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])); end; procedure main; var i,j:longint; begin qsort(1,n); Tbao; ans:=0; for i:=1 to tot-1 do ans:=ans+dist(num[i],num[i+1]); ans:=ans+dist(num[tot],num[1]); ans:=ans+temp*pi*2; writeln(ans:0:1); end; begininit;main;end.
网站标题:Python求凸包的函数 python凸包检测
分享网址:http://myzitong.com/article/dodpcij.html