几何问题中的分治法

1.最近对问题

问题描述:

设p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)一共n个点构成点集S，最近点对问题就是找出集合中距离最近的两个点，严格来说最近点对可能多于一个，但我们简单起见只找出一对即可。

算法思路:

(1)划分:将集合S分成两个子集S1和S2，根据平衡子问题原则，每个子集中大约有n/2个点,设集合S的最近点对是pi与pj(1<=i,j<=n),则会出现三种情况。
①pi在S1中，pj在S1中
②pi在S2中，pj在S2中
③pi在S1中，pj在S2中
(2)划分①②可以递归，划分③比较麻烦
(3)合并，比较三种情况取最小值返回即可
下面讨论情况③:

代码:

import org.junit.Test;
public class AVL {//最近点对问题@Testpublic  void Test(){Point p1 = new Point();p1.setX(0.1);p1.setY(0.2);Point p2 = new Point();p2.setX(0.4);p2.setY(0.3);Point p3 = new Point();p3.setX(0.2);p3.setY(0.1);Point points[]=new Point[]{p1,p2,p3};Point[] points_help = new Point[points.length];for(int i=0;i<points.length;i++){points_help[i]=new Point();}//排序横轴sort(points,0,2,0);//验证sort函数for (Point point : points) {System.out.println(point);}System.out.println(MiniDisttance(points,0,2,points_help));}//编写函数将点集按照排序,condition为0表示按照横坐标排序，为1表示按照纵坐标排序int Partition(Point points[],int left,int right,int condtion){int i=left,j=right;Point temp=new Point();temp = points[i];if(condtion==0)while(i<j){while(i<j&&points[j].x>=temp.x)j--;points[i]=points[j];while(i<j&&points[i].x<=temp.x)i++;points[j]=points[i];}else{while(i<j){while(i<j&&points[j].y>=temp.y)j--;points[i]=points[j];while(i<j&&points[i].y<=temp.y)i++;points[j]=points[i];}}points[i]=temp;return i;}void  sort(Point points[],int left,int right,int condtion){if(left<right){int partition = Partition(points, left, right, condtion);sort(points,left,partition-1,condtion);sort(points,partition+1,right,condtion);}}//在使用MiniDistance函数之前我们假设points已经按照x排好序了double MiniDisttance(Point points[],int left,int right,Point points_help[]){//如果只有两个点返回即可if(right-left==1){getDistance(points[left],points[right]);}//如果有三个点else if(right-left==2){double d1 = getDistance(points[left],points[left+1]);double d2 = getDistance(points[left+1],points[left+2]);if(d1<d2){return d1;}elsereturn d2;}int mid = (left+right)/2;//最近点对在左半边double d1 = MiniDisttance(points,left,mid,points_help);//最近点对在右半边double d2 = MiniDisttance(points,mid+1,right,points_help);//比较d1与d2的大小double d;if(d1<d2)d= d1;elsed= d2;//接下来寻找在mid左右两边都为d范围内的点并并将其保存double mid_left = points[mid].x-d;double mid_right = points[mid].y+d;int index =0;//收集P1与P2的点for(int i=mid-1;i>=left;i--){if(points[mid].x-points[i].x<=d)points_help[index++]=points[i];elsebreak;}for(int j=mid+1;j<=right;j++){if(points[j].x-points[mid].x<=d){points_help[index++]=points[j];}elsebreak;}//现在已经收集好了我们将其按照y轴的方向从小到大排序sort(points_help,0,index-1,1);for(int i=0;i<index;i++){for(int j=i+1;j<index;j++){if(getDistance(points_help[i],points_help[j])<d)d=getDistance(points_help[i],points_help[j]);elsebreak;}}return d;}double getDistance(Point p1,Point p2){return Math.sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}
}class Point{public void setX(double x) {this.x = x;}@Overridepublic String toString() {return "Point{" +"x=" + x +", y=" + y +'}';}public void setY(double y) {this.y = y;}double x;double y;}

输出:

2.凸包问题

问题描述：设p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n个点构成的集合S,凸包问题是为集合S构造最小凸多边形。


由于最近比较忙碌，就先介绍到这吧，后续有空会补上代码