Graham算法求凸包完整程序代码

凸包算法模型想象在⼀个平⾯上钉下了n个钉⼦。

现在有⼀根橡⽪筋，我们把它撑开，期望在松⼿之后橡⽪筋可以收缩，包住所有的n个钉⼦。

事实上，这正是⼀个凸包。

如下图：引⼊凸包的概念：凸包，定义为周长最⼩的包含点集中所有点的凸多边形。

即使存在某个凹多边形的周长与凸包相等且可以包含所有点，这个凹多边形也⼀定不是凸包。

如下图，这个凹多边形不是该点集的凸包：凸包问题属于计算⼏何，通常可以使⽤Andrew,Graham,Jarvis，斜率逼近等算法求解。

本⽂将着重介绍其中思想通俗、代码简单的Andrew算法。

由于求解凸包需要⼀些前置的计算⼏何知识，本⽂将会介绍⼀些基础计算⼏何知识。

前置知识引进向量的概念。

在数学中，向量指同时具有⼤⼩和⽅向的量，与之相对的量称为数量。

数量只有⼤⼩，没有⽅向。

向量可以⽤⼀条带箭头的线段来形象地表⽰：箭头代表⽅向，线段的长度代表向量的⼤⼩。

如果向量的起点为A，终点为B，则这个向量可以记作→ab。

两个向量→x1,y1和→x2,y2的外积称之为叉积，它的结果是⼀个向量。

叉积的计算⽅法是 (x1y2)−(x2y1) ，记为→x1,y1×→x2,y2。

对于两个向量→ab,→bc，如果它们的叉积>0 ，说明→ab在→bc的顺时针⽅向；如果它们的叉积=0，说明→ab和→bc共线；如果它们的叉积<0，说明→ab在→bc的逆时针⽅向。

算法思想凸包Andrew算法的思想⾮常简单。

我们⾸先把点集按照以x坐标为第⼀关键字，以y坐标为第⼆关键字的⽅式进⾏双关键字从⼩到⼤排序，排序后的第⼀个点就是我们选出的极点。

两个关键字的顺序可以调换。

如下图，点 1 就是该点集的极点。

接着，我们从极点开始逆时针考虑将每⼀个点都加⼊凸包。

显然我们排序后的第⼀个点和最后⼀个点⼀定在凸包上。

从第⼆个点开始，我们假设当前点可以加⼊凸包。

设凸包上此时有m个点，第m−1 个点和第m个点分别是a,b，当前要加⼊凸包的点为c。

坐标点连接成多边形的程序多边形是几何学中的一个重要概念，它由一系列的顶点和边组成。

在计算机图形学和计算几何学中，我们经常需要编写程序来连接给定的坐标点，从而构造出多边形。

本文将介绍如何编写一个程序来实现这一功能。

我们需要明确程序的输入和输出。

输入是一组坐标点的集合，每个坐标点都有一个x和y坐标值。

输出是通过连接这些坐标点而构成的多边形。

接下来，我们需要确定程序的算法。

一种常见的算法是使用凸包算法来连接坐标点。

凸包算法是一种计算凸多边形的方法，它可以从给定的坐标点中找出一个包含所有点的最小凸多边形。

凸包算法的基本思想是，首先找到一个起始点作为凸包的一部分，然后按照一定的规则逐步添加其他点，直到形成一个封闭的凸多边形。

常用的凸包算法有Graham扫描算法和Jarvis步进算法。

以Graham扫描算法为例，我们可以按照以下步骤编写程序：1. 将所有坐标点按照x坐标从小到大进行排序；2. 选择第一个坐标点作为起始点，并将其入栈；3. 依次遍历剩下的坐标点，对于每个坐标点，判断其与栈顶两个点构成的直线是否是一个左转弯；4. 如果是左转弯，则将该点入栈；5. 如果不是左转弯，则将栈顶的点出栈，直到栈顶两个点与当前点构成的直线是一个左转弯；6. 遍历完所有的坐标点后，栈中的点即为凸包的顶点。

通过这个算法，我们可以将给定的坐标点连接成一个凸多边形。

如果需要连接成非凸多边形，我们可以通过添加额外的步骤来实现。

