Python求凸包的函数 python计算包

使用Python 会降低程序员的编程能力吗

十年前，Pascal。我会精确计算每个数组和变量使用的内存，熟练地用非递归方法改写程序，最短的时间内自己实现各种排序，多源最短路径，求凸包和相邻

点，动态规划，二分图匹配和网络流算法等等等等，同时考虑算法的最坏复杂度和最高项前边的那个常数。现在，我一个都不记得Python求凸包的函数了是的现在列举这些名词我就是在装逼。

五

年前，C。我会自认为炫酷的使用函数指针，强制类型转换，goto语句，宏来实现各种技巧（Python求凸包的函数他喵的全是Linux

kernel害的）。我挣扎在多线程，多进程和各种锁。我试着照ICC出来的汇编改程序。但Python求凸包的函数你让我不看书写个红黑树出来我是做不到了。现在，Python求凸包的函数你突然让我写

个C程序我得想一下语法。（所以这里我还是在装逼。）

现在，Python。写之前习惯性搜一下有没有现成的库。不会自己去实现图的数据结构了，因为有NetworkX。不会自己去处理网络通信了，用Redis搞个发布订阅机制或者干脆实现个ReST服务都没几行代码。多线程？Gevent搞异步多简单速度还比你快。

但是。

十年前我只能刷刷USACO和浙大同济的Online Judge。AC是最高目标。

五年前我只能写写自己用的小软件系统驱动什么的，或者通宵写个大作业。

现在我在研究用Evolutionary Optimisation在云平台上调度Scientific Workflow。

会什么和干什么，你觉得哪个重要？

我

的意思并不是说因为用这些语言所以在干这些事儿，而是确确实实感觉到这些年自己的编程能力（或者说基本功，因为毕竟很多高级的技巧我也会的越来越多）在下

降，而且我认为这和我用的语言越来越高级是有一定关系的。当然语言和做的事之间完全没什么必然关系。但是以前的水平高又怎么样呢？做出来的不过是没有人关

心的玩具罢了。即使能力值降低了，不过既然现在在做也可以做更有意义的事了，谁还关心跑分呢。

相关问答

Q1: 凸包的平面求法

这个算法是由数学大师葛立恒（Graham）发明Python求凸包的函数的，他曾经是美国数学学会（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，过程如下Python求凸包的函数：

计算点集最右边的点为凸包的顶点的起点，如上图的P3点。

Do

For i = 0 To 总顶点数

计算有向向量P3-Pi

If 其余顶点全部在有向向量P3-Pi的左侧或右侧，则Pi点为凸包的下一顶点

Pi点加入凸包列表

GoTo 1

End If

Next

Exit Do

1:

Loop

此过程执行后，点按极角自动顺时针或逆时针排序，只需要按任意两点的次序就可以Python求凸包的函数了。而左侧或右侧的判断可以用前述的矢量点积性质实现。 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.

Q2: 2021-02-16 Python OpenCV convexHull()函数

此函数利用Sklansky's算法在一个二维点集中找到凸包。时间复杂度为 。

其中Python求凸包的函数，points和hull应该为不同Python求凸包的函数的数组Python求凸包的函数，该函数不支持原地处理。

Q3: matlab中convhull函数怎么用

matlab中的convhull（）函数是凸包函数，用于计算给定区域的面积或体积。convhull使用格式：

一、凸包面积

k = convhull(x,y) %计算凸包的面积

例如：

P = [0 0; 1 1; 1.5 0.5; 1.5 -0.5; 1.25 0.3; 1 0; 1.25 -0.3; 1 -1];

[k,av] = convhull(P); %av=1.75

plot(P(:,1),P(:,2),'*') %绘制原始点及凸包。

hold on

plot(P(k,1),P(k,2))

二、凸包体积

k = convhull(x,y,z) %计算凸包的体积

例如：

[x,y,z] = meshgrid(-2:1:2,-2:1:2,-2:1:2);

x = x(:);y = y(:);z = z(:);

[k,av] = convhull(x,y,z);av %av=64

trisurf(k,x,y,z,'FaceColor','cyan'),axis equal

Q4: 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, 下期见。

Python求凸包的函数的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于python计算包、Python求凸包的函数的信息别忘了在本站进行查找喔。