`
128kj
  • 浏览: 600167 次
  • 来自: ...
社区版块
存档分类
最新评论

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

阅读更多
Graham扫描法

   基本思想:通过设置一个关于候选点的堆栈来解决凸包问题。

   操作:输入集合P中的每一个点都被压入栈一次,非凸包中的顶点的点最终将被弹出堆栈,
当算法终止时,堆栈中仅包含凸包中的顶点,其顺序为个各顶点在边界上出现的逆时针方向排列的顺序。


(1)设P0是P中Y坐标最小的点,如果有多个这样的点则取最左边的点作为P0;

(2) 设<P1,P2,……,Pn >是P中剩余的点,对其按逆时针方向相对P0 的极角进行排序,
如果有数个点有相同的极角,则去掉其余的点,只留下一个与P0 距离最远的那个点;

(3)
//前三个点先入栈 
    ch[0] = p[0];
    ch[1] = p[1];
    ch[2] = p[2];

//判断与其余所有点的关系  
   for (int i = 3; i < n; i++) {
    //不满足向左转的关系,栈顶元素出栈  
    while (top > 0 && multiply(p[i], ch[top], ch[top - 1]) >= 0)
        top--;
        //当前点与栈内所有点满足向左关系,因此入栈.
        ch[++top] = p[i];
   }

原理:沿逆时针方向通过凸包时,在每个顶点处应该向左转。因此,while循环每次发现在一个顶点处没有向左转时,就把该顶点从堆栈中弹出。)当算法向点pi推进、在已经弹出所有非左转的顶点后,就把pi压入堆栈中。


下面是POJ1113的AC代码:关于POJ1113请参见http://128kj.iteye.com/blog/1748635
import java.util.Scanner;

 class Point { 
    double x; 
    double y; 

    public Point(int x, int y) { 
       this.x = x; 
       this.y = y; 
    } 
 } 

public class Main { 
      Point[] ch; //点集p的凸包
      Point[] p ; //给出的点集
      int n;
      int l;
      int len=0;

     public Main(Point[] p,int n,int l){
        this.p=p;
        this.n=n;
        this.l=l;
        ch= new Point[n]; 
     }

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

    //求距离
    public  double distance(Point p1, Point p2) { 
        return (Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) 
                * (p1.y - p2.y))); 
    } 

    public void answer(){
     double sum = 0; 
        for (int i = 0; i < len - 1; i++) { 
            sum += distance(ch[i], ch[i + 1]); 
        } 
        if (len > 1) { 
            sum += distance(ch[len - 1], ch[0]); 
        } 
        sum += 2 * l * Math.PI; 
        System.out.println(Math.round(sum)); 
    }

    public  int Graham_scan() { 
        int k = 0, top = 2; 
        Point tmp; 

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

        //按极角从小到大,距离偏短进行排序   
        for (int i = 1; i < n - 1; i++) { 
            k = i; 
            for (int j = i + 1; j < n; j++) 
                if ((multiply(p[j], p[k], p[0]) > 0) 
                        || ((multiply(p[j], p[k], p[0]) == 0) && (distance( 
                                p[0], p[j]) < distance( 
                                p[0], p[k])))) 
                    k = j; //k保存极角最小的那个点,或者相同距离原点最近  
            tmp = p[i]; 
            p[i] = p[k]; 
            p[k] = tmp; 
        } 

        //前三个点先入栈  
        ch[0] = p[0]; 
        ch[1] = p[1]; 
        ch[2] = p[2]; 

         //判断与其余所有点的关系   
        for (int i = 3; i < n; i++) { 
             //不满足向左转的关系,栈顶元素出栈   
            while (top > 0 && multiply(p[i], ch[top], ch[top - 1]) >= 0) 
                top--; 

             //当前点与栈内所有点满足向左关系,因此入栈. 
            ch[++top] = p[i]; 
        } 
        len=top+1;
        return len; 
    } 
   
    public static void main(String[] args)  { 
     
        Scanner in=new Scanner(System.in);
        int n = in.nextInt(); 
        int l = in.nextInt();
        int x, y; 
        Point[] p = new Point[n]; 
        for (int i = 0; i < n; i++) { 
            x = in.nextInt(); 
            y = in.nextInt();
            p[i] = new Point(x, y); 
        } 
       
      Main ma=new Main(p,n,l); 
      ma.Graham_scan(); 
        ma.answer();
    } 

} 




  • 大小: 38.1 KB
0
0
分享到:
评论

相关推荐

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

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

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

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

    学习凸包(三):凸包练习 POJ 1113

    1. **Graham扫描法**:这是最简单的凸包算法之一,首先选择一个点作为起点,然后按照点的顺时针或逆时针极角排序,接着逐步构建凸包。每次添加一个点时,如果它不破坏凸性,则保留;否则,删除之前的一个点。 2. **...

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

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

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

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

    学习凸包(一):暴力算法求解

    为了提高效率,人们开发了更高级的算法,如Graham扫描、Jarvis步进法、Andrew's算法等,它们的时间复杂度可以降低到O(n log n)。然而,对于小规模的数据集,简单的暴力算法仍然是一个可接受的解决方案。 总之,这篇...

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

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

    最小凸包算法Java版

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

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

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

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

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

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

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

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

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

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

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

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

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

    空间分析最小凸包算法

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

    tubao.zip_凸包_凸包问题

    2. Graham扫描法:首先,找到点集中的最低点(最小y坐标,如果相同则取最小x坐标),然后按照点与最低点的极角排序。之后,使用一个栈来维护当前凸包的边,遍历排序后的点,对于每个点,如果它与栈顶两点形成的向量...

    求凸包及其直径

    对于给定的点集,求解凸包的方法有很多种,其中最著名的两种是格拉姆-舒尔茨(Graham's Scan)算法和 Jarvis March(也称为gift wrapping 或刺探法)。Graham's Scan首先找到一个最低点作为起点,然后按照角度排序...

    vc++二维凸包算法

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

Global site tag (gtag.js) - Google Analytics