java实现分治法，求平面内最近点对

2019-11-08 01:15:07

字体：大中小

来源：转载

供稿：网友

算法分析：

方法一：穷举

1）算法描述：已知集合S中有n个点，一共可以组成n(n-1)/2对点对，蛮力法就是对这n(n-1)/2对点对逐对进行距离计算，通过循环求得点集中的最近点对2）算法时间复杂度：算法一共要执行 n(n-1)/2次循环，因此算法复杂度为O(n²)

代码实现：

利用两个for循环可实现所有点的配对,每次配对算出距离然后更新最短距离.

方法二：分治

在二维空间里，可用分治法求解最近点对问题。预处理：分别根据点的x轴和y轴坐标进行排序，得到X和Y,很显然此时X和Y中的点就是S中的点。

情况（1）：点数小于等于三时：

情况（2）：点数大于三时：首先划分集合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为界，如下图所示： %20 %20 %20 %20 %20 %20 %20 %20 %20 %20 %20

如果在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内的所有点，计算距离为d'。如果d'小于d，令d=d'，最后的d值就是答案。

代码如下：

import java.util.Arrays;// 提供一个静态方法返回平面内最近点对：public static Point[] nearest(Point[] array)// 其他的方法皆为私有的助手方法public class NearestPoint {	// 返回给定点集中的最近点对，如果只有一个点，则返回只包含一个点的数组	public static Point[] nearest(Point[] array) {		Point[] cpArray = Arrays.copyOfRange(array, 0, array.length);		SortComparable.sort(cpArray);		return mergeNearest(cpArray, 0, cpArray.length - 1);	}	// 分治求最近点对	PRivate static Point[] mergeNearest(Point[] points, int begin, int end) {		if (begin == end)			return new Point[] { points[begin] };		else {			int mid = (begin + end) / 2;			Point[] left = mergeNearest(points, begin, mid);			Point[] right = mergeNearest(points, mid + 1, end);			return merge(left, right, points, begin, mid, end);		}	}	// 合并左右两边，求最近点对	private static Point[] merge(Point[] left, Point[] right, Point[] points,			int begin, int mid, int end) {		if (left.length == 1 && right.length == 1)			return new Point[] { left[0], right[0] };		Point[] partNearest = partNearest(left, right);		return mergeNearest(points, partNearest, begin, mid, end);	}	// 比较左右两边，返回局部最近点对	private static Point[] partNearest(Point[] left, Point[] right) {		// 两个数组长度不可能同时为0		if (left.length == 1) {			return right;		} else if (right.length == 1) {			return left;		} else {			if (left[0].distance(left[1]) < right[0].distance(right[1]))				return left;			else				return right;		}	}	private static Point[] mergeNearest(Point[] points, Point[] partNearest,			int begin, int mid, int end) {		// 初始化两边在d范围内的点， 并按y坐标排序		Point[] left = null;		Point[] right = null;		Point[] nearest = partNearest;		double middle = (points[mid].getX() + points[mid + 1].getX()) / 2;		double d = partNearest[0].distance(partNearest[1]);		for (int i = mid; i >= begin - 1; i--) {			if (i != begin - 1) {				if (middle - points[i].getX() <= d)					continue;			} else {				left = Arrays.copyOfRange(points, i + 1, mid + 1);				SortComparable.sort(left, new PointYComparaotr());				break;			}		}		for (int i = mid + 1; i <= end + 1; i++) {			if (i != end + 1) {				if (points[i].getX() - middle <= d)					continue;			} else {				right = Arrays.copyOfRange(points, mid + 1, i);				SortComparable.sort(right, new PointYComparaotr());				break;			}		}		// 遍历left数组，在right中寻找符合条件的点		for (Point inLeft : left) {			for (int i = 0; i < right.length; i++) {				if (inLeft.getY() - right[i].getY() > d)					continue;				if (inLeft.getY() - right[i].getY() < -d)					break;				if (inLeft.distance(right[i]) < d) {					nearest = new Point[] { inLeft, right[i] };					d = inLeft.distance(right[i]);				}			}		}		return nearest;	}}测试代码：方法一和方法二输出一样的距离则输出truepublic class TestNearestPoints {	static final int SIZE = 100;	public static void main(String[] args) {		PointGenerator pg = new PointGenerator(10000);		Point[] array = new Point[SIZE];		for(int i = 0; i < array.length; i++)			array[i] = pg.next();		Point[] nearP = NearestPoint.nearest(array);		double d = nearP[0].distance(nearP[1]);		System.out.println(nearest(array) == d);	}	private static double nearest(Point[] array) {		double d = 214748364;          // the guard		for(int i = 0; i < array.length - 1; i++)			for(int j = i + 1; j < array.length; j++)				if(d > array[i].distance(array[j])) {					d = array[i].distance(array[j]);				}			return d;	}}测试代码中相关的PointGenerator类等，请参见：http://blog.csdn.net/QQ_35328850/article/details/56279113