1. 全栈程序员必看首页

凸包 —— 五种解法

全栈程序员-站长 • • 未分类 • 阅读 2

凸包 —— 五种解法欢迎访问 https blog csdn net lxt Lucia 宇宙第一小仙女 o 萌量爆表求带飞 o dalao 们点个关注呗 nbsp 关于凸包 之前一直漏掉了这一个 上周末组队赛 听说有一题就是凸包的模板 可惜不会 听说不算很难 正好这周空余的课很少 就顺便搞了 8 nbsp nbsp 目录前言 解一 穷举法 蛮力法 解二 分治法 解三

欢迎访问https://blog.csdn.net/lxt_Lucia～～

宇宙第一小仙女\(^o^)/～～萌量爆表求带飞=≡Σ((( つ^o^)つ~ dalao们点个关注呗～～

 

关于凸包，之前一直漏掉了这一个，上周末组队赛，听说有一题就是凸包的模板，可惜不会，听说不算很难，正好这周空余的课很少，就顺便搞了8… 

 

目录

  • 前言
  • 解一：穷举法（蛮力法）
  • 解二：分治法
  • 解三：Jarvis步进法
  • 解四：Graham扫描法
  • 解五：Melkman算法
  • 快包算法代码（C语言）
  • 例题（ HDU 3285 ）及模板

 

前言：

首先，什么是凸包？ 

è¿éåå¾çæè¿°

然后，什么是凸包问题？ 

 

然后，什么是极角排序和左转判定？

1）极角排序：就是选取一个最左的点，按y最小，其次x最小来定义，接下来所有的点针对该点的射线，按角度由小到大，若相同

                        按距离由近到远来排序。

2）左转判定：这个和叉积有关，对于向量p1(x1,y1),p2(x2,y2)如果x1*y2-x2*y1>0,则从p1到p2左转

 

下面，我们来看一下解决凸包问题的五种方法。

 

 

解一：穷举法（蛮力法）

 è¿éåå¾çæè¿°
当上式结果为正时，p3在直线 p1p2 的左侧；当结果为负时，p3在直线 p1p2 的右边。

 

 

解二：分治法

è¿éåå¾çæè¿°

注意：在步骤一，如果横坐标最小的点不止一个，那么这几个点都是凸包上的点，此时上包和下包的划分就有点不同了，需要注意。

 

 

解三：Jarvis步进法

è¿éåå¾çæè¿°
注意：

 

 

解四：Graham扫描法

如果没看懂的话，咱们再换种描述方式：

（1）选取最下左的点P0。

（2）计算出每个点相对于P0的角度和距离(利用这个来排序)排序。

（3）设点数为n，将p[n-1]和p[0]入栈，判断点集合是否为一条直线（初始k=2表示当前凸包的大小）。

（4）i 从1到 n-1 遍历，对于p[k-1],p[k-2],p[i]若满足左转，将p[i]压入栈。否则就 i– ，k– 。

如果还没懂，那咱们放在动图里看一下。

以下为用Graham扫描法动态求解的过程： 

è¿éåå¾çæè¿°

模板代码实现：

int Polygon::Graham(Polygon &con) //别用自己做对象 { int t=0,k=0; Point tmp;//先y最小再x最小 for(i=1; i 
                0) con.p[k++]=p[i]; else { i--; k--; } } } return con.n=--k; }   /* 9 1 4 3 6 5 7 2 2 3 3 5 4 8 3 9 6 7 1 */

 

 

解五：Melkman算法

è¿éåå¾çæè¿°

说真的，这个算法网上的资料也少的可怜，先把网上的解释截个图在这里。

下面详细介绍一下这个基于Graham扫描线算法却更加强大的凸包算法 —— Melkman算法

问题： 
平面上有一个简单多边形，沿着多边形的边，按照逆时针的顺序给出多边形的顶点的坐标，要求你求出此多边形的凸包。

因此，我现在来介绍一种由Melkman在1987年发明的，可以在O（n）的时间复杂度下求出正确的，简单多边形的凸包的Melkman算法

