C++-এ অ্যারেতে নিকটতম পয়েন্ট জোড়া (Closest Pair of Points) বের করার প্রোগ্রাম

এটি একটি অ্যারেতে নিকটতম পয়েন্ট জোড়া বের করার প্রোগ্রাম।

অ্যালগরিদম

নিকটতম পয়েন্টের দূরত্ব বের করার জন্য:

শুরু
  Closest_dist_Spoint(poi stp[], int s, double dist, poi &pnt1, poi &pnt2) ফাংশন double টাইপে ডিক্লেয়ার করুন
  Minimum double টাইপে ডিক্লেয়ার করুন
    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) হয়, তবে
        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
শেষ

সর্বনিম্ন দূরত্ব ক্যালকুলেট করার জন্য:

শুরু
  Closest_dist(poi P[], poi stp[], int n, poi &pnt1, poi &pnt2) ফাংশন double টাইপে ডিক্লেয়ার করুন
  pt1, pt2, pt3, pt4 স্ট্যাটিক অবজেক্ট poi স্ট্রাকচারের ডিক্লেয়ার করুন
  যদি (n <= 3) হয়, তবে
    return S_Distance(P, n, pt1, pt2)
  medium ইন্টিজার টাইপে ডিক্লেয়ার করুন
    medium = n/2 ইনিশিয়ালাইজ করুন
  mediumPoint অবজেক্ট poi স্ট্রাকচারের ডিক্লেয়ার করুন
    mediumPoint = P[medium] ইনিশিয়ালাইজ করুন
  D_Left double টাইপে ডিক্লেয়ার করুন
    D_Left = Closest_dist(P, stp, medium, pt1, pt2) ইনিশিয়ালাইজ করুন
  D_Right double টাইপে ডিক্লেয়ার করুন
    D_Right = Closest_dist(P + medium, stp, n-medium, pt3, pt4) ইনিশিয়ালাইজ করুন
  যদি (D_Left < D_Right) হয়, তবে
    pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2
    pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2
  অন্যথায়
    pnt1.poi1 = pt3.poi1; pnt1.poi2 = pt3.poi2
    pnt2.poi1 = pt4.poi1; pnt2.poi2 = pt4.poi2
  min_dist double টাইপে ডিক্লেয়ার করুন
    min_dist = Minimum(D_Left, D_Right) ইনিশিয়ালাইজ করুন
  j ইন্টিজার টাইপে ডিক্লেয়ার করুন
    j = 0 ইনিশিয়ালাইজ করুন
  for (int i = 0; i < n; i++)
    if (abs(P[i].poi1 - mediumPoint.poi1) < min_dist) হয়, তবে
      stp[j++] = P[i]
  min_dist_strip, F_Min double টাইপে ডিক্লেয়ার করুন
    min_dist_strip = Closest_dist_Spoint(stp, j, min_dist, pt1, pt2) ইনিশিয়ালাইজ করুন
    F_Min = min_dist ইনিশিয়ালাইজ করুন
  যদি (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
শেষ

উদাহরণ কোড

#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) { // দুটি পয়েন্টের মধ্যে দূরত্ব ক্যালকুলেট
    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) { // দুটি মানের মধ্যে ন্যূনতম
    return (poi1 < poi2) ? poi1 : poi2;
}

double Closest_dist_Spoint(poi stp[], int s, double dist, poi &pnt1, poi &pnt2) { // নিকটতম পয়েন্টের দূরত্ব
    double Minimum = dist; // ন্যূনতম দূরত্ব 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) { // সর্বনিম্ন দূরত্ব
    static poi pt1, pt2, pt3, pt4;
    if (n <= 3)
        return S_Distance(P, n, pt1, pt2);
    int medium = n/2; // মিড পয়েন্ট ক্যালকুলেট
    poi mediumPoint = P[medium];
    double D_Left = Closest_dist(P, stp, medium, pt1, pt2); // D_Left: মিড পয়েন্টের বামপাশ
    double D_Right = Closest_dist(P + medium, stp, n-medium, pt3, pt4); // D_Right: মিড পয়েন্টের ডানপাশ
    
    if (D_Left < D_Right) {
        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;
    }
    
    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}; // অ্যারেতে নিকটতম পয়েন্ট জোড়া
    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)