分治法求解最近点距

1.问题描述：

最近点对问题很简单，就是给定一堆点（这里是二位坐标下），求解最近的点的距离，该问题可以用穷举法求解，双重循环就够了，就不说了，主要看一下分治法的代码，代码也很简单，有注释。

2.分治法求解：

代码如下：

采用C++类模板编写
编译环境VS2015

#include <stdio.h>
#include <tchar.h>
#include"math.h"
#include<iostream>
using namespace std;//定义PointX以及PointY类，设定其编号，x,y坐标以及<=运算符，主要是因为
//按X坐标排序和按Y坐标排序时所比较的坐标不相同，因此不能采用同一个类。
//采用两个类可简化算法的复杂度。
class PointX {
public:int operator<= (PointX a)const{return (x <= a.x);}
public:int ID;float x, y;
};class PointY {
public:int operator<= (PointY a)const{return (y <= a.y);}
public:int p;float x, y;
};//通过模板可使函数的通用性更强
template <class T>
inline float Distance(const T &u, const T &v);
bool CPair2(PointX X[], int n, PointX &a, PointX &b, float &d);
template <class T>
void MergeSort(T a[], int n);
template <class T>
void MergePass(T x[], T y[], int s, int n);
template <class T>
void Merge(T c[], T d[], int l, int m, int r);
void closest(PointX X[], PointY Y[], PointY Z[], int l, int r, PointX &a, PointX &b, float &d);int main()
{int n;PointX *X, a, b;float d;cout << "Please input the number of points:" << endl;cin >> n;X = new PointX[n];cout << "Please input the coordinate of the points:" << endl;for (int i = 0; i<n; i++) {cout << "X Y:";cin >> X[i].x >> X[i].y;X[i].ID = i;}CPair2(X, n, a, b, d);cout << "min distance: " << d <<endl;delete[] X;return 0;
}//求任意两点之间的距离
template <class T>
inline float Distance(const T &u, const T &v)
{float dx = u.x - v.x;float dy = u.y - v.y;return sqrt(dx*dx + dy*dy);
}//按x坐标和y坐标排序，并求点对。按y坐标排序的点记录了其原来在排好序之后的X数组中的位置。
//Y数组主要用于存储某分界线两端的点，并使其按Y坐标的大小进行排列，以便于计算。
bool CPair2(PointX X[], int n, PointX &a, PointX &b, float &d)
{if (n<2)return false;MergeSort(X, n);PointY *Y = new PointY[n];for (int i = 0; i<n; i++) {Y[i].p = i;Y[i].x = X[i].x;Y[i].y = X[i].y;}MergeSort(Y, n);PointY *Z = new PointY[n];closest(X, Y, Z, 0, n - 1, a, b, d);delete[] Y;delete[] Z;return true;
}
//用分治法实现的归并排序算法，该函数实现将长度为s的两段序列合并成一段。
template <class T>
void MergeSort(T a[], int n)
{T *b = new T[n];int s = 1;while (s<n) {//将a中的数合并到b中MergePass(a, b, s, n);//s增加一倍，使得合并步长增加一倍。s += s;//将b中的数合并到a中MergePass(b, a, s, n);s += s;}
}//将相邻两段排好序的数组合并成有序序列。
template <class T>
void MergePass(T x[], T y[], int s, int n)
{int i = 0;while (i <= n - 2 * s) {//将x中相邻两段长度为s的有序序列合并成一个，并放在y中。Merge(x, y, i, i + s - 1, i + 2 * s - 1);i = i + 2 * s;}//若x中还有剩余，则将剩余的元素少于2s合并到y中if (i + s<n)Merge(x, y, i, i + s - 1, n - 1);elsefor (int j = i; j <= n - 1; j++)y[j] = x[j];
}//将c[l...m]中的元素和c[m+1...r]中的元素合并在d中。
template <class T>
void Merge(T c[], T d[], int l, int m, int r)
{int i = l, j = m + 1, k = l;while ((i <= m) && (j <= r))//谁小谁先放if (c[i] <= c[j])d[k++] = c[i++];elsed[k++] = c[j++];if (i>m)for (int q = j; q <= r; q++)d[k++] = c[q];elsefor (int q = i; q <= m; q++)d[k++] = c[q];}
//求最小点对及距离
void closest(PointX X[], PointY Y[], PointY Z[], int l, int r, PointX &a, PointX &b, float &d)
{//如果2个点，直接求距离if (r - l == 1) {a = X[l];b = X[r];d = Distance(X[l], X[r]);return;}//如果3个点，则两两计算求最小距离及点对。if (r - l == 2) {float d1 = Distance(X[l], X[l + 1]);float d2 = Distance(X[l + 1], X[r]);float d3 = Distance(X[l], X[r]);if (d1 <= d2 && d1 <= d3) {a = X[l];b = X[l + 1];d = d1;return;}if (d2 <= d3) {a = X[l + 1];b = X[r];d = d2;}else {a = X[l];b = X[r];d = d3;}return;}//其他情况采用二分法分割成几段来求int m = (l + r) / 2;int f = l, g = m + 1;//m将l，r分割成两段，分别求m两边的点，并按照y坐标的大小排列，放在Z数组中for (int i = l; i <= r; i++)if (Y[i].p>m)Z[g++] = Y[i];elseZ[f++] = Y[i];//求l...m间所有点最小点对及距离closest(X, Z, Y, l, m, a, b, d);float dr;PointX ar, br;//求m+1...r间所有点的最小点对及距离closest(X, Z, Y, m + 1, r, ar, br, dr);//求两边点中最小点对及距离。if (dr<d) {a = ar;b = br;d = dr;}//将m两边的点合并到Y数组中，并按Y坐标大小排列Merge(Z, Y, l, m, r);//取矩形条内的点int k = l;for (int i = l; i <= r; i++)if (fabs(Y[m].x - Y[i].x)<d)Z[k++] = Y[i];//求矩形条内的点的最小距离及点对，并与前面求得的点距比较，取最小。for (int i = l; i<k; i++) {for (int j = i + 1; j<k && Z[j].y - Z[i].y<d; j++) {float dp = Distance(Z[i], Z[j]);if (dp<d) {d = dp;a = X[Z[i].p];b = X[Z[j].p];}}}
}