凸包算法入门

2018/03/06 15:41
阅读数 22

前言:

首先,什么是凸包? 
假设平面上有p0~p12共13个点,过某些点作一个多边形,使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候,我们就叫它“凸包”。如下图: 
这里写图片描述

然后,什么是凸包问题? 
我们把这些点放在二维坐标系里面,那么每个点都能用 (x,y) 来表示。 
现给出点的数目13,和各个点的坐标。求构成凸包的点?

 

 

 

解一:穷举法(蛮力法)

时间复杂度:O(n³)。 
思路:两点确定一条直线,如果剩余的其它点都在这条直线的同一侧,则这两个点是凸包上的点,否则就不是。 
步骤:

  1. 将点集里面的所有点两两配对,组成 n(n-1)/2 条直线。
  2. 对于每条直线,再检查剩余的 (n-2) 个点是否在直线的同一侧。

如何判断一个点 p3 是在直线 p1p2 的左边还是右边呢?(坐标:p1(x1,y1),p2(x2,y2),p3(x3,y3))

这里写图片描述 
当上式结果为正时,p3在直线 p1p2 的左侧;当结果为负时,p3在直线 p1p2 的右边。

 

 

 

解二:分治法

时间复杂度:O(n㏒n)。 
思路:应用分治法思想,把一个大问题分成几个结构相同的子问题,把子问题再分成几个更小的子问题……。然后我们就能用递归的方法,分别求这些子问题的解。最后把每个子问题的解“组装”成原来大问题的解。 
步骤:

  1. 把所有的点都放在二维坐标系里面。那么横坐标最小和最大的两个点 P1 和 Pn 一定是凸包上的点(为什么呢?用反证法很容易证明,这里不详讲)。直线 P1Pn 把点集分成了两部分,即 X 轴上面和下面两部分,分别叫做上包和下包。
  2. 对上包:求距离直线 P1Pn 最远的点,即下图中的点 Pmax 。
  3. 作直线 P1Pmax 、PnPmax,把直线 P1Pmax 左侧的点当成是上包,把直线 PnPmax 右侧的点也当成是上包。
  4. 重复步骤 2、3。
  5. 对下包也作类似操作。

这里写图片描述

 


然而怎么求距离某直线最远的点呢?我们还是用到解一中的公式: 
这里写图片描述 
设有一个点 P3 和直线 P1P2 。(坐标:p1(x1,y1),p2(x2,y2),p3(x3,y3)) 
对上式的结果取绝对值,绝对值越大,则距离直线越远。

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

 

 

 

解三:Jarvis步进法

时间复杂度:O(nH)。(其中 n 是点的总个数,H 是凸包上的点的个数) 
思路:

  • 纵坐标最小的那个点一定是凸包上的点,例如图上的 P0。
  • 从 P0 开始,按逆时针的方向,逐个找凸包上的点,每前进一步找到一个点,所以叫作步进法。
  • 怎么找下一个点呢?利用夹角。假设现在已经找到 {P0,P1,P2} 了,要找下一个点:剩下的点分别和 P2 组成向量,设这个向量与向量P1P2的夹角为 β 。当 β 最小时就是所要求的下一个点了,此处为 P3 。

这里写图片描述

注意:

  1. 找第二个点 P1 时,因为已经找到的只有 P0 一个点,所以向量只能和水平线作夹角 α,当 α 最小时求得第二个点。
  2. 共线情况:如果直线 P2P3 上还有一个点 P4,即三个点共线,此时由向量P2P3 和向量P2P4 产生的两个 β 是相同的。我们应该把 P3、P4 都当做凸包上的点,并且把距离 P2 最远的那个点(即图中的P4)作为最后搜索到的点,继续找它的下一个连接点。

 

 

 

解四:Graham扫描法

时间复杂度:O(n㏒n) 
思路:Graham扫描的思想和Jarris步进法类似,也是先找到凸包上的一个点,然后从那个点开始按逆时针方向逐个找凸包上的点,但它不是利用夹角。 
这里写图片描述 
步骤:

  1. 把所有点放在二维坐标系中,则纵坐标最小的点一定是凸包上的点,如图中的P0。
  2. 把所有点的坐标平移一下,使 P0 作为原点,如上图。
  3. 计算各个点相对于 P0 的幅角 α ,按从小到大的顺序对各个点排序。当 α 相同时,距离 P0 比较近的排在前面。例如上图得到的结果为 P1,P2,P3,P4,P5,P6,P7,P8。我们由几何知识可以知道,结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。 
    (以上是准备步骤,以下开始求凸包) 
    以上,我们已经知道了凸包上的第一个点 P0 和第二个点 P1,我们把它们放在栈里面。现在从步骤3求得的那个结果里,把 P1 后面的那个点拿出来做当前点,即 P2 。接下来开始找第三个点:
  4. 连接 栈最上面的连个元素(即P0和栈顶)的那个点,得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5;如果在直线上,或者在直线的左边就执行步骤6。
  5. 如果在右边,则栈顶的那个元素不是凸包上的点,把栈顶元素出栈。执行步骤4。
  6. 当前点是凸包上的点,把它压入栈,执行步骤7。
  7. 检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点,返回步骤4。