这个算法是基于Graham扫描线算法的，他们的大体思路相同，但是不同之处在于，Graham使用一个栈来维护凸包，而Melkman使用一个双头队列来维护凸包，每次不仅仅维护队列头的凸性，也维护队列尾的凸性，因此，它得到每时每刻都包含当前考虑过的所有的点的凸包 
下面我们模拟一下 
对于一个n个点的多边形，我们开一个大小为2*n的deque（即双头队列），设bot为队列尾，top为队列头，bot初始值为n-1，top初始值为n 
我们把点1从前插入队列，同时top++，接下来，由于队列里只有一个点1，我们可以直接把2从队列头插入和把2从队列尾插入注意，从现在起每时每刻，队列头和队列尾的点总是同一个，也就是当前凸包里的最后考虑的点 
接下来我们插入点3 
我们说过，要在队列头和队列尾都维护凸性，如果队列头不是凸的，在队列头弹栈（top–），如果队列尾不是凸的，我们在队列尾弹栈（bot++），我们写程序的时候，在队列头维护一下，然后入栈，之后在队列尾维护一下，然后入栈，所以最后，我们的队列会是3 1 2 3或者3 2 1 3 
这是头三个点 
我们现在来考虑点4，我们看，队列头和队列正数第二个点所连成的直线，队列尾和队列倒数第二个点所连成的直线，以及剩下的凸包上的边们，会把平面分为5个部分，看图 
这个图 
如果第四个点落在区域II，说明对列头不合法了，在队列头弹栈，如果在区域III，我们要在队列尾进行维护，如果在区域I，我们要把队列的头和尾一起进行维护，如果在区域IV说明这个点是当前所求得的凸包内部的点，明显对答案没有贡献，我们此时直接忽略这个点去看第五个点（上次用Graham跑凸包时的错误可被此情况排除） 
那么，如果点落在区域V呢？？？ 
并不会落在区域V！ 
因为我们是个简单多边形，如果在区域V有点，则必然产生自交边，这是违背简单多边形的定义的。 
如此进行下去，直到我们将所有的点考虑一遍，此时bot+1到top-1就是凸包上的点 
时间复杂度很明显是线性的，因为每个点最多进栈出栈一次 
而且此算法还是个在线算法，可以随时接收新的点，并且我最开始塞入队列中的点不必非得在凸包上，相比之下，这个算法比Graham妙得多 
来看一下蒟蒻丑到不行的代码 
代码
实现细节：判断在什么区域时，只需要先排除IV区，接着队列头队列尾分别判断即可，无需细究究竟是什么区域 
那么就是这样，通过对此博客的阅读，您： 
1），明白了求简单多边形凸包时Graham错误的原因 
2），学会了目前最优的凸包算法——Melkman算法 
3），明白了这个博客创作者是个蒟蒻 
如果您第二条收获并没有，建议您再仔细看看，因为我的博客可能是最详细的讲授Melkman算法的了 
就是这样希望您有收获 
我的号是1145101354 ，欢迎大家加我来讨论问题（请注明来自CSDN） 
以上 
（还不快夸我可爱QwQ






















































 

扩展：
以上讨论的只是二维的凸包，如果延生为三维、多维的凸包问题呢？如何求解？ 
不过首先，二维凸包可以用来解决围栏问题、城市规划问题、聚类分析等等。但是三维、多维的凸包可能的使用范畴有哪些？




 

 

附：快包算法代码（C语言）：

