快速空间最近点对C++实现.docx

/* *im:平面最近点对 *&2016-2-25 15:47:50*Author:小花熊 *Q:1198253149 */#include#include#include#include struct Point float x,y; ; /插入排序 void _insert_sorty(Point *y,const int size) Point *x; int k,j; for(j=1;j=0 & x-yy) yk+1=yk; -k; if( k+1 != j ) yk+1=x; /假设点已经是按照x轴升序排列好了,并且size是2的整次幂/实验证明,对数数据量为40240的平面点,快速算法的时间为29毫秒/朴素算法的时间为:19017毫秒 float close_point(Point *_point,const int size) float *_distance=new floatsize1; Point *_object=(Point *)malloc(sizeof(Point *)*(size+1)1);/记录被选中的点的数目 int _object_count; int k,_step,j; float _near1,_near2; float x,y; / int _origin,_final;/首先,将两个相邻的点的距离计算出来 for(k=0;k1=sqrt(x*x+y*y); /分段计算最小两点间最小距离 for(_step=2;(1_step)=size;_step=_step+1) for(k=0;k size;k+=(1_step) int _origin=k;/左边界 int _final=k+(1_step-1;/上一次在左边界所取得的最小值 _near2=_distance(k_step-1)+1;/上一次在右边界所取得的最小值 float _min=_near1_near2?_near1:_near2; int _boundary=_origin+(1=_origin & x-_pointj.x =_min ;-j)/左侧 _object_object_count+=_point+j; for(j=_boundary;j_final & _pointj.x-x=_min;+j) _object_object_count+=_point+j; _insert_sorty(_object,_object_count);/对所得到的数组按照y坐标进行升序排序 for(j=0;j_object_count-1;+j) _boundary=j+6_object_count?j+6:_object_count; for(_origin=j+1;_originx-_object_origin-x; y=_objectj-y-_object_origin-y; _near1=sqrt(x*x+y*y); if(_min_near1) _min=_near1; _distancek_step=_min; _near1=_distance0; delete _distance; free(_object); return _near1; /朴素的算法 float prim_close_point(const Point *_point,const int size) float x,y; float _min=1e8; for(int i=0;isize;+i) for(int k=i+1;k_near) _min=_near; return _min; int main(int argc,char *argv) Point *_point=(Point *)malloc(sizeof(Point)*40240); const int size=40240; int i,k,j=0; Point _temp; srand(int)time(NULL); for(i=0;isize;+i) _pointi.x=rand(); _pointi.y=rand(); for(i=0;isize;+i ) j=i; for(k=i+1;ksize;+k) if(_pointk.x_pointj.x) j=k; if(j != i) _temp=_pointj; _pointj=_pointi; _pointi=_temp; / for(i=0;i%fn,i,_pointi.x);/测试两者需要耗费的时间 #ifdef _TEST_ time_t _start,_final; _start=clock(); float _near1=close_point(_point,size); _final=clock(); printf(fast method cost time %fn,difftime(_final,_start); _start=clock(); float _near2=prim_close_point(_point,size); _final=clock(); printf(prim method cost time: %fn,difftime(_final,_s