C++ Program to Find Closest Pair of Points in an Array

This is the program to find closest pair of points in an array.

Algorithms

For Distance between Closest point

Begin    Declare function Closest_dist_Spoint(poi stp[], int s, double dist, poi &pnt1, poi &pnt2) to the double datatype.    Declare Minimum to the double datatype.       Initialize Minimum = dist.    for (int i = 0; i < s; ++i)       for (int j = i+1; j < s && (stp[j].poi2 - stp[i].poi2) < Minimum; ++j)          if (Distance(stp[i],stp[j]) < Minimum) then          Minimum = Distance(stp[i], stp[j]).             pnt1.poi1 = stp[i].poi1, pnt1.poi2 = stp[i].poi2.             pnt2.poi1 = stp[j].poi1, pnt2.poi2 = stp[j].poi2.    Return Minimum. End.

To Calculate smallest distance −

Begin    Declare function Closest_dist(poi P[], poi stp[], int n, poi &pnt1, poi &pnt2) to the double datatype.    Declare static object pt1, pt2, pt3, pt4 of poi structure.    if (n <= 3) then       return S_Distance(P, n, pt1, pt2).    Declare medium to the integer datatype.       Initialize midium = n/2.    Declare object mediumPoint of poi structure.       Initialize midiumPoint = P[midium].    Declare D_Left to the double datatype.       Initialize D _Left = Closest_dist(P, stp, midium, pt1, pt2).    Declare D_Right to the double datatype.       Initialize D_Right = Closest_dist(P + midium, stp, n-midium, pt3, pt4).    if(D_Left < D_Right) then       pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2.       pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2.    else       pnt1.poi1 = pt3.poi1; pnt1.poi2 = pt3.poi2;       pnt2.poi1 = pt4.poi1; pnt2.poi2 = pt4.poi2;    Declare min_dist to the double datatype.       Initialize min_dist = Minimum(D_Left, D_Right).    Declare j to the integer datatype.       initialize j = 0.    for (int i = 0; i < n; i++)       if (abs(P[i].poi1 - midiumPoint.poi1) < min_dist) then          stp[j++] = P[i].    Declare min_dist_strip, F_Min to the double datatype.       Initalize min_dist_strip = Closest_dist_Spoint(stp, j, min_dist, pt1, pt2).       Initialize F_Min = min_dist.    if(min_dist_strip < min_dist) then       pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2;       pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2;       F_Min = min_dist_strip;    Return F_Min. End.

Example

 Live Demo

#include <iostream> #include <cfloat> #include <cstdlib> #include <cmath> using namespace std; struct poi {    double poi1, poi2; }; inline int Comp_poi1(const void* x, const void* b) {    poi *p1 = (poi *)x, *pnt2 = (poi *)b;    return (p1->poi1 - pnt2->poi1); } inline int Comp_poi2(const void* x, const void* y) {    poi *pnt1 = (poi *)x, *pnt2 = (poi *)y;    return (pnt1->poi2 - pnt2->poi2); } inline double Distance(poi pnt1, poi pnt2) { // Calculate the distance between two points    return sqrt( (pnt1.poi1 - pnt2.poi1)*(pnt1.poi1 - pnt2.poi1) +    (pnt1.poi2 - pnt2.poi2)*(pnt1.poi2 - pnt2.poi2) ); } double S_Distance(poi P[], int n, poi &pnt1, poi &pnt2) {    double min = DBL_MAX;    for (int i = 0; i < n; ++i)       for (int j = i+1; j < n; ++j)          if (Distance(P[i], P[j]) < min) {             min = Distance(P[i], P[j]);             pnt1.poi1 = P[i].poi1, pnt1.poi2 = P[i].poi2;             pnt2.poi1 = P[j].poi1, pnt2.poi2 = P[j].poi2;          }    return min; } inline double Minimum(double poi1, double poi2) {  // Find minimum between two values    return (poi1 < poi2)? poi1 : poi2; } double Closest_dist_Spoint(poi stp[], int s, double dist, poi &pnt1, poi &pnt2) { // Calculate distance beween the closest points    double Minimum = dist; // Initialize the minimum distance as dist    qsort(stp, s, sizeof(poi), Comp_poi2);    for (int i = 0; i < s; ++i)       for (int j = i+1; j < s && (stp[j].poi2 - stp[i].poi2) < Minimum; ++j)          if (Distance(stp[i],stp[j]) < Minimum) {             Minimum = Distance(stp[i], stp[j]);             pnt1.poi1 = stp[i].poi1, pnt1.poi2 = stp[i].poi2;             pnt2.poi1 = stp[j].poi1, pnt2.poi2 = stp[j].poi2;          }          return Minimum; } double Closest_dist(poi P[], poi stp[], int n, poi &pnt1, poi &pnt2) { // Calculate smallest distance.    static poi pt1, pt2, pt3, pt4;    if (n <= 3)       return S_Distance(P, n, pt1, pt2);    int medium = n/2; // Calculate the mid point    poi mediumPoint = P[medium];    double D_Left = Closest_dist(P, stp, medium, pt1, pt2); // D_Left: left of medium point    double D_Right = Closest_dist(P + medium, stp, n-medium, pt3, pt4); // D_Right: right side of the medium point    if(D_Left < D_Right) {       pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2; // Store the pair that has smaller distance       pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2;    } else {       pnt1.poi1 = pt3.poi1; pnt1.poi2 = pt3.poi2;       pnt2.poi1 = pt4.poi1; pnt2.poi2 = pt4.poi2;    }    double min_dist = Minimum(D_Left, D_Right);    int j = 0;    for (int i = 0; i < n; i++)       if (abs(P[i].poi1 - mediumPoint.poi1) < min_dist)          stp[j++] = P[i];       double min_dist_strip = Closest_dist_Spoint(stp, j, min_dist, pt1, pt2);       double F_Min = min_dist;       if(min_dist_strip < min_dist) {          pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2;          pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2;          F_Min = min_dist_strip;       }       return F_Min; } int main() {    poi P[] = {{4, 1}, {15, 20}, {30, 40}, {8, 4}, {13, 11}, {5, 6}};    poi pnt1 = {DBL_MAX, DBL_MAX}, pnt2 = {DBL_MAX, DBL_MAX}; // Closest pair of points in array    int n = sizeof(P) / sizeof(P[0]);    qsort(P, n, sizeof(poi), Comp_poi1);    poi *stp = new poi[n];    cout << "The closest distance of point in array is: " << Closest_dist(P, stp, n, pnt1, pnt2) << endl;    cout << "The closest pair of point in array: (" << pnt1.poi1 << "," << pnt1.poi2 << ") and ("    << pnt2.poi1 << "," << pnt2.poi2 << ")" << endl;    delete[] stp;    return 0; }

Output

The closest distance of point in array is: 3.60555 The closest pair of point in array: (13,11) and (15,20)