【测试】经典分治算法求解最近点对

gzxl

测试1
采集点 100000 个
最近点对距离 = 0.312
分治算法求解最近点对用时: 31 毫秒

测试2
采集点 157011 个
最近点对距离 = 0.028
分治算法求解最近点对用时: 46 毫秒

测试3
采集点 1436160 个
最近点对距离 = 0.003
分治算法求解最近点对用时: 1828 毫秒

1. // 归并排序的归并操作（对y排序）
   
2. static void Merge(AcGePoint3dArray &pts, int nLeft, int nRight)
   
3. {
   
4.     int mid = (nLeft + nRight) / 2;
   
5.     int i = nLeft;
   
6.     int j = mid + 1;
   
7.     AcGePoint3dArray resPts;
   
8.     while (i <= mid && j <= nRight)
   
9.     {
   
10.         if (pts.at(i).y < pts.at(j).y)
    
11.             resPts.append(pts.at(i++));
    
12.         else
    
13.             resPts.append(pts.at(j++));
    
14.     }
    
15.     while (i <= mid)
    
16.         resPts.append(pts.at(i++));
    
17.     while (j <= nRight)
    
18.         resPts.append(pts.at(j++));
    
19.     for (int i = nLeft; i < resPts.length(); i++)
    
20.         pts.at(i) = resPts.at(i);
    
21. }

复制代码

1. // 计算点对距离
   
2. static double distance(const AcGePoint3d& p1, const AcGePoint3d& p2)
   
3. {
   
4.     return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
   
5. }

复制代码

1. // 分治法找最近点对
   
2. static double mergeMethod(AcGePoint3dArray &pts, int nLeft, int nRight, AcGePoint3d &p1, AcGePoint3d &p2)
   
3. {
   
4.     if (nRight - nLeft <= 1)
   
5.         return INT_MAX;
   
6.     else if (nRight - nLeft == 2)
   
7.     {
   
8.         Merge(pts, nLeft, nRight);//确保每个小单元的两个点对的y轴是有序的，才能保证后续对y归并排序的复杂度
   
9.         p1 = pts.at(nLeft);
   
10.         p2 = pts.at(nRight);
    
11.         return distance(p1, p2);
    
12.     }
    
13.     else
    
14.     {
    
15.         AcGePoint3d l1, l2, r1, r2;
    
16.         int mid = (nLeft + nRight) / 2;
    
17.         double mindis = INT_MAX;
    
18.         double middleX = pts.at(mid).x; //中线
    
19.         double mindis1 = mergeMethod(pts, nLeft, mid, l1, l2);      // 左侧最近点对
    
20.         double mindis2 = mergeMethod(pts, mid + 1, nRight, r1, r2); // 右侧最近点对
    
21.         if (mindis1 < mindis2)
    
22.         {
    
23.             mindis = mindis1;
    
24.             p1 = l1;
    
25.             p2 = l2;
    
26.         }
    
27.         else
    
28.         {
    
29.             mindis = mindis2;
    
30.             p1 = r1;
    
31.             p2 = r2;
    
32.         }
    
33.         AcGePoint3dArray temp;
    
34.         Merge(pts, nLeft, nRight); // 按照y排序
    
35.         for (int i = nLeft; i <= nRight; i++)   //找到在中间区域的点
    
36.         {
    
37.             if (fabs(pts.at(i).x - middleX) <= mindis)
    
38.             {
    
39.                 temp.append(pts.at(i));
    
40.             }
    
41.         }
    
42.         double tempDis = INT_MAX;
    
43.         // 遍历中间数组，每个点最多遍历其他点6次，记录最短距离和点对
    
44.         for (int i = 0; i < temp.length(); i++)
    
45.         {
    
46.             for (int j = i + 1; j < i + 1 + 6 && j < temp.length(); j++)
    
47.             {
    
48.                 tempDis = distance(temp[i], temp[j]);
    
49.                 if (tempDis < mindis)
    
50.                 {
    
51.                     mindis = tempDis;
    
52.                     p1 = temp[i];
    
53.                     p2 = temp[j];
    
54.                 }
    
55.             }
    
56.         }
    
57.         return mindis;
    
58.     }
    
59. }

复制代码

flz0728

橡皮

距离那个地方使用距离平方也行吧