在实际编写程序时，我们可以使用编程语言如Python、C++或Java 来实现。

下面是一个使用Python语言实现的示例代码：```pythondef connect_points(points):sorted_points = sorted(points, key=lambda p: p[0])stack = [sorted_points[0]]for i in range(1, len(sorted_points)):while len(stack) >= 2 and orientation(stack[-2], stack[-1], sorted_points[i]) <= 0:stack.pop()stack.append(sorted_points[i])return stackdef orientation(p, q, r):return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])# 测试样例points = [(0, 0), (1, 1), (2, 2), (1, 0), (3, 1), (2, 0)] result = connect_points(points)print(result)```以上代码实现了一个连接坐标点的函数connect_points，它接受一个坐标点的列表作为输入，返回连接后的多边形的顶点列表。

葛立恒扫描法葛立恒扫描法（Graham Scan），又称凸包算法，是解决计算几何问题中的经典算法之一。

它的主要作用是计算多边形或点集的凸包，并返回凸包上的点集。

葛立恒扫描法的时间复杂度为O(nlogn)，其中n是输入点集的大小。

凸包是一个简单多边形，可以包含给定点集中的所有点。

它的边界是由点集中的一些点组成的，这些点被称为凸包上的顶点。

凸包在计算几何、图形学以及计算机视觉等领域都有广泛的应用。

葛立恒扫描法的运行过程如下：1. 找到y值最小的点，并将它放在结果集中。

2. 将其余所有点按照与y值最小点的极角进行排序。

3. 对于每个点P，计算它与前两个点的极角。

如果它的角度不在逆时针方向，则将倒数第二个点从结果集中删除，然后重复此过程直到极角正确。

4. 返回结果集。

让我们来详细了解葛立恒扫描法的每个步骤。

找到y值最小的点要找到y值最小的点，我们可以遍历所有点，并找到纵坐标最小的那个。

在这里，我们使用了lambda函数来比较每个点的y值。

```python def find_lowest_point(points): lowest = min(points, key=lambda point: point[1]) return lowest ```排序接下来，我们需要将其余所有点按照与y值最小点的极角进行排序。

为此，我们需要定义一个函数来计算两点之间的极角。

在这里，我们使用了arctan2函数来计算极角。

```python def polar_angle(p1, p2=None): if p2 is None: p2 = lowest_point y_span =p1[1] - p2[1] x_span = p1[0] - p2[0] return atan2(y_span, x_span) ```然后，我们可以使用此函数来排序输入点集。

在这里，我们使用了sorted函数来排序。

```python def sort_points(points):sorted_points = sorted( points,key=cmp_to_key(lambda x,y: 1 if polar_angle(x) < polar_angle(y) else -1) ) returnsorted_points ```计算极角接下来，我们需要为每个点计算它与前两个点的极角。

convexhull函数Convex Hull是计算凸包的一种常用算法，它是一个包围一组点的最小凸多边形。

凸包问题在计算机图形学、计算几何学和计算机视觉等领域中都有广泛的应用，用于解决诸如寻找最远点、点集包含关系判断等问题。

Convex Hull算法有多种实现方式，最常见的包括Graham Scan、Jarvis March以及Quick Hull。

下面将详细介绍Graham Scan算法。

1.算法思想：Graham Scan算法的基本思想是通过构建一个逆时针的类环排序，先找到最低的点（Y轴最小，如果有多个，则选择X轴最小的点），然后将其与其他所有点按照相对于最低点的极坐标进行排序。

排序后，按顺序将点加入凸包，同时保持凸包的有序性。

最后，返回生成的凸包。

2.算法步骤：a.找到最低点：遍历所有的点，找到Y轴最小值最小，并记录最低点的索引。

b.极坐标排序：除最低点外的其他点，根据其相对于最低点的极坐标进行排序。

c.构建凸包：依次将点加入凸包，同时根据凸包的有序性，维护凸包的结构。

d.返回凸包。

