C ++程序查找数组中最近的点对

这是在数组中查找最接近的点对的程序。

演算法

对于最近点之间的距离

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.

要计算最小距离-

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.

示例

#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;
}

输出结果

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