C++ Problem: Finding a Closest Pair

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 imple­mented 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 dis­tance. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *