博客

算法导论——二维平面上的最邻近点对

  • Post author:
  • Post category:其他



一、   算法设计与分析：

采用分治算法，算法每一次递归调用的输入为点集的子集P，以及数组X和数组Y，由于点击P按X坐标划分，所以不用单独输入X，采用Point.x即可，对数组X中的点排序，使其x坐标坐标单调递增。类似地，对数组Y中的点排序，使其y坐标单调递增。不能再每次递归调用中都进行排序，采用预排序的策略，对Y数组预排序伪代码如下：

Let YL[1…Y.length]and YR[1…Y.length] be new arrays

YL.length=YR.length=0

for i=1 to Y.length

if Y[i] is in PL

YL.length=YL.length+1

YL[YL.length]=Y[i]

else

YR.length=YR.length+1

YR[YR..length]=Y[i]

该算法涉及的数据结构如下： 

//点结构
struct Point{
       Point(){}
       Point(double x, double y){this->x=x;this->y=y;}
       double x;//x坐标
       double y;//y坐标
};
//Y坐标定义
struct axisY{
       int ID;//点编号
       double Yvalue;//y坐标
};

二、算法实现 

//点定义
struct Point{
	Point(){}
	Point(double x, double y){this->x=x; this->y=y;}
	double x;//x坐标
	double y;//y坐标
};
//Y坐标定义
struct axisY{
	int ID;//点编号
	double Yvalue;//y坐标
};

//
bool cmpY(axisY y1, axisY y2){
	return y1.Yvalue<y2.Yvalue;
}
bool cmpPoint(Point p1, Point p2){
	return p1.x<p2.x;
}

#include "compare.h"
#define MAX_NUM 1000
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;
double getMinDis(Point points[], axisY Y[], int left, int right, Point& point1, Point& point2);
double getDisLessThree(Point points[], int start, int end, Point& point1, Point& point2);
double getMinCross(Point points[], axisY Y_2d[],int count, Point& point1, Point& point2);
double getDistance(Point p1,Point p2);

int main(){
	double min;
	Point points[MAX_NUM];//存储所有点,排序后下标表示ID
	//axisX X[MAX_NUM];//存储所有点x坐标
	axisY Y[MAX_NUM];//存储所有点y坐标
	Point point1,point2;
	
	for(int i=0;i<MAX_NUM;i++){
		points[i].x=(rand()/double(RAND_MAX))*100;
		points[i].y=(rand()/double(RAND_MAX))*100;
	}
	
	/*
	//测试数据
	points[0].x=9.83;points[0].y=-81.96;
	points[1].x=-88.29;points[1].y=44.76;
	points[2].x=21.97;points[2].y=-81.49;
	points[3].x=2.44;points[3].y=-1.83;
	points[4].x=-89.17;points[4].y=63.58;
	points[5].x=20;points[5].y=-49.92;
	points[6].x=-81.21;points[6].y=-48.01;
	points[7].x=-33.28;points[7].y=-49.09;
	points[8].x=-54.05;points[8].y=12.88;
	points[9].x=-64.85;points[9].y=-53.12;
	points[10].x=12.07;points[10].y=64.91;
	points[11].x=-72.9;points[11].y=-21.57;
	points[12].x=12.93;points[12].y=-92.71;
	points[13].x=-27.71;points[13].y=-0.19;
	points[14].x=73.17;points[14].y=32.17;
	*/
	sort(points,points+MAX_NUM,cmpPoint);// points按x坐标有序
	for(int i=0;i<MAX_NUM;i++){
		Y[i].ID=i;
		Y[i].Yvalue=points[i].y;
	}
	sort(Y,Y+MAX_NUM,cmpY);
	min=getMinDis(points, Y, 0, MAX_NUM-1,point1, point2);
	cout << "最近点对为：("<< point1.x << "," << point1.y << ")和"<<"("<<point2.x<< "," << point2.y << ")"<< endl;
	cout << "最小距离："<< min << endl;
	return 0;
}

