cpair.cpp

最近点对算法

// Cpair.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
#include<math.h>
#include <time.h>



using namespace std;

typedef struct point   //定义平面上点的结构
{ 
    float x,y;

} point;   


void x_sort(point* Array , int n);  //以每个点的x坐标进行排序
void y_sort(point* Array , int n);  //以每个点的y坐标进行排序
double dist(point u,point v);       //求两个点之间的距离
double closestPair(point *X,point *Y,int l,int r);   //求最近点对的距离
void quickSort(float a[],int low,int high) ;          //穷举法求出最近点对距离

int main()
{   
    int n,i,j;                  //定义点的个数  
    int temp;
    float *A= new float;
    
    cout<< "Please input the number of points :";
    cin>>n;
 
   
    point* X = new point[n] ;
    cout<<"Please choose Random (x y)(=0) OR Artificial input (x y)(=1) :";
    scanf("%d",&temp);
    
    
    if (temp==0)
    {
        srand((unsigned)time(NULL));
	
        for (i=0; i<n ; i++)
        {
            X[i].x = rand()%70;
	    X[i].y = rand()%200;
	   
        }
	for (i=0; i<n ; i++)
        {
             cout<<"("<<X[i].x<<","<<X[i].y<<")"<<endl;
        }

    }
    else if (temp==1)
    {
       
    cout<< "Please input the coordinates of points (x y) "<<endl;
    
    for(i=0;i<n;i++)
    {
        
	cin>>X[i].x>>X[i].y;
	
    } 
	
    }
    
    else
    {
        printf("Input ERROR　!!!\n");
        return 0 ;
    }
  
    //穷举法求出最近点对距离
//     int k=0;
//     for(i=0;i<n;i++){
// 	for (j=i+1;j<n;j++)
// 	{   
// 	    
// 		A[k]=dist(X[i],X[j]);
// 		//cout<<A[k]<<endl;
// 	        k++;
// 	   
// 
// 	}
//     }
    
//     
//     int high;
//     high = n*(n-1)/2 ;
//     if (high==0)
//     {
//      cout<<"Exhaustive method Calculation of minimum distance is 0"<<endl;
//     } 
//     else
//     {
// 	quickSort(A,0,high-1) ;
//     
//         cout<<"Exhaustive method Calculation of minimum distance is"<<A[0]<<endl;
//     }
//     


    x_sort(X,n);   //以x坐标增序对S中的点排序
    
    
    //以x坐标增序对输入的点排序
    point* Y = new point[n] ;
    
    for(i=0;i<n;i++)
    {
	Y[i].x=X[i].x;
	Y[i].y=X[i].y;
    }    
    
    x_sort(Y,n);
   
    double min=closestPair(X,Y,0,n-1);
    
    cout<<"ClosestPair minimum distance between two points is "<<min<<endl;
    
    free (X) ;
    free (Y) ;
    
    
    system("pause");
    return 0;
}


//用快速排序对穷举任意两点间的距离进行排序

void quickSort(float a[],int low,int high)  
{
    int i,j;
    float temp;
    i=low;
    j=high;
    temp=a[low];
    if(low>high)
	return ;
    while(i!=j)/*找到最终位置*/
    {
	while(a[j]>=temp && j>i)
	    j--;
	if(j>i)
	    a[i++]=a[j];
	while(a[i]<=temp && j>i)
	    i++;
	if(j>i)
	    a[j--]=a[i];
	
    }
    a[i]=temp;
    quickSort(a,low,i-1);/*递归左边*/
    quickSort(a,i+1,high);/*递归右边*/
}


//以每个点的X坐标进行排序
void x_sort(point* Array , int n)
{ 
    int i=1,j=0 ;
    double tempx,tempy;
    while(i<n){
	for(j=0;j<i;j++)
	    while(Array[i].x<Array[j].x){
		tempx=Array[i].x;
		tempy=Array[i].y;
		Array[i].x=Array[j].x;
                Array[i].y=Array[j].y;
		Array[j].x=tempx;
		Array[j].y=tempy;
	    }
	    i++;
    }
}


//以每个点的y坐标进行排序
void y_sort(point* Array , int n)
{ 
    int i=1,j=0 ;
    double tempx,tempy;
    while(i<n){
	for(j=0;j<i;j++)
	    while(Array[i].y<Array[j].y){
		tempx=Array[i].x;
		tempy=Array[i].y;
		Array[i].x=Array[j].x;
                Array[i].y=Array[j].y;
		Array[j].x=tempx;
		Array[j].y=tempy;
	    }
	    i++;
    }
}



//求两点间的距离

double dist(point u,point v)
{
    float dx=u.x-v.x;
    float dy=u.y-v.y;
   
    return sqrt(dx*dx+dy*dy);
}   



double closestPair(point *X,point *Y,int l,int r)
{
    float min;
    int n = r-l+1;  //输入点的个数
   
    //点的个数小于三个,则直接计算
    
    if(n<=1) return 0;
    if(n==2) return dist(X[l],X[r]);
    if(n==3){
        float d1,d2,d3;
        d1=dist(X[l],X[l+1]);
        d2=dist(X[l+1],X[r]);
        d3=dist(X[l],X[r]);
        if(d1<=d2) min=d1;
        else min=d2;
        if(min>d3) min=d3;
	return min;
    }
      
    //递归求解
    
    int mid;
    float x0,minl,minr;
   
    mid = (l+r)/2;
    x0 = X[mid].x;
    minl = closestPair(X,Y,l,mid);
    minr = closestPair(X,Y,mid+1,r);
    if(minl<=minr) min = minl;
    else min = minr;
   
    int i,k=0;
    point* Pair;
    Pair=(point *)malloc(sizeof(point)*n);
  
   
    //d矩形条内的点	
    
    for(i=0;i<n;i++) 
    {
        if(fabs(Y[i].x-x0)<=min)
        {
            Pair[k].x=Y[i].x;
            Pair[k].y=Y[i].y;
            k++;
        }
    }
   
    double lmin=2*min;
    
    //搜索中间区域7个最近点的距离计算
    
    for(i=0;i<k;i++)
    {
        int t;
        if((i+7)<k) t=i+7;
        else t=k;       
        for(int j=i+1;j<t;j++)
        {
            float dp=dist(Pair[i],Pair[j]);
            if(dp<minl) 
	    lmin = dp;
        }
    }          
   
    if(lmin < min) min=lmin;
   
    return min; 

}