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

学习凸包(二):分治法求解

阅读更多
接上文:学习凸包(一):暴力算法求解http://128kj.iteye.com/blog/1748442





import java.util.*;   
class Line {//线   
 Point p1, p2;   
 Line(Point p1, Point p2) {   
  this.p1 = p1;   
  this.p2 = p2;   
 }   

  public double getLength() {
	double dx = Math.abs(p1.x - p2.x);
	double dy = Math.abs(p1.y - p2.y);
	return Math.sqrt(dx * dx + dy * dy);
  }

}   
  
class Point{//点   
  double x;   
  double y;   
  
  public Point(double x,double y){
     this.x=x;
     this.y=y;
  }
}   


/*
*	分治法求凸包
*/
class QuickTuBao  {
  List<Point> pts = null;//给出的点集
  List<Line> lines = new ArrayList<Line>();//点集pts的凸包
	
  public void setPointList(List<Point> pts) {
      this.pts = pts;
  }

  public QuickTuBao(List<Point> pts){
      this.pts=pts;
  }

  //求凸包,结果存入lines中
  public List<Line> eval() {
      lines.clear();
      if (pts == null || pts.isEmpty()) { return lines; }
        List<Point> ptsLeft = new ArrayList<Point>();//左凸包中的点
          List<Point> ptsRight = new ArrayList<Point>();//右凸包中的点
		
        //按x坐标对pts排序
         Collections.sort(pts, new Comparator<Point>() {
             public int compare(Point p1, Point p2) {
              if(p1.x-p2.x>0) return 1;
              if(p1.x-p2.x<0) return -1;
              return 0;
             } 
			
		});  
         
            Point p1 = pts.get(0);//最左边的点
            Point p2 = pts.get(pts.size()-1);//最右边的点,用直线p1p2将原凸包分成两个小凸包
            Point p3 = null;
            double area = 0;
            for (int i = 1; i < pts.size(); i++) {//穷举所有的点,
              p3 = pts.get(i);
              area = getArea(p1, p2, p3);//求此三点所成三角形的有向面积
                if (area > 0) {		
                 ptsLeft.add(p3);//p3属于左
                } else if (area < 0) {
                  ptsRight.add(p3);//p3属于右
                }
              }
              d(p1, p2, ptsLeft);//分别求解
              d(p2, p1, ptsRight);
              return lines;
   }

   private void d(Point p1, Point p2, List<Point> s) {
     //s集合为空
     if (s.isEmpty()) {
       lines.add(new Line(p1, p2));
       return;
     }
     //s集合不为空,寻找Pmax
     double area = 0;
     double maxArea = 0;
     Point pMax = null;
     for (int i = 0; i < s.size(); i++) {
      area = getArea(p1, p2, s.get(i));//最大面积对应的点就是Pmax
      if (area > maxArea) {
        pMax = s.get(i);
        maxArea = area;
       }
      }
      //找出位于(p1, pMax)直线左边的点集s1
      //找出位于(pMax, p2)直线左边的点集s2
       List<Point> s1 = new ArrayList<Point>();
       List<Point> s2 = new ArrayList<Point>();
       Point p3 = null;
       for (int i = 0; i < s.size(); i++) {
         p3 = s.get(i);
         if (getArea(p1, pMax, p3) > 0) {
            s1.add(p3);
         } else if (getArea(pMax, p2, p3) > 0) {
            s2.add(p3);
         } 
        }
       //递归
       d(p1, pMax, s1);
      d(pMax, p2, s2);	
    }
	// 三角形的面积等于返回值绝对值的二分之一
	// 当且仅当点p3位于直线(p1, p2)左侧时,表达式的符号为正
	private double getArea(Point p1, Point p2, Point p3) {
           return p1.x * p2.y + p3.x * p1.y + p2.x * p3.y -
             p3.x * p2.y - p2.x * p1.y - p1.x * p3.y;
	}
}


代码来自:http://blog.163.com/maxupeng@yeah/

未完,待续.....
  • 大小: 16.5 KB
  • 大小: 28.8 KB
0
0
分享到:
评论