最后,栈中的元素就是凸包上的点了。 
以下为用Graham扫描法动态求解的过程: 
这里写图片描述

 

 

 

解五:Melkman算法

这里写图片描述 
说真的,这个算法我也还没有看清。网上的资料也少的可怜,我暂且把网上的解释截个图在这里,往后搞懂以后再回来补上。 
或者有人看懂了的,希望不吝指教,不甚感激! 

 

 

扩展:

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

 

分治法实现代码:

#include<stdio.h>
#include<stdlib.h>

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<ResultPack[0][0];i++)
        {
            x3 = ResultPack[i][0];
            y3 = ResultPack[i][1];
            R = x1*y2 + x3*y1 + x2*y3 - x3*y2 - x2*y1 - x1*y3;
            if(R == 0 && !((x3==x2&&y3==y2)||(x3==x1&&y3==y1)))
            {
                t = ++g_result[0][0];
                g_result[t][0] = ResultPack[i][0];
                g_result[t][1] = ResultPack[i][1];
            }
        }
        return;
    }
    else
    {
        t = ++g_result[0][0];
        g_result[t][0] = Pack[tmax][0];
        g_result[t][1] = Pack[tmax][1];
        if(ResultPack[0][0] == 0)
            return;
    }
    getResult(ResultPack,x1,y1,Pack[tmax][0],Pack[tmax][1]);
    getResult(ResultPack,Pack[tmax][0],Pack[tmax][1],x2,y2);
}

void main()
{
    int Point[240][2];//Point存所有点。
    int i=1;
    int x1,y1,x2,y2,x3,y3;
    g_result[0][0]=0;Point[0][0]=0;//Point的第一行第一列元素存放包里面有几个点。初始化为0。
    printf("请输入所有点的坐标:\n");
    while(scanf("%d,%d",&Point[i][0],&Point[i][1]) != EOF)
        i++;
    Point[0][0] = i-1;
    x1 = Point[1][0];
    y1 = Point[1][1];
    x2 = x1;
    y2 = y1;
    for(i=2;i<=Point[0][0];i++)
    {
        x3 = Point[i][0];
        y3 = Point[i][1];
        if(x3 < x1)
        {
            x1 = x3;
            y1 = y3;
        }
        else if(x3 > 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");
}

 

Graham扫描法实现代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>


using namespace std;
struct node
{
    int x,y;
};
node vex[1000];//存入的所有的点
node stackk[1000];//凸包中所有的点
int xx,yy;
bool cmp1(node a,node b)//排序找第一个点
{
    if(a.y==b.y)
        return a.x<b.x;
    else
        return a.y<b.y;
}
double cross(node a,node b,node c)//计算叉积 判断bc向量到ac向量 是否通过左转得到 >0左转 <0右转  =0共线 
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dis(node a,node b)//计算距离
{
    return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));
}
bool cmp2(node a,node b)//极角排序另一种方法,速度快
{
    if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))
        return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));
    return a.x<b.x;
}
bool cmp(node a,node b)//极角排序
{
    int m=cross(vex[0],a,b);
    if(m>0)
        return 1;
    else if(m==0&&dis(vex[0],a)-dis(vex[0],b)<=0)  //共线 也读入凸包 
        return 1;
    else return 0;
     
}
int main()
{
    int t,L;
    int i;
    t=7;
        
    vex[0].x=1,vex[0].y=0; 
    vex[1].x=-1,vex[1].y=1; 
    vex[2].x=2,vex[2].y=0; 
    vex[3].x=0,vex[3].y=0; 
    vex[4].x=-1,vex[4].y=-1; 
    vex[5].x=1,vex[5].y=-1; 
    vex[6].x=-2,vex[6].y=-0;   //可以用while读  更改 
        
   
    memset(stackk,0,sizeof(stackk));
    
    sort(vex,vex+t,cmp1);//最左下角的点 
    stackk[0]=vex[0];  //第一个凸包点 
    sort(vex+1,vex+t,cmp);//cmp2是更快的,cmp更容易理解   极角排序
            
    stackk[1]=vex[1];//将第2个点存入凸包的结构体中
    
    int top=1;//最后凸包中拥有点的个数  实际为2 
    for(i=2; i<t; i++)
    {
                
        while(cross(stackk[top-1],stackk[top],vex[i])<0){   //是否满足叉乘大于0 不满足出栈  控制<0或<=0可以控制重点,共线
            top--;        
        }
        stackk[++top]=vex[i];  //满足的入栈 
                        
    }
       
    for(i=0; i<=top; i++)   
        cout<<stackk[i].x<<" "<<stackk[i].y<<endl;
}

 练习题:圈水池

展开阅读全文
vex
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部