Chương trình C++ tìm cặp điểm gần nhất trong mảng

Đây là chương trình tìm cặp điểm gần nhất trong một mảng.

Thuật toán

Khoảng cách giữa cặp điểm gần nhất

Bắt đầu
  Khai báo hàm Closest_dist_Spoint(poi stp[], int s, double dist, poi &pnt1, poi &pnt2) trả về double.
  Khai báo Minimum kiểu double.
    Khởi tạo 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) thì
        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.
  Trả về Minimum.
Kết thúc.

Để tính khoảng cách nhỏ nhất:

Bắt đầu
  Khai báo hàm Closest_dist(poi P[], poi stp[], int n, poi &pnt1, poi &pnt2) trả về double.
  Khai báo đối tượng tĩnh pt1, pt2, pt3, pt4 của cấu trúc poi.
  if (n <= 3) thì
    trả về S_Distance(P, n, pt1, pt2).
  Khai báo medium kiểu nguyên.
    Khởi tạo midium = n/2.
  Khai báo đối tượng mediumPoint kiểu poi.
    Khởi tạo midiumPoint = P[midium].
  Khai báo D_Left kiểu double.
    Khởi tạo D_Left = Closest_dist(P, stp, midium, pt1, pt2).
  Khai báo D_Right kiểu double.
    Khởi tạo D_Right = Closest_dist(P + midium, stp, n-midium, pt3, pt4).
  if(D_Left < D_Right) thì
    pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2.
    pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2.
  ngược lại
    pnt1.poi1 = pt3.poi1; pnt1.poi2 = pt3.poi2;
    pnt2.poi1 = pt4.poi1; pnt2.poi2 = pt4.poi2;
  Khai báo min_dist kiểu double.
    Khởi tạo min_dist = Minimum(D_Left, D_Right).
  Khai báo j kiểu nguyên.
    Khởi tạo j = 0.
  for (int i = 0; i < n; i++)
    if (abs(P[i].poi1 - midiumPoint.poi1) < min_dist) thì
      stp[j++] = P[i].
  Khai báo min_dist_strip, F_Min kiểu double.
    Khởi tạo min_dist_strip = Closest_dist_Spoint(stp, j, min_dist, pt1, pt2).
    Khởi tạo F_Min = min_dist.
  if(min_dist_strip < min_dist) thì
    pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2;
    pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2;
    F_Min = min_dist_strip;
  Trả về F_Min.
Kết thúc.

Ví dụ

#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) {
  // Tính khoảng cách giữa hai điểm
  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) {
  // Tìm nhỏ hơn giữa hai giá trị
  return (poi1 < poi2) ? poi1 : poi2;
}

double Closest_dist_Spoint(poi stp[], int s, double dist, poi &pnt1, poi &pnt2) {
  // Tính khoảng cách giữa các điểm gần nhất
  double Minimum = dist; // Khởi tạo khoảng cách nhỏ nhất là 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) {
  // Tính khoảng cách nhỏ nhất.
  static poi pt1, pt2, pt3, pt4;
  if (n <= 3)
    return S_Distance(P, n, pt1, pt2);
  int medium = n/2; // Tính điểm giữa
  poi mediumPoint = P[medium];
  double D_Left = Closest_dist(P, stp, medium, pt1, pt2); // D_Left: bên trái điểm giữa
  double D_Right = Closest_dist(P + medium, stp, n-medium, pt3, pt4); // D_Right: bên phải điểm giữa
  if(D_Left < D_Right) {
    pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2; // Lưu cặp có khoảng cách nhỏ hơn
    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}; // Cặp điểm gần nhất trong mảng
  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;
}

Kết quả

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