यह ऐरे में निकटतम बिंदु युग्म खोजने का प्रोग्राम है।
एल्गोरिदम
निकटतम बिंदु के बीच दूरी के लिए
Begin
Closest_dist_Spoint(poi stp[], int s, double dist, poi &pnt1, poi &pnt2) फंक्शन को डबल डेटाटाइप के रूप में घोषित करें
Minimum को डबल डेटाटाइप के रूप में घोषित करें
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
Closest_dist(poi P[], poi stp[], int n, poi &pnt1, poi &pnt2) फंक्शन को डबल डेटाटाइप के रूप में घोषित करें
poi स्ट्रक्चर के स्थैतिक ऑब्जेक्ट pt1, pt2, pt3, pt4 घोषित करें
if (n <= 3) then
return S_Distance(P, n, pt1, pt2)
medium को इंटीजर डेटाटाइप के रूप में घोषित करें
medium = n/2 से इनिशियलाइज़ करें
poi स्ट्रक्चर का mediumPoint ऑब्जेक्ट घोषित करें
mediumPoint = P[medium] से इनिशियलाइज़ करें
D_Left को डबल डेटाटाइप के रूप में घोषित करें
D_Left = Closest_dist(P, stp, medium, pt1, pt2) से इनिशियलाइज़ करें
D_Right को डबल डेटाटाइप के रूप में घोषित करें
D_Right = Closest_dist(P + medium, stp, n-medium, 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
min_dist को डबल डेटाटाइप के रूप में घोषित करें
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) then
stp[j++] = P[i]
min_dist_strip, F_Min को डबल डेटाटाइप के रूप में घोषित करें
min_dist_strip = Closest_dist_Spoint(stp, j, min_dist, pt1, pt2) से इनिशियलाइज़ करें
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) { // दो बिंदुओं के बीच दूरी की गणना
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)