closestpair.java

最近点对问题的图形界面实现

package firstproblem;

/**
 * 求最近点对算法，使用这个类求得的复杂度为O(nlgn)
 * 
 * @author 何腾飞
 * 
 */
public class ClosestPair {
	public static Pair cpair2(Point1[] x) {
		if (x.length < 2)
			return null;
		MergeSort.mergeSort(x);
		Point2[] y = new Point2[x.length];
		for (int i = 0; i < x.length; i++) {
			y[i] = new Point2(x[i].x, x[i].y, i);
		}
		MergeSort.mergeSort(y);
		Point2[] z = new Point2[x.length];
		for(int i=0;i<z.length;i++){
			z[i] = new Point2();
		}
		return closestPair(x, y, z, 0, x.length - 1);
	}

	public static Pair closestPair(Point1[] x, Point2[] y, Point2[] z, int l,
			int r) {
		if (r - l == 1)
			return new Pair(x[l], x[r], Distance.dist(x[l], x[r]));
		if (r - l == 2) {
			double d1 = Distance.dist(x[l], x[l + 1]);
			double d2 = Distance.dist(x[l + 1], x[r]);
			double d3 = Distance.dist(x[l], x[r]);
			if (d1 <= d2 && d1 <= d3)
				return new Pair(x[l], x[l + 1], d1);
			else if (d2 <= d3) {
				return new Pair(x[l + 1], x[r], d2);
			} else
				return new Pair(x[l], x[r], d3);
		}
		int m = (l + r) / 2;
		int f = l;
		int g = m + 1;
		for (int i = l; i <= r; i++) {
			if (y[i].p > m){
				z[g++] = y[i];
				// System.out.println("i:"+i+"g:"+g);
				// g++;
			}	
			else{
				z[f++] = y[i];
				// System.out.println("i:"+i+"f:"+f);
				// f++;
			}
				
		}
		Pair best = closestPair(x, z, y, l, m);
		Pair right = closestPair(x, z, y, m + 1, r);
		if (right.dist < best.dist)
			best = right;
		MergeSort.merge(z, y, l, m, r);
		int k = l;
		for (int i = l; i <= r; i++) {
			if (Math.abs(x[m].x - y[i].x) < best.dist)
				z[k++] = y[i];
		}
		for (int i = l; i < k; i++) {
			for (int j = i + 1; j < k && z[j].y - z[i].y < best.dist; j++) {
				double dp = Distance.dist(z[i], z[j]);
				if (dp < best.dist)
					best = new Pair(x[z[i].p], x[z[j].p], dp);
			}
		}
		return best;
	}
}