分治法求最近点对

  • W6_603476
    了解作者
  • 5.1KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-04-11 04:06
    上传日期
资源位分治法求最近点对,包含几种算法,以及图形界面,是一套完整的工程。全部为java实现。
src.rar
  • src
  • FrameRe.java
    3.9KB
  • NearestPointMan.java
    614B
  • Point.java
    424B
  • NearestPoint.java
    4.6KB
  • mainDivideConquer.java
    120B
  • test.java
    852B
  • test.class
    863B
  • MouseDrawPoint.java
    1020B
内容介绍
import java.util.Arrays; public class NearestPoint { /** * @param args */ // public static void main(String[] args) { // // TODO Auto-generated method stub // // Point[] Points = new Point[10]; // // Points[0] = new Point(3, 4); // Points[1] = new Point(2, 5); // Points[2] = new Point(3, 8); // Points[3] = new Point(13, 9); // Points[4] = new Point(7, 8); // Points[5] = new Point(7, 12); // Points[6] = new Point(90, 0); // Points[7] = new Point(5, 8); // Points[8] = new Point(7, 9); // Points[9] = new Point(3, 6); // //Points[10] = new Point(3,41); // // Arrays.sort(Points);//按照x坐标升序对点预排序,n*log(n)的复杂度---Arrays提供的静态排序方法 // // Point[] result = new Point[2]; // result = getNearestPoints(Points); // System.out.println("输出距离最近的两个点是: "); // //System.out.println(result[0].x); // for (int i = 0; i < result.length; i++) // System.out.print("(" + result[i].x + "," + result[i].y + ") "); // } public static Point[] getNearestPoints(Point[] Points) { //从一个点数组里面找到最近的两个点,并返回这两个点 Point[] result = new Point[2]; if (Points.length == 3 || Points.length == 2) //递归结束的条件 result = getNear(Points); else //多于3个点,分治,分别找出两个子集合的最近点对,然后合并结果 { Point[] left = Arrays.copyOfRange(Points, 0, Points.length / 2);//最后一个下标不包括 Point[] right = Arrays.copyOfRange(Points, Points.length / 2, Points.length); //得到2个子集里面分别最短距离的2个点 Point[] result1 = getNearestPoints(left); Point[] result2 = getNearestPoints(right); double d1 = dPoints(result1[0], result1[1]); double d2 = dPoints(result2[0], result2[1]); //忘了将result赋值 if (d1 <= d2) result = result1; else result = result2; //合并结果:找到全局距离最短的两个点 double dmin = Math.min(d1, d2); int x1 = left.length - 1;//两个x的分界点 int x2 = x1 + 1; //在Points.length/2是一个整数时是错误的 //int x1 = Points[Points.length/2 - 1].x;//两个x的分界点 //int x2 = Points[Points.length/2].x; for (int i = x1; i >= 0; i--) { //if(x2 - Points[i].x > dmin) //直接导致调试很久都不知道错在哪!!!!!! if (Points[x2].x - Points[i].x > dmin) break; else //for(int j = Points.length/2;j < Points.length;j++) for (int j = x2; j < Points.length; j++) { //System.out.println(Points[j].y); //if(Points[j].x - x1 > dmin) if (Points[j].x - Points[x1].x > dmin) break; else { double temp = dPoints(Points[i], Points[j]); //System.out.println(temp); if (temp < dmin) { dmin = temp; result[0] = Points[i]; result[1] = Points[j]; } } } } } return result; } private static Point[] getNear(Point[] Points) { //返回仅有2个点或者三个点的点数组中距离最小的两个点 Point[] result = new Point[2]; if (Points.length == 2) result = Points; else //有3个点,枚举求距离最短的两个点 { double d1 = dPoints(Points[0], Points[1]); double d2 = dPoints(Points[0], Points[2]); double d3 = dPoints(Points[1], Points[2]); if (d1 <= d2 && d1 <= d3) { result[0] = Points[0]; result[1] = Points[1]; } else if (d2 <= d3) { result[0] = Points[0]; result[1] = Points[2]; } else { result[0] = Points[1]; result[1] = Points[2]; } } return result; } private static double dPoints(Point a, Point b) { //求两个点之间的距离 return Math.pow(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2), 0.5); } }
评论
    相关推荐
    • SVM 算法 java 实现
      SVM 算法 java 实现了调用接口,只要传入数据即可,调用了encog这个开源包的SVM算法,也是官方libsvm的。
    • 经典算法Java实现
      包括JAVA的经典算法和实现,用于JAVA的学习和研究
    • 遗传算法java工程
      工程利用遗传算法解决多路复用器的模拟状态,里面有充分的技术文档(英语)以及代码注释,自己写的,用不到了以后。贡献出来给大家。
    • LRU算法 java实现
      LRU算法java实现
    • 国密算法java实现
      国家商用密码管理局公布的标准国密算法SM4的算法实现哦
    • 遗传算法java实现
      本代码为Java实现的遗传算法,压缩包中有详细的说明,希望对各位有帮助
    • SVM 算法 java版本
      SVM 算法 java 实现了调用接口,只要传入数据即可,调用了encog这个开源包的SVM算法,也是官方libsvm的。
    • AHP算法java实现
      java实现AHP算法,包括文档说明,算法介绍等ppt文档 欢迎使用
    • DES算法Java实现
      DES算法Java代码实现,适用于学生交作业
    • tomasulo算法java实现
      自己用java实现的一个简单的tomasulo算法的实现对,并且做了界面,有助于对tomasulo算法有一个更好的了解