Java Reference
In-Depth Information
for
(
int
j = i +
1
; j < points.length; j++) {
24
25
double
distance = distance(points[i][
0
], points[i][
1
],
26 points[j][
0
], points[j][
1
]);
// Find distance
27
28
29 p1 = i;
// Update p1
30 p2 = j;
// Update p2
31 shortestDistance = distance;
// Update shortestDistance
32 }
33 }
34 }
35
36
// Display result
37 System.out.println(
"The closest two points are "
+
38
"("
+ points[p1][
0
] +
", "
+ points[p1][
1
] +
") and ("
+
39 points[p2][
0
] +
", "
+ points[p2][
1
] +
")"
);
40 }
41
42
for each point
j
distance between
i
and
j
distance between two points
if
(shortestDistance > distance) {
update
shortestDistance
/** Compute the distance between two points (x1, y1) and (x2, y2)*/
43
public static double
distance(
44
double
x1,
double
y1,
double
x2,
double
y2) {
45
return
Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
46 }
47 }
Enter the number of points:
Enter 8 points:
The closest two points are (1, 1) and (2, 0.5)
8
-1 3 -1 -1 1 1 2 0.5 2 -1 3 3 4 2 4 -0.5
The program prompts the user to enter the number of points (lines 6-7). The points are
read from the console and stored in a two-dimensional array named
points
(lines 12-15).
The program uses the variable
shortestDistance
(line 19) to store the distance between
the two nearest points, and the indices of these two points in the
points
array are stored in
p1
and
p2
(line 18).
For each point at index
i
, the program computes the distance between
points[i]
and
points[j]
for all
j > i
(lines 23-34). Whenever a shorter distance is found, the variable
shortestDistance
and
p1
and
p2
are updated (lines 28-32).
The d
istance between two poin
ts
(x1, y1)
and
(x2, y2)
can be computed using the for-
mula (lines 43-46).
The program assumes that the plane has at least two points. You can easily modify the pro-
gram to handle the case if the plane has zero or one point.
Note that there might be more than one closest pair of points with the same minimum dis-
tance. The program finds one such pair. You may modify the program to find all closest pairs
in Programming Exercise 7.8.
x
1
)
2
y
1
)
2
2
(
x
2
-
+
(
y
2
-
multiple closest pairs
Tip
It is cumbersome to enter all points from the keyboard. You may store the input in a
file, say
FindNearestPoints.txt
, and compile and run the program using the follow-
ing command:
input file
java FindNearestPoints < FindNearestPoints.txt