相关推荐

    高级算法设计实验1分治算法:求解凸包问题

    求解凸包问题:输入是平面上 n 个点的集合 Q,凸包问题是要输出一个 Q 的 凸包。其中,Q 的凸包是一个凸多边形 P,Q 中的点或者在 P 上或者在 P 中。 实现基于枚举方法的凸包求解算法...实现基于分治思想的凸包求解算法

    分治法求解凸包问题

    利用分治法求解凸包问题!c语言 #include #define PPmax 30 #define random(x) (rand()%x) typedef struct node{ float x,y; }Point; Point DingDian[PPmax];//用于存放凸边形的顶点 int DingDnum=0; typedef ...

    分治法解凸包问题

    ### 分治法解凸包问题 #### 背景与定义 在计算机科学与几何算法领域,凸包问题是一项基础而重要的课题。简单来说,给定一个点集,凸包是指包含这些点的所有凸多边形中周长最小的一个。在实际应用中,凸包的应用...

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

    ### 分治法解决凸包问题(用C语言递归调用实现) #### 一、引言 本篇文章将深入探讨如何使用分治策略来解决计算几何中的一个经典问题——凸包问题,并通过C语言实现这一算法。凸包问题是计算几何中的一个基本问题...

    凸包分治法

    ### 凸包分治法知识点解析 #### 一、引言 在计算机科学与图形学领域,凸包问题是一项基础而重要的课题。凸包是指在二维平面上,给定一组...理解并掌握分治法求解凸包的方法对于深入学习这些领域的知识具有重要意义。

    fenzhi_分治法求凸包_

    在本主题中,我们将讨论如何利用分治法来求解二维平面上散乱点集的凸包问题。 凸包是一组点在二维空间中的最小凸多边形,该多边形包含所有点并且与这些点没有交点。在几何计算、图像处理、机器学习等领域,求解凸包...

    分治法凸包问题

    分治法求解凸包问题,能够运行的出来,已运行调试过

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

    3. **QuickHull算法**:这是一种类似于快速排序的分治算法,通过不断分割空间直到每个子空间中只包含一个点,从而达到求解凸包的目的。这种方法在最坏情况下具有较高的效率,但实际应用中可能不如其他方法稳定。 在...

    1.理解枚举算法 2.利用枚举算法实现简单问题编程求解

    因此,对于大规模问题,通常需要寻找更高效的方法,如动态规划、贪心策略或分治法。 文件列表中的《枚举算法》学案.docx可能包含详细的教学材料,解释了枚举算法的基本概念、步骤和示例。枚举算法.mp4可能是一个...

    分治法(算法竞赛,ACM程序设计)

    **分治法**是一种在计算机科学中广泛应用的算法设计策略,尤其在算法竞赛和ACM程序设计...这个压缩包中的“2分治法”很可能包含了一系列关于分治法的课件、练习题和解题策略,对于系统学习和掌握分治法有着极大的帮助。

    算法设计与分析课件-第四章 分治法.ppt

    2. **查找**:分治法可用于二分查找,通过不断将查找区间减半,快速定位目标元素。 3. **大整数乘法**:如Karatsuba算法利用分治法减少了乘法运算的次数,提高了效率。 4. **矩阵乘法**:Strassen算法通过分解矩阵...

    Convex_hull_problem.rar_凸包问题_凸包问题穷举

    分治法和穷举法是解决凸包问题的两种常见策略。 **分治法**: 分治法是一种将大问题分解为小问题来解决的策略。在处理凸包问题时,可以采用Graham扫描算法,这是分治法的一个实例。首先,找到最低的点作为起点,...

    2015300005_黄晓阳_计算几何算法与应用大作业1

    3. **用分治法求解凸包问题的策略**:应用分治法解决凸包问题,首先将点集映射到二维坐标系中,找到x轴或y轴的最大值和最小值点作为初始的分割点。以最大x值点P1和最小x值点P2为界,将点集分为上半部分和下半部分。...

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

    此外,还有分治法(Divide and Conquer)、Akl-Toussaint启发式算法等其他方法用于求解凸包问题。分治法通过将问题分解为较小的部分来降低计算复杂度,而Akl-Toussaint启发式算法则尝试减少旋转次数,提高效率。 ...

    基于分治法和分支限界法的大规模TSP算法 (2012年)

    该算法利用聚类和凸包技术将大规模问题逐层进行有效划分,直到适合分支限界法求解的最佳规模;然后用分支限界法求出每个子问题和每层子问题间的最优解,合并而得到整个问题的解。比较实验表明:该算法在求解质量、稳定性...

    蛮力法姊妹篇 | Python分治法解决凸包问题并用matplotlib实现可视化以及与蛮力法的对比

    之前写了一篇Python蛮力法解决凸包问题并用matplotlib实现可视化,最后也给出了同样是在1000个点的情况下蛮力法和分治法的差距有多大(蛮力法1154秒,分治法0.125秒…) 先解释一下为什么吧: 因为蛮力法的重点在于...

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

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

    蛮力法实现最近对,凸包,选择排序,冒泡排序

    虽然有更高效的算法(如平分线段树或分治法),但蛮力法提供了一个简单的起点。 最近对问题,是计算几何中的一个经典问题,要求在二维空间中找出一组点中距离最近的两点。蛮力法的解决方案会计算每一对点之间的...

    java-convexhull:Java实现od凸包算法

    Java 实现的 Convex Hull(凸包)算法是一种在计算机科学中常见的几何算法,用于找出一组给定点在二维平面上的最小凸多边形,该多边形包含所有点。这个算法在各种应用中都有用到,比如路径规划、图像处理、机器学习...

    自己手写的凸包程序,用vc6.0实现

    【描述】:“用vc6.0编写的凸包求解程序,复杂度n*logn,递归实现” VC6.0是微软发布的一款经典且功能强大的C++集成开发环境,虽然现在已被更新的版本取代,但它仍然是许多程序员学习和开发的重要工具。描述中提到...

Global site tag (gtag.js) - Google Analytics