2.9 二维最近点对问题

2.9.1 问题描述

问题描述：二维平面上有n个点，如何找到距离最近的点？

2.9.2 暴力求解

1 算法思路

二维平面上有n个点，则有(n-1)+(n-1)+...+1=n(n-1)/2个点对，依次遍历求出所有点对的距离即可。

2 时间复杂度分析

由1分析可知，即总共要求出n(n-1)/2个距离，故时间复杂度O(n^2)

2.9.3 分治法求解

1 算法思路

核心思想：

  • 数据预处理
  • 划分中轴线
  • 求出左边的最小距离
  • 求出右半边的最小距离
  • 求出中间的最小距离
  • 比较这三个最小距离

① 数据预处理
因为这些点的位置是随机产生并保存在二维数组中，所以我们得先将这些点，按照x坐标从小到大排序，调整它们在二维数组中的次序。比如：最左边的点，它的位置就保存在二维数组的第一个元素中；

② 划分中轴线
把这些点在平面上分成左右两边。
问：依据什么来划分中轴线？
答：选择最中间的两个元素，求出它俩x坐标的平均值，设置为中轴线的坐标。

③ 求半边最小距离
左半边和右半边的求最小距离的方法是一样的。
假如我们现在求的是左半边，那就把左半边也看成一个整体，我们再把它分成左右两半，依次往下递归，越分越小。
问：递归何时中止？
答：分到点只剩很小的时候就终止，比如本文在后面附加的代码中，是当平面只剩下4个点时就不再切分。

④ 求中间的最小距离
问：中间区域应该划分多宽？
答：我们只需要考查中轴线左右两边距离小于d的点。理由是，距离中轴线大于d的那些点，它们和另一个半边的点的距离，肯定大于d，考查他们就没有意义了。

那么，现在我们只需要对上图的左侧2个点和右侧4个点分别进行比较即可。

如何进一步优化？
比如我们现在选取了左侧的m点，但实际上，我们不必跟右侧的4个点都比较，只需跟右侧的阴影部分(d*2d)以内的点进行比较，也就是，跟m点垂直距离在d以内的那两个点。
原因：如果两点之间垂直距离大于d，那么这两点间距必然大于d，考查他们也没有意义。

关于矩形的进一步说明
如果查阅过其他资料，或许你听过，我们划分出的dx2d区域中，最多只能有6个点。
因为我们已知两侧的最小距离为d，而d*2d的区域中的点是同一侧的。因此这些点的距离必然大于等于d，经过数学几何知识，我们可以算出这个区域最多只能有6个点。

2 时间复杂度分析

时间复杂度：O(nlog2n)

2.9.4 代码实现

① 数据预处理
在这里，我是采用了效率较高的快速排序算法。
具体的代码，请见2.6.2节快速排序

② 分治法

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
public static double getByDivideConquer(double[][] points) {
	if(points.length==1|points.length==0) {
		return 0;
	}
	double[][] pointsSorted=quickSort(points);
	int head=0;
	int tail=pointsSorted.length-1;
	int [] minIndex=getByDivideConquer(pointsSorted,head,tail);
	double minDist=getDistance(pointsSorted,minIndex[0],minIndex[1]);
	return minDist;
}
private static int[] getByDivideConquer(double[][] points, int head, int tail) {
	double minDist=getDistance(points,head,head+1);//初始化最小距离
	int [] minIndex=new int[] {head,head+1};//初始化最小点对序号
	if(tail-head+1<=4) {//点数小于等于4时
		for(int i=head;i<=tail-1;i++) {//遍历求距离
			for(int j=i+1;j<=tail;j++) {
				if(getDistance(points,i,j)<minDist) {
				/*核心代码*/
					minDist=getDistance(points,i,j);
					minIndex[0]=i;
					minIndex[1]=j;
				}
			}
		}
	}else {
		int [] minIndexLeft=getByDivideConquer(points,head,head+(tail-head)/2);
		int [] minIndexRight=getByDivideConquer(points,head+(tail-head)/2+1,tail);
		double minDisLeft=getDistance(points,minIndexLeft[0],minIndexLeft[1]);
		double minDisRight=getDistance(points,minIndexRight[0],minIndexRight[1]);
		double minDisTwoSide=Math.min(minDisLeft, minDisRight);//即d
		if(minDisLeft>=minDisRight) {
			minDist=minDisRight;
			minIndex=minIndexRight;
		}else {
			minDist=minDisLeft;
			minIndex=minIndexLeft;
		}
		double middleAxis=(points[head+(tail-head)/2][0]+points[head+(tail-head)/2+1][0])/2;//设置中间线，该变量为中间线的x轴坐标
		int i=head+(tail-head)/2+1;//中间线右边的点
		/*核心代码*/
		while(i<=tail&&(points[i][0]-middleAxis<minDisTwoSide)) {//i点没越界且和中间线的x轴距离小于d
			{
				int count=0;
				for(int j=head+(tail-head)/2;j>=head&&(points[j][0]-middleAxis<minDisTwoSide)&&(count<=6);j--) {//j点没越界且符合条件的个数小于6
					if(Math.abs(points[][1]-points[j][1])<minDisTwoSide) {//找出d*2d矩形的点
						if(getDistance(points,i,j)<minDist) {
							minDist=getDistance(points,i,j);
							minIndex[0]=i;
							minIndex[1]=j;
						}
					count++;
					}
				}
				i++;
			}
		}
	}
	return minIndex ;
}
   /////////////////////////////////////////////
//计算点i和点j的距离
private static double getDistance(double[][] points, int i, int j) {
	double dis=Math.sqrt(Math.pow(points[i][0]-points[j][0], 2)+Math.pow(points[i][1]-points[j][1], 2));
	return dis;
}