ClosestPair.java
8.33 KB
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
/******************************************************************************
* Compilation: javac ClosestPair.java
* Execution: java ClosestPair < input.txt
* Dependencies: Point2D.java
* Data files: http://algs4.cs.princeton.edu/99hull/rs1423.txt
* http://algs4.cs.princeton.edu/99hull/kw1260.txt
*
* Given n points in the plane, find the closest pair in n log n time.
*
* Note: could speed it up by comparing square of Euclidean distances
* instead of Euclidean distances.
*
******************************************************************************/
package edu.princeton.cs.algs4;
import java.util.Arrays;
/**
* The {@code ClosestPair} data type computes a closest pair of points
* in a set of <em>n</em> points in the plane and provides accessor methods
* for getting the closest pair of points and the distance between them.
* The distance between two points is their Euclidean distance.
* <p>
* This implementation uses a divide-and-conquer algorithm.
* It runs in O(<em>n</em> log <em>n</em>) time in the worst case and uses
* O(<em>n</em>) extra space.
* <p>
* See also {@link FarthestPair}.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/99hull">Section 9.9</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class ClosestPair {
// closest pair of points and their Euclidean distance
private Point2D best1, best2;
private double bestDistance = Double.POSITIVE_INFINITY;
/**
* Computes the closest pair of points in the specified array of points.
*
* @param points the array of points
* @throws NullPointerException if {@code points} is {@code null} or if any
* entry in {@code points[]} is {@code null}
*/
public ClosestPair(Point2D[] points) {
int n = points.length;
if (n <= 1) return;
// sort by x-coordinate (breaking ties by y-coordinate)
Point2D[] pointsByX = new Point2D[n];
for (int i = 0; i < n; i++)
pointsByX[i] = points[i];
Arrays.sort(pointsByX, Point2D.X_ORDER);
// check for coincident points
for (int i = 0; i < n-1; i++) {
if (pointsByX[i].equals(pointsByX[i+1])) {
bestDistance = 0.0;
best1 = pointsByX[i];
best2 = pointsByX[i+1];
return;
}
}
// sort by y-coordinate (but not yet sorted)
Point2D[] pointsByY = new Point2D[n];
for (int i = 0; i < n; i++)
pointsByY[i] = pointsByX[i];
// auxiliary array
Point2D[] aux = new Point2D[n];
closest(pointsByX, pointsByY, aux, 0, n-1);
}
// find closest pair of points in pointsByX[lo..hi]
// precondition: pointsByX[lo..hi] and pointsByY[lo..hi] are the same sequence of points
// precondition: pointsByX[lo..hi] sorted by x-coordinate
// postcondition: pointsByY[lo..hi] sorted by y-coordinate
private double closest(Point2D[] pointsByX, Point2D[] pointsByY, Point2D[] aux, int lo, int hi) {
if (hi <= lo) return Double.POSITIVE_INFINITY;
int mid = lo + (hi - lo) / 2;
Point2D median = pointsByX[mid];
// compute closest pair with both endpoints in left subarray or both in right subarray
double delta1 = closest(pointsByX, pointsByY, aux, lo, mid);
double delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi);
double delta = Math.min(delta1, delta2);
// merge back so that pointsByY[lo..hi] are sorted by y-coordinate
merge(pointsByY, aux, lo, mid, hi);
// aux[0..m-1] = sequence of points closer than delta, sorted by y-coordinate
int m = 0;
for (int i = lo; i <= hi; i++) {
if (Math.abs(pointsByY[i].x() - median.x()) < delta)
aux[m++] = pointsByY[i];
}
// compare each point to its neighbors with y-coordinate closer than delta
for (int i = 0; i < m; i++) {
// a geometric packing argument shows that this loop iterates at most 7 times
for (int j = i+1; (j < m) && (aux[j].y() - aux[i].y() < delta); j++) {
double distance = aux[i].distanceTo(aux[j]);
if (distance < delta) {
delta = distance;
if (distance < bestDistance) {
bestDistance = delta;
best1 = aux[i];
best2 = aux[j];
// StdOut.println("better distance = " + delta + " from " + best1 + " to " + best2);
}
}
}
}
return delta;
}
/**
* Returns one of the points in the closest pair of points.
*
* @return one of the two points in the closest pair of points;
* {@code null} if no such point (because there are fewer than 2 points)
*/
public Point2D either() {
return best1;
}
/**
* Returns the other point in the closest pair of points.
*
* @return the other point in the closest pair of points
* {@code null} if no such point (because there are fewer than 2 points)
*/
public Point2D other() {
return best2;
}
/**
* Returns the Eucliden distance between the closest pair of points.
*
* @return the Euclidean distance between the closest pair of points
* {@code Double.POSITIVE_INFINITY} if no such pair of points
* exist (because there are fewer than 2 points)
*/
public double distance() {
return bestDistance;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
/**
* Unit tests the {@code ClosestPair} data type.
* Reads in an integer {@code n} and {@code n} points (specified by
* their <em>x</em>- and <em>y</em>-coordinates) from standard input;
* computes a closest pair of points; and prints the pair to standard
* output.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
int n = StdIn.readInt();
Point2D[] points = new Point2D[n];
for (int i = 0; i < n; i++) {
double x = StdIn.readDouble();
double y = StdIn.readDouble();
points[i] = new Point2D(x, y);
}
ClosestPair closest = new ClosestPair(points);
StdOut.println(closest.distance() + " from " + closest.either() + " to " + closest.other());
}
}
/******************************************************************************
* Copyright 2002-2016, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/