#include 
         
           #include 
          
            int g_result[240][2]; /*getResult()实现功能：以坐标P0(x1,y1)和Pn(x2,y2)为直线，找出pack里面里这条直线最远的点Pmax *并找出直线P0Pmax和PmaxPn的上包，进行递归。 *注：Pack[0][0]存放点的个数，pack[1]开始存放点的坐标。 *全局变量g_result[][]用来存放凸包上的点，即最终所要的答案。同样g_result[0][0]存放的是已找到的点的个数。 / void getResult(int Pack[240][2], int x1, int y1, int x2, int y2) { int i,t,x3,y3,R,Rmax,tmax; int ResultPack[240][2]; ResultPack[0][0] = 0; if(Pack[0][0] <= 1) return; x3 = Pack[1][0]; y3 = Pack[1][1]; R = x1*y2 + x3*y1 + x2*y3 - x3*y2 - x2*y1 - x1*y3; Rmax = R; tmax = 1; for(i=2;i<=Pack[0][0];i++) { x3 = Pack[i][0]; y3 = Pack[i][1]; R = x1*y2 + x3*y1 + x2*y3 - x3*y2 - x2*y1 - x1*y3; if(R >= 0) { t = ++ResultPack[0][0]; ResultPack[t][0] = x3; ResultPack[t][1] = y3; } if(R > Rmax) { Rmax = R; tmax = i; } } if(Rmax <= 0) { for(i=1;i 
           
             x2) { x2 = x3; y2 = y3; } } g_result[1][0] = x1; g_result[1][1] = y1; g_result[2][0] = x2; g_result[2][1] = y2; g_result[0][0] += 2; getResult(Point, x1, y1, x2, y2); getResult(Point, x2, y2, x1, y1); printf("\n\n构成凸包的点有：\n"); for(i=1;i<=g_result[0][0];i++) printf("(%d,%d)\n",g_result[i][0],g_result[i][1]); system("pause"); }

 

例题（ HDU 3285 ）

Description

凸包 —— 五种解法

 

Input

 

Output

For each data set there are multiple lines of output. The first line contains a decimal integer giving the data set number followed by a single space, followed by a decimal integer giving the total number of vertices of the convex hull. The vertices of the convex hull follow, one per line in standard order. Each line contains the decimal integer x coordinate, a single space and the decimal integer y coordinate.

 

Sample Input

​​​​Sample Output

1 10

4 9

7 9

10 6

10 3

9 2

7 1

2 1

1 2

1 5

2 7

2 8

3 9

6 9

12 7

12 4

10 -2

7 -2

1 0

1 3

3 2

1 3

3 1

4 4

1 3

11 2

19 1

2 1

 

代码：

#include  #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                
                  #include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #define eps 1e-10 #define mod 1e9+7 #define PI acos(-1) #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) #define read(x) scanf("%d",&x) #define mem(a,b) memset(a,0,sizeof(a)) #define fori(a,b) for(int i=a; i<=b; i++) #define forj(a,b) for(int j=a; j<=b; j++) #define fork(a,b) for(int k=a; k<=b; k++) #define ifor(a,b) for(int i=a; i>=b; i--) #define jfor(a,b) for(int j=a; j>=b; j--) #define kfor(a,b) for(int k=a; k>=b; k--) #define IN freopen("in.txt","r",stdin) #define OUT freopen("out.txt","w",stdout) using namespace std; typedef long long LL; struct Point { int x, y; }p[55], stk[55]; int to_left(const Point& a, const Point& b, const Point& c) { return (b.y-a.y)*(c.x-a.x) - (b.x-a.x)*(c.y-a.y); } int dis(const Point& a, const Point& b) { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); } bool cmp(const Point& a, const Point& b) { int t = to_left(p[0], a, b); return t<0 || (t==0 && dis(p[0], a) 
                                            =0) top--; stk[++top] = p[i]; } k = 0; fori(1,top) { if(stk[i].y>stk[k].y || (stk[i].y==stk[k].y && stk[i].x

 

参考资料：

https://blog.csdn.net/bone_ace/article/details/

https://blog.csdn.net/foreverlin1204/article/details/

https://blog.csdn.net/thewalker88/article/details/

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/208539.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月19日 上午11:21
下一篇 2026年3月19日 上午11:21


相关推荐

  • voliate关键字[通俗易懂]

    voliate关键字[通俗易懂]

    voliate关键字[通俗易懂]1.voliate简介在上一篇文章中我们深入理解了java关键字synchronized，我们知道在java中还有一大神器就是关键volatile，可以说是和synchronized各领风骚，其中奥妙，我们来共同探讨下.通过上一篇的文章我们了解到synchronized是阻塞同步的，在线程竞争激烈的情况下会升级为重量级锁。而voliate就可以说是java虚拟机提供的最轻量级的同步锁。但它同时…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年4月29日
    85
  • 如何用Cursor+Claude两个神器，两步完成APP开发？ cursor

    如何用Cursor+Claude两个神器，两步完成APP开发？

    如何用Cursor+Claude两个神器，两步完成APP开发？

    Ai探索者的头像 Ai探索者
    2026年3月16日
    2
  • 软件开发生命周期汇总

    软件开发生命周期汇总

    软件开发生命周期汇总在开发模型知识点中 软件生命周期的概念 各种开发模型的特点和应用场合 主要的开发模型有瀑布模型 增量模型 螺旋模型 喷泉模型 智能模型 V 模型 RAD 模型 CBSD 模型 原型方法 XP 方

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月16日
    5
  • 数字证书简介_全域数字证书

    数字证书简介_全域数字证书

    数字证书简介_全域数字证书数字证书，一种集合了多种加密方式的安全标准，数字证书通常由受到人们广泛信赖的组织向第三方颁发，表明这个第三方也是一个值得信赖的对象。

    全栈程序员-站长的头像 全栈程序员-站长
    2022年10月1日
    3
  • 关于解决token过期失效问题「建议收藏」

    关于解决token过期失效问题「建议收藏」

    关于解决token过期失效问题「建议收藏」关于解决token过期失效问题，用户对token无感知（实现免登陆）一、先认识下token二、整体思路三、实现步骤1.理清各个文件作用2.路由导航守卫3.封装localStorage方法4.vuex5.封装axios实现请求拦截器和响应拦截器（重点部分）四、小结一、先认识下token二、整体思路三、实现步骤1.理清各个文件作用2.路由导航守卫设置用户有无token访问主页，并且登录成功回到目标页importVuefrom’vue’importVueRouterfrom’v

    全栈程序员-站长的头像 全栈程序员-站长
    2025年11月2日
    4
  • 【SpringBoot】19、SpringBoot中实现启动任务

    【SpringBoot】19、SpringBoot中实现启动任务

    【SpringBoot】19、SpringBoot中实现启动任务我们在项目中会用到项目启动任务，即项目在启动的时候需要做的一些事，例如：数据初始化、获取第三方数据等等，那么如何在SpringBoot中实现启动任务，一起来看看吧SpringBoot中提供了两种项目启动方案，CommandLineRunner和ApplicationRunner一、CommandLineRunner使用CommandLineRunner，需要自定义一个类区实现CommandLineRunner接口，例如：importorg.springframework.boot.

    全栈程序员-站长的头像 全栈程序员-站长
    2026年4月13日
    7

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号