配列内の最も近いポイントのペアを見つける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)