`
kmplayer
  • 浏览: 508807 次
  • 性别: 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 扫描法

    本篇文章将详细探讨“学习凸包(四):Graham扫描法”,这是一种在二维空间中找到一组点的凸包的有效算法。 Graham扫描法由Ronald Graham于1972年提出,其基本思想是首先找到点集中一个最低的点,然后按照顺时针或...

    凸包问题枚举 Graham_scan以及分治实现

    在这个项目中,我们将探讨两种解决凸包问题的方法:Graham扫描法和分治策略。 1. **Graham扫描法**: - **基本原理**:Graham扫描法是一种基于极角排序的算法,首先找到一个最低点,然后按顺时针或逆时针顺序对...

    凸包的几种常见解法Jarvis march Graham Scan

    解决凸包问题有多种算法,其中两种常见的方法是Jarvis步进法(Jarvis March)和Graham扫描法(Graham Scan)。 **Jarvis步进法**,又称为包裹法,其基本思想是从点集中选取一个必定在凸包上的点作为起点,然后通过...

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

    首先,凸包的计算通常采用两种经典算法:Graham扫描法和Jarvis步进法。这里我们关注Graham扫描法,其时间复杂度为O(n log n),比Jarvis步进法(O(nh))更适用于点集较大且高度较小的情况。Graham扫描法的基本思路是...

    根据已知顶点求构成凸包的顶点集合

    Graham 扫描法是求解二维凸包的一种经典方法,由 Ronald Graham 在 1972 年提出。以下是该算法的主要步骤: 1. **找到最低点**:首先,我们需要找到点集中角度最小的点,即最左下角的点。这个点将成为凸包的起始点...

    Graham Jarvis两种算法求散点集凸包

    这个算法以电脑科学家Ronald Graham命名,其核心思想是找到散点集中最低的点作为起始点,然后通过旋转扫描线来确定凸包的边界点。具体步骤如下: 1. 找到散点集中的最低点,作为凸包的第一个点。 2. 对其余点按与...

    凸包算法计算随机散点的最小凸包(老外编的)

    凸包算法有多种实现方法,其中最著名的是Graham扫描法、Jarvis步进法和Andrew的扫地机算法。Graham扫描法首先找到所有点中的最低点,然后按照角度排序其余点,接着从最低点开始扫描,剔除那些在当前边与前一条边形成...

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

    Graham扫描法是一种经典的求解凸包的算法,它首先找到所有点中的最低点,然后按照点相对于最低点的顺时针或逆时针顺序排序,最后通过不断去除内凹边界的点,直到所有剩余的点都在凸包上。以下是Graham扫描法的基本...

    计算凸包的graham算法.rar_C++_drinkqx7_凸包_计算凸包

    Graham算法的基本思想是先找到一个点,使得以此点为基准,其余点按逆时针或顺时针方向排序,然后通过一系列的扫描线操作逐步构建出凸包。以下是Graham算法的详细步骤: 1. **选择起点**:首先,从给定点集中选择一...

    分治法解决凸包问题(用C语言递归调用实现)

    ### 分治法解决凸包问题(用C语言递归调用实现) #### 一、引言 本篇文章将深入探讨如何使用分治策略来解决计算几何中的一个经典...此外,还可以考虑使用其他算法如Graham扫描法、Jarvis步进法等,以进一步优化性能。

    vc++二维凸包算法

    例如,使用Graham扫描法的步骤可能如下: 1. 找到最低点,将其设为初始顶点。 2. 将其余点按相对于最低点的角度排序,角度从小到大。 3. 初始化一个空栈,将最低点压入栈。 4. 遍历排序后的点集,对于每个点,如果...

    tubao.zip_凸包_凸包问题

    - 稳定性:某些算法如Graham扫描法是稳定的,即输入点的微小变化不会导致输出凸包的大幅度改变,这对于一些应用至关重要。 - 实现细节:C语言实现需要注意内存管理和计算效率,比如避免不必要的数据拷贝,使用指针...

    最小凸包算法Java版

    4. 凸包构建:核心算法的实现,可能是Graham扫描或Andrew's反向扫描。 5. 鼠标事件处理:允许用户通过鼠标选择点,更新输入的点集。 6. 可视化:显示点集及计算出的凸包,可能是利用Java的Swing或JavaFX库。 代码中...

    DEM两种凸包算法程序 C# .NET

    总结来说,"DEM两种凸包算法程序 C# .NET"是一个专注于C#环境下的数字高程模型处理项目,涵盖了Graham扫描法和Jarvis步进法两种凸包算法的实现。这些算法在地理信息处理、地图渲染、3D建模等领域有着广泛的应用,而...

    算法实验凸包枚举、Graham-Scan、分治三种解决方法

    在本实验中,我们将探讨三种解决凸包问题的方法:枚举法、Graham-Scan算法以及分治策略。下面将对这三种方法进行详细介绍。 首先,枚举法是最直观的一种解决方法。对于给定的一组点,我们可以尝试所有可能的点顺序...

    空间分析最小凸包算法

    描述中提到的"Gramham法"是一种常见的求解凸包的方法,也称为Graham扫描算法。该算法的基本思想是首先找到所有点中最低的三个点,然后按照逆时针或顺时针方向排序其余的点。接着,从这三个点开始,通过逐一检查新...

    VC++MFC实现凸包绘制

    常见的有Graham扫描法、 Jarvis March( gift wrapping)法、Andrew算法等。这些算法都以相对简单的方式找到给定点集的凸包。以Graham扫描法为例,步骤包括: 1. 找到点集中最低的点,作为起始点。 2. 将其余点按照...

    c# WPF实现计算绘制凸包

    // 使用Graham扫描法计算凸包 Stack&lt;Point&gt; hullStack = new Stack(); hullStack.Push(points[0]); hullStack.Push(points[1]); for (int i = 2; i ; i++) { while (hullStack.Count &gt;= 2 && ...

Global site tag (gtag.js) - Google Analytics