3.具体实现：下面是Graham Scan算法的伪代码实现：a.找到最低点：minPoint = points[0]for p in points:if p.y < minPoint.y or (p.y == minPoint.y and p.x < minPoint.x):minPoint = pb.极坐标排序：orientation = getOrientation(minPoint, point1, point2)if orientation == 0:return distSq(minPoint, point2) >= distSq(minPoint, point1) else:return orientation == 2c.构建凸包：hull = [minPoint]for i in range(1, len(sortedPoints)):while len(hull) > 1 and getOrientation(hull[-2], hull[-1], sortedPoints[i]) != 2:hull.pophull.append(sortedPoints[i])d.返回凸包：return hull4.时间复杂度：Graham Scan算法的时间复杂度为O(nlogn)，其中n为点的数量。

平面散乱点集凸包算法matlab在计算几何学和计算机图形学中，凸包是一个常见的概念，它指的是包围一组点的最小凸多边形。

在平面上，凸包可以用于解决许多实际问题，比如寻找最远点对、计算最小包围矩形等。

在本文中，我们将介绍如何使用Matlab实现平面散乱点集的凸包算法。

Matlab是一种强大的数学计算软件，它提供了丰富的函数和工具箱，可以方便地进行凸包计算。

首先，我们需要明确凸包算法的基本原理。

凸包算法的一种常见实现是Graham扫描算法，它基于极角排序和栈的数据结构。

在Matlab中，我们可以使用sortrows函数对点集进行极角排序，然后利用栈来实现凸包的计算。

接下来，我们将以一个简单的示例来说明如何在Matlab中实现凸包算法。

假设我们有一组散乱的二维点集P，我们首先需要对这些点进行极角排序，然后利用栈来计算凸包。

matlab.function hull = convexHull(points)。

% Sort the points based on polar angle.[~, idx] = sortrows(points);sortedPoints = points(idx, :);% Initialize the stack.stack = [];% Graham scan algorithm.for i = 1:length(sortedPoints)。

while length(stack) > 1 && ccw(stack(end-1,:), stack(end,:), sortedPoints(i,:)) <= 0。

stack(end) = [];end.stack = [stack; sortedPoints(i,:)];end.hull = stack;end.function orientation = ccw(p1, p2, p3)。

orientation = (p2(2) p1(2)) (p3(1) p2(1)) (p2(1)p1(1)) (p3(2) p2(2));end.在上面的示例中，我们首先对点集进行极角排序，然后利用栈来实现Graham扫描算法。

凸包算法及凸包融合凸包算法是计算凸包的一种常用算法，它可以找到一组点集中最外层的凸多边形。

凸包融合是指将两个凸包合并成一个新的凸包，能够通过减少顶点数目来优化计算效率。

凸包算法主要有以下几种常见的实现方法：1.枚举算法：对于点集中的每一对点，判断其他点是否位于这两点所确定的直线的一侧。

如果所有点都在一侧，则这两点是凸包上的边。

时间复杂度为O(n^3)。

2. Graham扫描算法：选取一个点作为基准点，将其他点按照相对于基准点的极角大小进行排序。

然后依次处理每个点，判断其是否属于凸包。

时间复杂度为O(nlogn)。

3. Jarvis步进算法（也称为包裹法）：从点集中选取一个临时点p，然后找到与p相邻的点集中极角最小的点q，将q加入凸包中。

然后将q作为新的临时点p，重复以上步骤，直到回到第一个点。

时间复杂度为O(nh)，其中h是凸包的边数。

4.快速凸包算法：通过空间分割和递归的方法进行凸包计算，时间复杂度为O(nlogn)。

凸包融合是指将两个凸包合并成一个新的凸包，通常需要满足以下条件：1.相交边的共享：两个凸包如果相交，那么它们的公共边必须都在新的凸包中。

2.外部边的合并：如果两个凸包没有相交，那么合并后的凸包应该包含两个凸包的外部边。

3.顺序性：合并后的凸包应该按照某种规定的顺序进行连接。

凸包融合算法的一种常见方法是基于边的融合。

具体步骤如下：1.找到两个凸包之间的最近边，并将其作为起始边。

2.沿着其中一个凸包的边界向对面的凸包前进，每次选取与当前边最接近的边。

3.如果新选取的边与已经选取的边形成了一个角度大于180度的三角形，那么停止前进，并将新选取的边作为起始边。