//返回最小距离
double getMinDis(Point points[], axisY Y[], int left, int right, Point& point1, Point& point2){
	int num_point;
	int mid;
	double min,min_left,min_right,min_cross;
	int lenL,lenR;
	Point *PL,*PR;
	axisY *YL,*YR,*Y_2d;
	double xleft,xright;

	num_point=right-left+1;
	Y_2d=new axisY[num_point];//为Y_2d分配存储空间
	if(num_point<=3){         //递归出口
		return getDisLessThree(points, left, right,point1,point2);
	}
	mid=(left+right)/2;
	lenL=mid-left+1;
	lenR=right-mid;
	PL=new Point[lenL];
	YL=new axisY[lenL];
	PR=new Point[lenR];
	YR=new axisY[lenR];
	//求PL
	for(int i=left,j=0;i<=mid;i++){
		PL[j++]=points[i];
	}
	//求PR
	for(int i=mid+1,j=0;i<=right;i++){
		PR[j++]=points[i];
	}
	//求YL和YR
	for(int i=0,jl=0,jr=0;i<num_point;i++){
		if(Y[i].ID<=mid)  //插入YL
			YL[jl++]=Y[i];
		else
			YR[jr++]=Y[i];  //插入YR
	}
	//递归求解
	Point point_L1,point_L2;
	Point point_R1,point_R2;
	min_left=getMinDis(points, YL, left, mid, point_L1, point_L2);
	min_right=getMinDis(points,YR,mid+1,right, point_R1, point_R2);
	min=min_left;point1=point_L1;point2=point_L2;
	if(min_right<min){
		min=min_right;point1=point_R1;point2=point_R2;
	}
	//求Y_2d
	int count=0;
	xleft=points[mid].x-min;
	xright=points[mid].x+min;
	for(int i=0;i<num_point;){
		if((points[Y[i].ID].x<xleft) || (points[Y[i].ID].x>xright)){
			i++;
		}
		else{
			Y_2d[count++]=Y[i];
		    i++;
		}
	}
	//求min_cross;
	Point point_M1,point_M2;
	min_cross=getMinCross(points, Y_2d, count, point_M1, point_M2);
	if(min_cross<min){
		point1=point_M1;point2=point_M2;min=min_cross;
	}
	return min;
}

//返回交叉区域最短距离
double getMinCross(Point points[], axisY Y_2d[],int count, Point& point1, Point& point2){
	double min_across=DBL_MAX;
	double this_min;
	double this_dis;
	int i=0,j=0;
	int p1,p2;
	Point cur_point1,cur_point2;

	if(count==0){
		return min_across;
	}
	for(i=0;i<count;i++){
		this_min=DBL_MAX;
		p1=Y_2d[i].ID;
		cur_point1=points[p1];
		cur_point2=points[p1];
		for(j=1;j<8&&(i+j)<count;j++){
			p2=Y_2d[i+j].ID;
			this_dis=getDistance(points[p1], points[p2]);
			if(this_dis<this_min){
				this_min=this_dis;
				cur_point2=points[p2];
			}
		}
		if(this_min<min_across){
			min_across=this_min;
			point1=cur_point1;
			point2=cur_point2;
		}
	}
	return min_across;
}

//求两点p1和p2之间的距离
double getDistance(Point p1,Point p2){
	double distance;

	distance=sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2));
	return distance;
}

//当点数小于等于三点时暴力求解
double getDisLessThree(Point points[], int start, int end, Point& point1, Point& point2){
	int len;
	double min;

	len=end-start+1;
	if(len==1){
		min=-1;
	}
	else if(len==2){//有两个点
		min=getDistance(points[start], points[end]);
		point1=points[start];
		point2=points[end];
	}
	else{//有三个点
		double dis1,dis2,dis3;

		dis1=getDistance(points[start],points[start+1]);
		dis2=getDistance(points[start],points[end]);
		dis3=getDistance(points[start+1],points[end]);
		min=dis1;
		point1=points[start];point2=points[start+1];
		if(dis2<min){
			min=dis2;
			point1=points[start];point2=points[end];
		}
		if(dis3<min){
			min=dis3;
			point1=points[start+1];point2=points[end];
		}
	}
	return min;
}

三、实验结果分析

先采用经过如下15个点进行测试，如果结果正确最邻近点应为points[12]和

points[0]，最小距离为11.1881

points[0].x=9.83;points[0].y=-81.96;

points[1].x=-88.29;points[1].y=44.76;

points[2].x=21.97;points[2].y=-81.49;

points[3].x=2.44;points[3].y=-1.83;

points[4].x=-89.17;points[4].y=63.58;

points[5].x=20;points[5].y=-49.92;

points[6].x=-81.21;points[6].y=-48.01;

points[7].x=-33.28;points[7].y=-49.09;

points[8].x=-54.05;points[8].y=12.88;

points[9].x=-64.85;points[9].y=-53.12;

points[10].x=12.07;points[10].y=64.91;

points[11].x=-72.9;points[11].y=-21.57;

points[12].x=12.93;points[12].y=-92.71;

points[13].x=-27.71;points[13].y=-0.19;

points[14].x=73.17;points[14].y=32.17;

运行结果如下：

和预期结果一致。

（2）采用如下语句随机生成100对点，寻找其最近点距离：

for(inti=0;i<MAX_NUM;i++){

points[i].x=(rand()/double(RAND_MAX))*100;

points[i].y=(rand()/double(RAND_MAX))*100;

}

结果如下：

（3）随机生成1000对点（坐标不超100）并进行测试，结果如下：

四、总结

根据事先设计好的数据对代码进行测试，测试结果和预期一致，证明了算法的正确性，加大测试数据集，分别采用100对随机点对和1000对随机点对进行测试，发现都能在很快的时间内，证明该算法是极其高效的。

该算法实现过程中，最巧妙的处理是对每个点，只需测试他和后边7个点之间的距离，以及对y坐标进行预排序，大大降低了时间复杂度。该算法实现的难点是对递归的处理，以及在递归调用过程中最近点对的跟踪。经过多次调试，上述问题都得到了解决。


版权声明：本文为xiaowang627原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。