Liny_@NotePad

沉迷ACG中

分治法：平面最近点对问题

YOYO posted @ 2009年4月29日 08:03 in 【算法】与【数据结构】 with tags 分治 , 9327 阅读

当一个点集中只有两个点时，它们的距离就是最近距离；
当一个点集中有三个点时，它们的距离也可以直接求出；
当一个点集中的点数量大于3时，则将数组拆分成两半，分别计算左右子集的最近距离的平方d（将数量>3的数组一直拆分，最后到只有2个或3个点的点集时即能求解），收集距离中线两侧小于d的点，在这些点中寻找垂直距离小于d的两个点，若存在则说明其为当前能找到的最近点对，更新d为这两点的距离。

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cmath>
  4. using namespace std;
  5.  
  6. /*      存储点的结构    */
  7. typedef struct{
  8.         float x,y;      //    点的x,y坐标
  9. }POINT;
  10.  
  11. /* 辅助的点结构 */
  12. typedef struct{
  13.         int index;      //    点在X数组中的下标
  14.         float x, y;     //   点的x,y坐标
  15. }A_POINT;
  16.  
  17. /* 对点进行递增顺序排序的比较 */
  18. bool compareX(POINT a, POINT b){
  19.         return b.x>a.x;
  20. }
  21.  
  22. /* 对辅助点进行递增排序的比较 */
  23. bool compareY(A_POINT a, A_POINT b){
  24.         return b.y>a.y;
  25. }
  26.  
  27. /* 计算两点距离的平方 */
  28. float dist(POINT a, POINT b){
  29.         float dx, dy;
  30.         dx = a.x - b.x, dy = a.y - b.y;
  31.         return (dx*dx+dy*dy);
  32. }
  33.  
  34. /************************************************************************
  35. * 求平面点集最近点对的分治算法
  36. *
  37. * 输入：存放平面点集点的数组X[]、辅助点数组Y[]，数组起点下标low与终点下标high
  38. * 输出：最近点对a,b及距离d
  39. **********************************************************************/
  40. void closest(POINT X[], A_POINT Y[], int low, int high, POINT &a, POINT &b, float &d){
  41.         int i,j,k,m;
  42.         POINT al,bl,ar,br;
  43.         float dl,dr;
  44.         if((high-low)==1){            //    当n=2时直接计算
  45.                 a = X[low], b = X[high], d = dist(X[low], X[high]);
  46.         }else{
  47.                 if((high-low)==2){      //    当n=3时直接计算
  48.                         dl = dist(X[low], X[low+1]);
  49.                         dr = dist(X[low], X[low+2]);
  50.                         d = dist(X[low+1], X[low+2]);
  51.                         if((dl<=dr)&&(dl<=d)){
  52.                                 a = X[low], b = X[low+1], d = dl;
  53.                         }else{
  54.                                 if(dr<=d){
  55.                                         a = X[low], b = X[low+2], d= dr;
  56.                                 }else{
  57.                                         a = X[low+1], b = X[low+2];
  58.                                 }
  59.                         }
  60.                 }else{        //        当n>3时进行分治
  61.                         A_POINT *SL = new A_POINT[(high-low)/2+1];
  62.                         A_POINT *SR = new A_POINT[(high-low)/2];
  63.  
  64.                         m = (high-low)/2 + low;    //       把x数组以m为界划分为两半
  65.                         j = k = 0;
  66.                         for(i=0; i<=high-low; i++){     
  67.                                 if(Y[i].index<=m){
  68.                                         SL[j++] = Y[i];   //       收集左边子集中的最近点对
  69.                                 }else{
  70.                                         SR[k++] = Y[i];   //       收集右边子集中的最近点对
  71.                                 }
  72.                         }
  73.  
  74.                         closest(X,SL,low, m, al, bl, dl);       //     计算左边子集的最近点对
  75.                         closest(X,SR,m+1, high, ar, br, dr);//  计算右边子集的最近点对
  76.  
  77.                         if(dl<dr){                              //    组合步得到左右子集中点的最短距离d
  78.                                 a = al, b = bl, d = dl;
  79.                         }else{
  80.                                 a = ar, b = br, d = dr;
  81.                         }
  82.  
  83.                         POINT *Z = new POINT[high-low+1];
  84.                         k = 0;
  85.                         for( i=0; i<=high -low; i++){      // 收集距离中线距离小于d的元素，保存到数组Z（因Y数组按y坐标递增排序，Z数组也一样）
  86.                                 if(fabs(X[m].x - Y[i].x)<d){
  87.                                         Z[k].x = Y[i].x, Z[k++].y = Y[i].y;
  88.                                 }
  89.                         }
  90.                         for( i=0; i<k; i++){
  91.                                 for( j=i+1; (j<k)&&(Z[j].y-Z[i].y<d); j++){     //   若前后两点y轴的距离超过d则不可能使距离小于d，退出
  92.                                         dl = dist(Z[i], Z[j]);    //        计算前后两点的距离
  93.                                         if(dl<d){                                   //     若小于d，则更新
  94.                                                 a = Z[i], b = Z[j], d = dl;
  95.                                         }
  96.                                 }
  97.                         }
  98.  
  99.                         delete SL;
  100.                         delete SR;
  101.                         delete Z;
  102.                 }
  103.         }
  104. }
  105.  
  106. /**********************************************
  107. * 求平面点集最近点对的分治算法
  108. *
  109. * 输入：存放平面点集点的数组X[]，点的个数n
  110. * 输出：最近点对a,b及距离d
  111. **********************************************/
  112. void closest_pair(POINT X[], int n, POINT &a, POINT &b, float &d){
  113.         if(n<2){        //      当点集个数小于2时不存在最近点对
  114.                 d = 0;
  115.         }else{
  116.                 sort(X,X+n, compareX);      //        对x数组进行递增排序
  117.                 A_POINT *Y = new A_POINT[n];    //  初始化辅助点数组Y
  118.                 for( int i = 0 ; i < n ;i ++){
  119.                         Y[i].index = i;
  120.                         Y[i].x = X[i].x;
  121.                         Y[i].y = X[i].y;
  122.                 }
  123.                 sort(Y,Y+n, compareY);      //        对y数组进行递增排序
  124.                 closest(X,Y,0,n-1,a,b,d);              //     求亲密点对
  125.                 d = sqrt(d);                //  将得到的d开平方才是两点间真正的距离
  126.                 delete Y;
  127.         }
  128. }
  129.  
  130. int main(){
  131.         int n;
  132.  
  133.         cout<<"请输入点个数：";
  134.         cin>>n;
  135.  
  136.         cout<<"请输入各个点的坐标："<<endl;
  137.         POINT *X = new POINT[n];
  138.         for(int i=0; i<n; i++){
  139.                 cin>>X[i].x>>X[i].y;
  140.         }
  141.  
  142.         POINT a,b;
  143.         float d;
  144.         closest_pair(X,n,a,b,d);
  145.        
  146.         if(n>=2){
  147.                 printf("(%.2f,%.2f) - (%.2f,%.2f) : %.2f\n", a.x, a.y, b.x, b.y, d);
  148.         }else{
  149.                 printf("不存在最近点对！\n");
  150.         }
  151.        
  152.         delete X;
  153.         return 0;
  154. }

 

Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter