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)