`
kmplayer
  • 浏览: 494982 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

寻找凸包的graham 扫描法

阅读更多
1,点集Q的凸包(convex hull)是指一个最小凸多边形,满足Q中的点或者在多边形边上或者在其内。
2,凸包最常用的凸包算法是Graham扫描法和Jarvis步进法。
3,Graham扫描法:
首先,找到所有点中最左边的(y坐标最小的),如果y坐标相同,找x坐标最小的.
以这个点为基准求所有点的极角(atan2(y-y0,x-x0)),并按照极角对这些点排序,前述基准点在最前面,设这些点为P[0]..P[n-1.
注:这样预处理后,保证p[0],p[1]和p[n-1]都是凸包上的点.
建立一个栈,初始时P[0]、P[1]、P[2]进栈,对于 P[3..n-1]的每个点,若栈顶的两个点与它不构成"向左转"的关系,则将栈顶的点出栈,直至没有点需要出栈以后将当前点进栈;
所有点处理完之后栈中保存的点就是凸包了。
图示:



4,实现代码
#include <iostream>
#include <cmath>
using namespace std;

/*
PointSet[]:输入的点集
ch[]:输出的凸包上的点集,按照逆时针方向排列
n:PointSet中的点的数目
len:输出的凸包上的点的个数
*/

struct Point
{
    float x,y;
};

//小于0,说明向量p0p1的极角大于p0p2的极角
float multiply(Point p1,Point p2,Point p0)
{
    return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}

float dis(Point p1,Point p2)
{
    return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}


void Graham_scan(Point PointSet[],Point ch[],int n,int &len)
{
    int i,j,k=0,top=2;
    Point tmp;

    //找到最下且偏左的那个点
    for(i=1;i<n;i++)
        if ((PointSet[i].y<PointSet[k].y)||((PointSet[i].y==PointSet[k].y)&&(PointSet[i].x<PointSet[k].x)))
            k=i;
    //将这个点指定为PointSet[0]
    tmp=PointSet[0];
    PointSet[0]=PointSet[k];
    PointSet[k]=tmp;

    //按极角从小到大,距离偏短进行排序
    for (i=1;i<n-1;i++)
    {
        k=i;
        for (j=i+1;j<n;j++)
            if( (multiply(PointSet[j],PointSet[k],PointSet[0])>0)
                ||((multiply(PointSet[j],PointSet[k],PointSet[0])==0)
                    &&(dis(PointSet[0],PointSet[j])<dis(PointSet[0],PointSet[k]))) )
                k=j;//k保存极角最小的那个点,或者相同距离原点最近
        tmp=PointSet[i];
        PointSet[i]=PointSet[k];
        PointSet[k]=tmp;
    }
    //第三个点先入栈
    ch[0]=PointSet[0];
    ch[1]=PointSet[1];
    ch[2]=PointSet[2];
    //判断与其余所有点的关系
    for (i=3;i<n;i++)
    {
        //不满足向左转的关系,栈顶元素出栈
        while(multiply(PointSet[i],ch[top],ch[top-1])>=0) top--;
        //当前点与栈内所有点满足向左关系,因此入栈.
        ch[++top]=PointSet[i];
    }
    len=top+1;
}

const int maxN=1000;
Point PointSet[maxN];
Point ch[maxN];
int n;
int len;

int main()
{
    int n=5;
    float x[]={0,3,4,2,1};
    float y[]={0,0,0,3,1};
    for(int i=0;i<n;i++)
    {
        PointSet[i].x=x[i];
        PointSet[i].y=y[i];
    }
    Graham_scan(PointSet,ch,n,len);
    for(int i=0;i<len;i++)
        cout<<ch[i].x<<" "<<ch[i].y<<endl;
    return 0;
}


5,应用:http://acm.pku.edu.cn/JudgeOnline/problem?id=1113
实现代码:
#include <iostream>
#include <cmath>
using namespace std;

/*
PointSet[]:输入的点集
ch[]:输出的凸包上的点集,按照逆时针方向排列
n:PointSet中的点的数目
len:输出的凸包上的点的个数
*/

struct Point
{
    float x,y;
};

//小于0,说明向量p0p1的极角大于p0p2的极角
float multiply(Point p1,Point p2,Point p0)
{
    return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}

float dis(Point p1,Point p2)
{
    return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}


void Graham_scan(Point PointSet[],Point ch[],int n,int &len)
{
    int i,j,k=0,top=2;
    Point tmp;

    //找到最下且偏左的那个点
    for(i=1;i<n;i++)
        if ((PointSet[i].y<PointSet[k].y)||((PointSet[i].y==PointSet[k].y)&&(PointSet[i].x<PointSet[k].x)))
            k=i;
    //将这个点指定为PointSet[0]
    tmp=PointSet[0];
    PointSet[0]=PointSet[k];
    PointSet[k]=tmp;

    //按极角从小到大,距离偏短进行排序
    for (i=1;i<n-1;i++)
    {
        k=i;
        for (j=i+1;j<n;j++)
            if( (multiply(PointSet[j],PointSet[k],PointSet[0])>0)
                ||((multiply(PointSet[j],PointSet[k],PointSet[0])==0)
                    &&(dis(PointSet[0],PointSet[j])<dis(PointSet[0],PointSet[k]))) )
                k=j;//k保存极角最小的那个点,或者相同距离原点最近
        tmp=PointSet[i];
        PointSet[i]=PointSet[k];
        PointSet[k]=tmp;
    }
    //第三个点先入栈
    ch[0]=PointSet[0];
    ch[1]=PointSet[1];
    ch[2]=PointSet[2];
    //判断与其余所有点的关系
    for (i=3;i<n;i++)
    {
        //不满足向左转的关系,栈顶元素出栈
        while(multiply(PointSet[i],ch[top],ch[top-1])>=0) top--;
        //当前点与栈内所有点满足向左关系,因此入栈.
        ch[++top]=PointSet[i];
    }
    len=top+1;
}

const int maxN=1010;
Point PointSet[maxN];
Point ch[maxN];
int n;
int len;

int main()
{
    double ans=0;
    int d;
    cin>>n>>d;
    for(int i=0;i<n;i++)
        cin>>PointSet[i].x>>PointSet[i].y;//input the data;
    Graham_scan(PointSet,ch,n,len);
    for(int i=0;i<len;i++)
        ans+=dis(ch[i],ch[(i+1)%len]);
    ans+=2*d*acos(-1.0); //等价于圆形周长
    cout<<(int)(ans+0.5)<<endl; //四舍五入
    return 0;
}
  • 大小: 38.1 KB
分享到:
评论

相关推荐

    凸包算法(Graham扫描法)JS实现.js

    采用Graham扫描法,实现提取凸包最小边界JS代码实现。(代码中点坐标采用平面坐标,如要在三维贴地展示,可转换为经纬度坐标)

    学习凸包(四):Graham 扫描法

    NULL 博文链接:https://128kj.iteye.com/blog/1749114

    凸包问题的Graham Scan法求解

    用VS2010写的Graham扫描法求解凸包问题 包括两个库文件和一个主文件 两个库文件包括凸包问题中栈的基本操作以及用到的一些点的运算函数 主函数中包含了程序的主要流程

    Python求凸包及多边形面积教程

    一般有两种算法来计算平面上给定n个点的凸包:Graham扫描法(Graham’s scan),时间复杂度为O(nlgn);Jarvis步进法(Jarvis march),时间复杂度为O(nh),其中h为凸包顶点的个数。这两种算法都按逆时针方向输出凸包顶点...

    c++Delaunay三角形凸包算法程序

    采用c++进行编程的凸包算法,是和生长算法不同的另一种构建tin的算法,该算法相对难度较大,此处用的是Graham扫描法

    ff.rar_grahamscan_n个点求其凸包_凸包测试数据_求其凸包。

    grahamScan扫描法求凸包 输入有若干组测试数据。每一组测试数据的第一行上有整数n,表示该组测试数据有n个点组成的。接下来有n行,其每一行上有二个正整数,之间用一个或几个空格隔开。当输入行上只有一个数0时,...

    46219700.rar_数据结构_MultiPlatform_

    凸包最常用的凸包算法是Graham扫描法和Jarvis步进法 本程序用Graham扫描法实现凸包的绘制

    c语言代码——ACM常用算法

    一、数学问题 1.精度计算——大数阶乘.乘法.加法.减法 .任意进制转换.最大公约数、最小公倍数....计算几何.Graham扫描法寻找凸包 .数论.求解模线性方程 图论.Dijkstra算法求单源最短路径.数据结构 。

    一种基于Graham三角剖分生成Delaunay三角网的算法 (2007年)

    方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序的点通过可见点的判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网。结果通过500至10000个点的测试,表明这种基于C-...

    acm常用代码及算法

    12.Graham扫描法寻找凸包 数论: 1.x的二进制长度 2.返回x的二进制表示中从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中国余数定理) 6.筛法素数产生器 7.判断一...

    ACM 内部预定函数

    12.Graham扫描法寻找凸包 13.求两条线段的交点 数论: 1.x的二进制长度 2.返回x的二进制表示中从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中国余数定理) 6.筛法素数产生器 7....

    DFT的matlab源代码-Image_Processing_Algorithms:一些常见的图像处理算法

    求凸包(Graham扫描法): 旋转卡壳法: Image_BWLabel(Python): Two-Pass法: Image_DFT_IDFT(C++): Image_FFT_IFFT(C++): : Image_Hough(C++): : Image_Radon(C++): : Image_White_Balance(C++): 灰度世界算法...

    ACM算法模版大集合

    Graham扫描法 水平序的引进,共线凸包的补丁 完美凸包算法 相关判定 两直线相交 两线段相交 点在任意多边形内的判定 点在凸多边形内的判定 经典问题 最小外接圆 近似O(n)的最小外接圆算法 点集直径 ...

    全面的算法代码库

    凸包算法(Graham扫描法) Graham-Scan 辗转相除法求最大公约数 Greatest-Common-Divisor 堆排序 Heap-Sort ISAP算法 Improved-Shortest-Augmenting-Path(Naive) 插入排序 Insertion-Sort 字符串匹配(KMP) ...

    ACM 算法经典代码 数据结构经典代码

    12.Graham扫描法寻找凸包 数论: 1.x的二进制长度 2.返回x的二进制表示中从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中国余数定理) 6.筛法素数产生器 7.判断一个数是否素数 ...

    算法引论:一种创造性方法.[美]Udi Manber(带详细书签).pdf

    8.4.3 Graham扫描算法 8.5 最近点对 8.6 水平线段和竖直线段的交点 8.7 小结 第9章 代数和数值算法 9.1 引言 9.2 求幂运算 9.3 欧几里得算法 9.4 多项式乘法 9.5 矩阵乘法 9.5.1 Winograd算法 9.5.2 ...

    一种快速提取植物叶片最小外接矩形的算法 (2015年)

    该算法首先使用Canny算子提取叶片轮廓,然后使用基于平面扫描法的Graham算法构造叶片轮廓凸包,最后提取叶片最小外接矩形。仿真实验结果表明:在Flavia植物叶片数据库中进行测试,该算法优于旋转法、顶点链码法。

    常用算法代码

    | GRAHAM 求凸包 O(N * LOGN) 34 | 判断线段相交 34 | 求多边形重心 34 | 三角形几个重要的点 34 | 平面最近点对 O(N * LOGN) 34 | LIUCTIC 的计算几何库 35 | 求平面上两点之间的距离 35 | (P1-P0)*(P2-P0)...

Global site tag (gtag.js) - Google Analytics