4.重复步骤2和步骤3，直到回到起始边。

凸包融合算法可以减少凸包的顶点数量，从而提高计算效率。

例如，对于两个有m和n个顶点的凸包，假设m > n，则融合后的凸包最多有m+n个顶点，而不是m*n个顶点。

融合后的凸包可以保留原始凸包的边界信息，并且减少了计算和存储开销。

概念凸包(Convex Hull)是一个计算几何（图形学）中的概念。

用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有点的。

严谨的定义和相关概念参见维基百科：凸包。

这个算法是由数学大师葛立恒(Graham)发明的，他曾经是美国数学学会(AMS)主席、AT&T首席科学家以及国际杂技师协会(IJA)主席。

（太汗了，这位大牛还会玩杂技~）问题给定平面上的二维点集，求解其凸包。

过程1. 在所有点中选取y坐标最小的一点H，当作基点。

如果存在多个点的y坐标都为最小值，则选取x坐标最小的一点。

坐标相同的点应排除。

然后按照其它各点p和基点构成的向量<H,p>与x轴的夹角进行排序，夹角由大至小进行顺时针扫描，反之则进行逆时针扫描。

实现中无需求得夹角，只需根据向量的内积公式求出向量的模即可。

以下图为例，基点为H，根据夹角由小至大排序后依次为H，K，C，D，L，F，G，E，I，B，A，J。

下面进行逆时针扫描。

2. 线段<H, K>一定在凸包上，接着加入C。

假设线段<K, C>也在凸包上，因为就H，K，C 三点而言，它们的凸包就是由此三点所组成。

但是接下来加入D时会发现，线段<K, D>才会在凸包上，所以将线段<K, C>排除，C点不可能是凸包。

3. 即当加入一点时，必须考虑到前面的线段是否会出现在凸包上。

从基点开始，凸包上每条相临的线段的旋转方向应该一致，并与扫描的方向相反。

如果发现新加的点使得新线段与上线段的旋转方向发生变化，则可判定上一点必然不在凸包上。

实现时可用向量叉积进行判断，设新加入的点为p n + 1，上一点为p n，再上一点为p n - 1。

顺时针扫描时，如果向量<p n - 1, p n>与<p n, p n>的叉积为正（逆时针扫描判断是否为负），则将上一点删除。

最⼩凸包算法使⽤Graham扫描法进新解决最⼩凸包问题先找到最左下端点然后根据极⾓来进⾏逆时针排序在根据相对极⾓增减来去除不需要的点C++代码1 #include<iostream>2 #include<cstdio>3 #include<cstring>4 #include<algorithm>5 #include<cmath>6#define PI 3.14159265357using namespace std;8struct node9 {10int x,y;11 };12 node vex[1000];//存⼊的所有的点13 node stackk[1000];//凸包中所有的点14int xx,yy;15bool cmp1(node a,node b)//排序找第⼀个点16 {17if(a.y==b.y)18return a.x<b.x;19else20return a.y<b.y;21 }22int cross(node a,node b,node c)//计算叉积23 {24return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);25 }26double dis(node a,node b)//计算距离27 {28return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));29 }30bool cmp2(node a,node b)//极⾓排序另⼀种⽅法，速度快31 {32if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))33return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));34return a.x<b.x;35 }36bool cmp(node a,node b)//极⾓排序37 {38int m=cross(vex[0],a,b);39if(m>0)40return1;41else if(m==0&&dis(vex[0],a)-dis(vex[0],b)<=0)42return1;43else return0;44/*if(m==0)45 return dis(vex[0],a)-dis(vex[0],b)<=0?true:false;46 else47 return m>0?true:false;*/48 }49int main()50 {51int t,L;52while(~scanf("%d",&t),t)53 {54int i;55for(i=0; i<t; i++)56 {57 scanf("%d%d",&vex[i].x,&vex[i].y);58 }59if(t==1)60 printf("%.2f\n",0.00);61else if(t==2)62 printf("%.2f\n",dis(vex[0],vex[1]));63else64 {65 memset(stackk,0,sizeof(stackk));66 sort(vex,vex+t,cmp1);67 stackk[0]=vex[0];68 xx=stackk[0].x;69 yy=stackk[0].y;70 sort(vex+1,vex+t,cmp2);//cmp2是更快的，cmp更容易理解71 stackk[1]=vex[1];//将凸包中的第两个点存⼊凸包的结构体中72int top=1;//最后凸包中拥有点的个数73for(i=2; i<t; i++)74 {75while(i>=1&&cross(stackk[top-1],stackk[top],vex[i])<0) //对使⽤极⾓排序的i>=1有时可以不⽤，但加上总是好的76 top--;77 stackk[++top]=vex[i]; //控制<0或<=0可以控制重点，共线的，具体视题⽬⽽定。

