nearestpoints.cpp

本程序实现的功能是给出一系列点

/*给定n 个点（xi，yi）（1≤i≤n），要求找出其中距离最近的两个点.
*/

/*算法思想：

  分而治之算法:

 如果n较小,用直接法寻找最近点对;  

 如果n较大, 将点集分成大致相等的两个部分A和B,

 确定A和B中的最近点对 ,确定一点在A中、另一点
 
 在B中的最近点对 ,从上面得到的三对点中，找出距离最小的一对点 */

#include <math.h>
#include <iostream.h>

class Point2;
class Point1 { 

friend float dist(const Point1&, const Point1&); 

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&); 

friend bool closest(Point1 *, int, Point1&, Point1&,float&); 

friend void main(); 

public:

int operator<=(Point1 a) const 

{return (x <= a.x);} 

private:

int ID; // 点的编号 

float x, y; // 点坐标 

} ;

class Point2 { 

friend float dist(const Point2&, const Point2&); 

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&); 

friend bool closest(Point1 *, int, Point1&, Point1&, float&); 

friend void main(); 

public: 

int operator<=(Point2 a) const 

{return (y <= a.y);} 

private:

int p; // 数组X中相同点的索引 

float x, y; // 点坐标 

} ;

template <class T>
 float dist(const T& u, const T& v) 

{ 
	// 计算点u 和v之间的距离 

float dx = u.x-v. x ; 

float dy = u.y-v. y ; 

return (float)sqrt(dx * dx + dy * dy); 

} 

 
 template <class T> void MergeSort(T a[], int n)

{// 使用归并排序算法对a[0:n-1] 进行排序

T *b = new T [n];

int s = 1; // 段的大小

while (s < n) {

MergePass(a, b, s, n); // 从a归并到b

s += s;

MergePass(b, a, s, n); // 从b 归并到a

s += s;

}

}

template <class T>

void MergePass(T x[], T y[], int s, int n)

{// 归并大小为s的相邻段

int i = 0;

while (i <= n - 2 * s) {

// 归并两个大小为s的相邻段

Merge(x, y, i, i+s-1, i+2*s-1);

i = i + 2 * s;

}

// 剩下不足2个元素

if (i + s < n) Merge(x, y, i, i+s-1, n-1);

else for (int j = i; j <= n-1; j++)

// 把最后一段复制到y

y[j] = x[j];

}



template <class T>

void Merge(T c[], T d[], int l, int m, int r)

{// 把c[l:m]] 和c[m:r] 归并到d [ l : r ] .

int i = l, // 第一段的游标

j = m+1, // 第二段的游标

k = l; // 结果的游标

//只要在段中存在i和j，则不断进行归并

while ((i <= m) && (j <= r))

if (c[i] <= c[j]) d[k++] = c[i++];

else d[k++] = c[j++];

// 考虑余下的部分

if (i > m) for (int q = j; q <= r; q++)

d[k++] = c[q];

else for (int q = i; q <= m; q++)

d[k++] = c[q];

}

bool closest(Point1 X[], int n, Point1& a, Point1& b, float& d) 

{
	// 在n >= 2 个点中寻找最近点对 

// 如果少于2个点，则返回f a l s e 

// 否则，在a 和b中返回距离最近的两个点 

if (n < 2) return false; 

// 按x坐标排序 

MergeSort( X , n ) ; 

// 创建一个按y坐标排序的点数组 

Point2 *Y = new Point2 [n]; 

for (int i = 0; i < n; i++) { 

// 将点i 从X 复制到Y 

Y[i].p = i; 

Y[i].x = X[i].x; 

Y[i].y = X[i].y; 

} 

MergeSort ( Y,n); // 按y坐标排序 

// 创建临时数组 

Point2 *Z = new Point2 [n]; 

// 寻找最近点对 

close( X , Y, Z , 0 , n - 1 , a , b , d ) ; 

// 删除数组并返回 

delete [] Y; 

delete [] Z; 

return true; 

} 



void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1& a, Point1& b, float& d) 

{//X[l:r] 按x坐标排序 

//Y[l:r] 按y坐标排序 

if (r-l == 1) {// 两个点 

a = X[l]; 

b = X[r]; 

d = dist(X[l], X[r]); 

return ; } 

if (r-l == 2) {// 三个点 

// 计算所有点对之间的距离 

float d1 = dist(X[l], X[l+1]); 

float d2 = dist(X[l+1], X[r]); 

float d3 = dist(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; // X[l:m] 在A中，余下的在B中 

// 在Z[l:m] 和Z [ m + 1 : r ]中创建按y排序的表 

int f = l, // Z[l:m]的游标 

g = m+1; // Z[m+1:r]的游标 

for (int i = l; i <= r; i++) 

if (Y[i].p > m) Z[g++] = Y[i]; 

else Z[f++] = Y[i]; 

// 对以上两个部分进行求解 

close( X , Z , Y, l , m , a , b , d ) ; 

float dr; 

Point1 ar, br; 

close ( X , Z , Y, m + 1 , r, ar, br, dr ) ; 

// (a,b) 是两者中较近的点对 

if (dr < d) {a = ar; 

b = br; 

d = dr;} 

Merge( Z,Y,l,m,r);// 重构Y 

//距离小于d的点放入Z 

int k = l; // Z的游标 

for (i = l; i <= r; i++) 

if (fabs(Y[m].x - Y[i].x) < d) Z[k++] = Y[i]; 

// 通过检查Z [ l : k - 1 ]中的所有点对，寻找较近的点对 

for (i = l; i < k; i++){ 

for (int j = i+1; j < k && Z[j].y - Z[i].y < d; j++)
 { 

float dp = dist(Z[i], Z[j]); 

if (dp < d) {// 较近的点对 

d = dp; 

a = X[Z[i].p]; 

b = X[Z[j].p];} 

} 

} 

} 


 void main()
 {
   int n;
   cout<<"请输入点对的数目:"<<endl;
   cin>>n;
   Point1* pArray = new Point1[n];
   int i=0;
   while(i<n)
   {
     cout<<"请输入点的X坐标:"<<endl;
	 cin>>pArray[i].x;
	 cout<<"请输入点的Y坐标:"<<endl;
	 cin>>pArray[i].y;
	 i++;}
	 Point1 nearest1,nearest2;
     float d;
   closest(pArray,n,nearest1,nearest2,d);
   cout<<"最近点1的X坐标:"<<nearest1.x<<"最近点1的Y坐标:"<<nearest1.y<<endl;
   cout<<"最近点2的X坐标:"<<nearest2.x<<"最近点2的Y坐标:"<<nearest2.y<<endl;
   cout<<"他们之间的距离为:"<<d<<endl;

 }