《算法导论》实验五：最近点对算法（C++）

一、题目描述

在n>=2个点的集合Q中寻找最近点对。
“最近”是指通常意义下的欧几里得距离：即点p1（x1，y1）和p2（x2，y2）之间的距离为：sqrt（（x1-x2）2 +（y1-y2）2）。

二、算法设计与分析

算法主要思想就是分治。
情况1：点数小于等于二时：直接计算，求该两点之间的距离。
情况2：集合中有三个点：两两比较，求三个点中的最近的两个点距离。
情况3：点数大于三时：首先划分集合S为SL和SR，使得SL中的每一个点位于SR中每一个点的左边，并且SL和SR中点数相同。分别在SL和SR中解决最近点对问题，得到DL和DR，分别表示SL和SR中的最近点对的距离。令d=min(DL,DR)。如果S中的最近点对(P1,P2)。P1、P2两点一个在SL和一个在SR中，那么P1和P2一定在以L为中心的间隙内，以L-d和L+d为界。
如下图-1所示：

图-1 点数大于三时时分治

如果在SL中的点P和在SR中的点Q成为最近点对，那么P和Q的距离必定小于d。因此对间隙中的每一个点，在合并步骤中，只需要检验yp+d和yp-d内的点即可。
步骤1：根据点的y值和x值对S中的点排序。
步骤2：找出中线L将S划分为SL和SR
步骤3：将步骤2递归的应用解决SL和SR的最近点对问题，并令d=min(dL,dR)。
步骤4：将L-d~L+d内的点以y值排序，对于每一个点(x1,y1)找出y值在y1-d~y1+d内的接下来的7个点，计算距离为d’。如果d’小于d，令d=d’，最后的d值就是答案。

三、实验结果与分析

本实验的所用到的测试用例是用随机函数生成的，所以每次的测试用例都有所不同。但可通过控制台设定需要测试点的个数N。
(一)、当点个数N=1时（输入不合理）。见下图-2：

图-2 N=1时（输入不合理）

(二)、当点个数N=2时，见下图-3：

图-3 N=2的输出结果

(三)、当点个数N=3时，见下图-4：

图-4 N=3的输出结果

(四)、当点个数N>3时，见下图-5：

图-5 N=15的输出结果

四、实验总结

1、 采用分治法寻找最近点对时，相较于寻找一维的最近点来说，二维的最近点对寻找要困难许多，难点在于分界线周围的点的处理，即跨分治区域的点的比较。
2、 可证明，处理δ*2δ区间内的点时，只需处理与当前点递增相连的7个点即可。因此可以大大减少开销，提高算法效率，改进算法时间复杂度。
3、 可对点对进行预排序，即在第一次递归调用前，对所有的点进行排序。预排序使运行时间增加了O(nlogn)，但这样一来，除递归调用外，递归过程的每一步仅需线性时间。因此算法的整个时间复杂度为O(nlogn)。

五、源代码（C++）

#include <iostream>  
#include <ctime>
#include <cmath>
#include <algorithm>

using namespace std; #define NO_DISTANCE 1000000

//定义二维点Point
typedef struct Point 
{ float x,y; //二维点的横纵坐标，范围均为[-100,100]
}Point;

//用随机函数对点数组points中的二维点进行初始化
void SetPoints(Point *points,int length)
{ srand(unsigned(time(NULL)));  //设置随机种子 for(int i=0;i<length;i++) { points[i].x=(rand()%20000)/100.0-100; //调整rand(),使得横纵坐标范围为[-100,100] points[i].y=(rand()%20000)/100.0-100; }

}

//平面上任意两点对之间的距离公式计算
float Distance(Point a,Point b)
{ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

//自定义排序规则：依照结构体中的x成员变量升序排序
bool CmpX(Point a,Point b)
{ return a.x<b.x;
}

//求出最近点对记录，并将两点记录再a、b中
float ClosestPair(Point points[],int length,Point &a,Point &b)
{ float distance; //记录集合points中最近两点距离  float d1,d2; //记录分割后两个子集中各自最小点对距离 int i=0,j=0,k=0; //用于控制for循环的循环变量 Point a1,b1,a2,b2; //保存分割后两个子集中最小点对 if(length<2)return NO_DISTANCE; //若子集长度小于2，定义为最大距离，表示不可达 if(length==2) { a=points[0]; b=points[1]; distance=Distance(points[0],points[1]); } else { Point *pts1=new Point[length]; //开辟两个子集 Point *pts2=new Point[length]; sort(points,points+length,CmpX);   //调用algorithm库中的sort函数对points进行排序，CmpX为自定义的排序规则 float mid=points[(length-1)/2].x;  //排完序后的中间下标值，即中位数 for(i=0;i<length/2;i++) pts1[i]=points[i]; for(int j=0,i=length/2;i<length;i++) pts2[j++]=points[i]; d1=ClosestPair(pts1,length/2,a1,b1); //分治求解左半部分子集的最近点   d2=ClosestPair(pts2,length-length/2,a2,b2); //分治求解右半部分子集的最近点   if(d1<d2) { distance=d1; a=a1; b=b1;} else { distance=d2; a=a2; b=b2;} //求解跨分割线并在δ×2δ区间内的最近点对 Point *pts3=new Point[length]; for(i=0,k=0;i<length;i++) if(abs(points[i].x-mid)<=distance)pts3[k++]=points[i]; for(i=0;i<k;i++) for(j=i+1;j<=i+7&&j<k;j++) //只需与有序的领接的的7个点进行比较 { if(Distance(pts3[i],pts3[j])<distance) {//如果跨分割线的两点距离小于已知最小距离，则记录该距离 distance=Distance(pts3[i],pts3[j]); a=pts3[i]; b=pts3[j]; } } } return distance;
}

int main()
{ int N; //随机生成的点对个数 Point a,b; float diatance; cout<<"请您输入二维点对个数："; cin>>N; if(N<2) cout<<"请输入大于等于2的点个数！！"<<endl; else { cout<<endl<<"随机生成的"<<N<<"个二维点对如下："<<endl; Point *points=new Point[N]; SetPoints(points,N); for(int i=0;i<N;i++) cout<<"("<<points[i].x<<","<<points[i].y<<")"<<endl; diatance=ClosestPair(points,N,a,b); cout<<endl<<endl<<"按横坐标排序后的点对:"<<endl; for(int i=0;i<N;i++) { cout<<"("<<points[i].x<<","<<points[i].y<<")"<<endl; } cout<<endl<<"最近点对为："<<"("<<a.x<<","<<a.y<<")和"<<"("<<b.x<<","<<b.y<<")"<<endl<<"最近点对距离为："<<diatance<<endl; } system("pause");
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
 

文章来源: blog.csdn.net，作者：allinallinallin，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/to_Baidu/article/details/50315607