001package algs91; // section 9.8 002import stdlib.*; 003import java.util.Arrays; 004import algs12.Point2D; 005import algs22.Merge; 006/* *********************************************************************** 007 * Compilation: javac ClosestPair.java 008 * Execution: java ClosestPair < input.txt 009 * Dependencies: Point2D.java 010 * 011 * Given N points in the plane, find the closest pair in N log N time. 012 * 013 * Note: could speed it up by comparing square of Euclidean distances 014 * instead of Euclidean distances. 015 * 016 * % java ClosestPair < rs1423.txt 017 * 15.0 from (11364.0, 12693.0) to (11373.0, 12705.0) 018 * 019 *************************************************************************/ 020 021 022public class ClosestPair { 023 // closest pair of points and their Euclidean distance 024 private Point2D best1, best2; 025 private double bestDistance = Double.POSITIVE_INFINITY; 026 027 public ClosestPair(Point2D[] points) { 028 int N = points.length; 029 if (N <= 1) return; 030 031 // sort by x-coordinate (breaking ties by y-coordinate) 032 Point2D[] pointsByX = new Point2D[N]; 033 for (int i = 0; i < N; i++) pointsByX[i] = points[i]; 034 Arrays.sort(pointsByX, Point2D.X_ORDER); 035 036 // check for coincident points 037 for (int i = 0; i < N-1; i++) { 038 if (pointsByX[i].equals(pointsByX[i+1])) { 039 bestDistance = 0.0; 040 best1 = pointsByX[i]; 041 best2 = pointsByX[i+1]; 042 return; 043 } 044 } 045 046 // sort by y-coordinate (but not yet sorted) 047 Point2D[] pointsByY = new Point2D[N]; 048 for (int i = 0; i < N; i++) pointsByY[i] = pointsByX[i]; 049 050 // auxiliary array 051 Point2D[] aux = new Point2D[N]; 052 053 closest(pointsByX, pointsByY, aux, 0, N-1); 054 } 055 056 // find closest pair of points in pointsByX[lo..hi] 057 // precondition: pointsByX[lo..hi] and pointsByY[lo..hi] are the same sequence of points 058 // precondition: pointsByX[lo..hi] sorted by x-coordinate 059 // postcondition: pointsByY[lo..hi] sorted by y-coordinate 060 private double closest(Point2D[] pointsByX, Point2D[] pointsByY, Point2D[] aux, int lo, int hi) { 061 if (hi <= lo) return Double.POSITIVE_INFINITY; 062 063 int mid = lo + (hi - lo) / 2; 064 Point2D median = pointsByX[mid]; 065 066 // compute closest pair with both endpoints in left subarray or both in right subarray 067 double delta1 = closest(pointsByX, pointsByY, aux, lo, mid); 068 double delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi); 069 double delta = Math.min(delta1, delta2); 070 071 // merge back so that pointsByY[lo..hi] are sorted by y-coordinate 072 Merge.merge(pointsByY, aux, lo, mid, hi); 073 074 // aux[0..M-1] = sequence of points closer than delta, sorted by y-coordinate 075 int M = 0; 076 for (int i = lo; i <= hi; i++) { 077 if (Math.abs(pointsByY[i].x() - median.x()) < delta) 078 aux[M++] = pointsByY[i]; 079 } 080 081 // compare each point to its neighbors with y-coordinate closer than delta 082 for (int i = 0; i < M; i++) { 083 // a geometric packing argument shows that this loop iterates at most 7 times 084 for (int j = i+1; (j < M) && (aux[j].y() - aux[i].y() < delta); j++) { 085 double distance = aux[i].distanceTo(aux[j]); 086 if (distance < delta) { 087 delta = distance; 088 if (distance < bestDistance) { 089 bestDistance = delta; 090 best1 = aux[i]; 091 best2 = aux[j]; 092 // StdOut.println("better distance = " + delta + " from " + best1 + " to " + best2); 093 } 094 } 095 } 096 } 097 return delta; 098 } 099 100 public Point2D either() { return best1; } 101 public Point2D other() { return best2; } 102 103 public double distance() { 104 return bestDistance; 105 } 106 107 108 public static void main(String[] args) { 109 StdIn.fromFile ("data/rs1423.txt"); 110 111 int N = StdIn.readInt(); 112 Point2D[] points = new Point2D[N]; 113 for (int i = 0; i < N; i++) { 114 double x = StdIn.readDouble(); 115 double y = StdIn.readDouble(); 116 points[i] = new Point2D(x, y); 117 } 118 ClosestPair closest = new ClosestPair(points); 119 StdOut.println(closest.distance() + " from " + closest.either() + " to " + closest.other()); 120 } 121 122}