public class ClosestPair extends Object
ClosestPair
data type computes a closest pair of points
in a set of n 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.
This implementation uses a divide-and-conquer algorithm. It runs in O(n log n) time in the worst case and uses O(n) extra space.
See also FarthestPair
.
For additional documentation, see Section 9.9 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
ClosestPair(Point2D[] points)
Computes the closest pair of points in the specified array of points.
|
Modifier and Type | Method and Description |
---|---|
double |
distance()
Returns the Euclidean distance between the closest pair of points.
|
Point2D |
either()
Returns one of the points in the closest pair of points.
|
static void |
main(String[] args)
Unit tests the
ClosestPair data type. |
Point2D |
other()
Returns the other point in the closest pair of points.
|
public ClosestPair(Point2D[] points)
points
- the array of pointsIllegalArgumentException
- if points
is null
or if any
entry in points[]
is null
public Point2D either()
null
if no such point (because there are fewer than 2 points)public Point2D other()
null
if no such point (because there are fewer than 2 points)public double distance()
Double.POSITIVE_INFINITY
if no such pair of points
exist (because there are fewer than 2 points)public static void main(String[] args)
ClosestPair
data type.
Reads in an integer n
and n
points (specified by
their x- and y-coordinates) from standard input;
computes a closest pair of points; and prints the pair to standard
output.args
- the command-line arguments