This section presents a geometric problem for finding the closest pair of points.
Given a set of points, the closest-pair problem is to find the two points that are nearest to each other. In Figure 8.2, for example, points (1, 1) and (2, 0.5) are closest to each other. There are several ways to solve this problem. An intuitive approach is to compute the distances between all pairs of points and find the pair with the minimum distance, as implemented in Listing 8.3.
Figure 8.2 Points can be represented in a two-dimensional array.
Listing 8.3 FindNearestPoints.cpp
1 #include <iostream>
2 #include <cmath>
3 using namespace std;
4
5 // Compute the distance between two points (x1, y1) and (x2, y2)
6 double getDistance(double x1, double y1, double x2, double y2)
7 {
8 return sqrt((x2 – x1) * (x2 – x1) + (y2 – y1) * (y2 – y1));
9 }
10
11 int main()
12 {
13 const int NUMBER_OF_POINTS = 8;
14
15 // Each row in points represents a point
16 double points[NUMBER_OF_POINTS][2];
17
18 cout << “Enter ” << NUMBER_OF_POINTS << ” points: “;
19 for (int i = 0; i < NUMBER_OF_POINTS; i++)
20 cin >> points[i][0] >> points[i][1];
21
22 // p1 and p2 are the indices in the points array
23 int p1 = 0, p2 = 1; // Initial two points
24 double shortestDistance = getDistance(points[p1][0], points[p1][1],
25 points[p2][0], points[p2][1]); // Initialize shortestDistance
26
27 // Compute distance for every two points
28 for (int i = 0; i < NUMBER_OF_POINTS; i++)
29 {
30 for (int j = i + 1; j < NUMBER_OF_POINTS; j++)
31 {
32 double distance = getDistance(points[i][0], points[i][1],
33 points[j][0], points[j][1]); // Find distance
34
35 if (shortestDistance > distance)
36 {
37 p1 = i; // Update p1
38 p2 = j; // Update p2
39 shortestDistance = distance; // Update shortestDistance
40 }
41 }
42 }
43
44 // Display result
45 cout << “The closest two points are ” <<
46 “(” << points[p1][0] << “, ” << points[p1][1] << “) and (” <<
47 points[p2][0] << “, ” << points[p2][1] << “)” << endl;
48
49 return 0;
50 }
The points are read from the console and stored in a two-dimensional array named points (lines 19-20). The program uses variable shortestDistance (line 24) to store the distance between two nearest points, and the indices of these two points in the points array are stored in pi and p2 (line 23).
For each point at index i, the program computes the distance between points[i] and points[j] for all j > i (lines 28-42). Whenever a shorter distance is found, the variable shortestDistance, pi, and p2 are updated (lines 37-39).
The distance between two points (xi, yi) and (x2, y2) can be computed using the formula in function getDistance (lines 6-9).
The program assumes that the plain has at least two points. You can easily modify the program to handle the case if the plain has one point or none.
Note that there might be more than one closest pair of points with the same minimum distance. The program finds one such pair. You may modify the program to find all closest pairs in Programming Exercise 8.10.
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 following command:
g++ FindNearestPoints.cpp -o FindNearestPoints.exe
FindNearestPoints.exe < FindNearestPoints.txt
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.