matlab练习程序（寻找凸包，Graham扫描法） 我不太清楚这个凸包在图像处理中到底会怎样的运⽤，因为这个好像更多的是计算⼏何或是图形学⾥⾯的东西。

不过作为⼀个算法，我感觉还是有必要研究⼀下的。

我主要的参考资料是《算法导论》的33.3和。

代码在这⾥，我只写了主要过程，过分细节的判断就省略了。

这⾥是逆时针寻找：main.mclear all;close all;clc;img=ones(256,256);imshow(img);[x y]=ginput();x=round(x);y=round(y);n=length(x);p=[];for i=1:nimg(y(i)-1:y(i)+1,x(i)-1:x(i)+1)=0;p=[p;x(i) y(i)]; %待判断凸包的点集endimshow(img);%%下⾯计算凸包[t index]=max(p(:,2)); %找到y最⼤的点的索引，这⾥没考虑当有多个这样的点的情况tmp_p=p(index,:); %找到y最⼤的点tmp_heng=[tmp_p(1)+30,tmp_p(2)]; %设⼀个和y最⼤的点平⾏的点for i=1:n %这⾥没判断夹⾓相同的情况，当夹⾓相同，可以判断当前点和p0点的距离。

jiao(i)=multi_jiao(tmp_heng,p(i,:),tmp_p); %求每个点和y最⼤的点的夹⾓，⾃⼰和⾃⼰夹⾓NANendjiao=jiao';p=[p jiao];p=sortrows(p,3); %按第三列排序，第三列是夹⾓度数re{1}=p(n,1:2); %re相当于栈re{2}=p(1,1:2);re{3}=p(2,1:2);top=3; %指向栈顶的指针for i=3:n-1while multi(p(i,1:2),re{top-1},re{top})>=0 %如果为正top=top-1;endtop=top+1;re{top}=p(i,1:2);end%下⾯是把找到的凸包上的点连线for i=2:topimg=drawline(img,re{i-1}(1),re{i-1}(2),re{i}(1),re{i}(2));endimg=drawline(img,re{1}(1),re{1}(2),re{top}(1),re{top}(2));figure;imshow(img)multi_jiao.m 向量的夹⾓，0-180度function re=multi_jiao(p1,p2,p0) %判断<p10,p20>夹⾓，为排序做准备x=1;y=2;vec1=p1-p0;vec2=p2-p0;re=acos(dot(vec1,vec2)/(norm(vec1)*norm(vec2)))*180/pi;endmulti.m 叉积，判断返回值的符号function re=multi(p1,p2,p0) %p10,p20叉积，获取正负，为正则栈顶的值不为凸包上的点，为负则为凸包上的点x=1;y=2;re=(p1(x)-p0(x))*(p2(y)-p0(y))-(p1(y)-p0(y))*(p2(x)-p0(x));enddrawline.m 画线函数，matlab好像没有，⾃⼰动⼿，丰⾐⾜⾷function img=drawline(img,x1,y1,x2,y2) %因为图像坐标和数学函数坐标y轴朝向相反，所以这⾥所有y变量取相反数 y1=-y1;y2=-y2;k=(y2-y1)/(x2-x1);b=y1-k*x1;mi=min(x1,x2);ma=max(x1,x2);for i=mi:maimg(-round(i*k+b),i)=0;endmi=min(y1,y2);ma=max(y1,y2);for i=mi:maimg(-i,round((i-b)/k))=0;endend下⾯是⼀个结果，matlab最⼤的好处就是直观的看到算法结果：。