镜之国的爱丽丝
0%

08 - 点集中找最近点对 - 分治法

发表于 更新于 分类于

1. 算法思路

时间复杂度 ： O(n⋅logn)O(n \cdot logn)
该算法采用分治法，问题被分解为两个子问题，合并的复杂度为 O(n)O(n)，所以：T(n)=2⋅T(n2)+nT(n)=2 \cdot T(\frac {n} {2})+n
即时间复杂度为：O(n⋅logn)O(n \cdot logn)

2. 示例代码

2.1 import

1
2
3
4
5
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import primitives.Point;

2.2 分治法

2.2.1 外部方法

1
2
3
4
5
6
7
8
9
public static ArrayList<Point> Fast(ArrayList<Point> points) {
    ArrayList<Point> X = (ArrayList<Point>)points.clone();
    ArrayList<Point> Y = (ArrayList<Point>)points.clone();

    Collections.sort(X, new PointComparatorX());
    Collections.sort(Y, new PointComparatorY());

    return ClosestPair(X, Y);
}

暴露给外部进行调用的方法，先对点集分别按X和Y坐标排序，分成两个序列

2.2.2 递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
private static ArrayList<Point> ClosestPair(ArrayList<Point> X, ArrayList<Point> Y) {
            
    ArrayList<Point> resultPair = new ArrayList<Point>();

    // 递归的子叶操作: |P| <= 3
    if (X.size() <= 1) {
        resultPair = null;
    } else if (X.size() == 2) {
        resultPair = X;
    } else if (X.size() == 3) {
        // |P| == 3 => 直接暴力求解
        // 将距离最小的点对加入至点集 resultPair
        double dist1 = dist(X.get(0), X.get(1));
        double dist2 = dist(X.get(0), X.get(2));
        double dist3 = dist(X.get(1), X.get(2));

        if (dist2 < dist3) {
            if (dist1 < dist2) {
                resultPair.add(X.get(0));
                resultPair.add(X.get(1));
            } else {
                resultPair.add(X.get(0));
                resultPair.add(X.get(2));
            }
        } else {
            if (dist1 < dist3) {
                resultPair.add(X.get(0));
                resultPair.add(X.get(1));
            } else {
                resultPair.add(X.get(1));
                resultPair.add(X.get(2));
            }
        }
    }
    // 递归步骤：分治
    else {
        // 按X坐标取中位数 lX
        double lX = (X.get(X.size() / 2)).getX();

        // 按中位点划分 ...
        ArrayList<Point> XL = new ArrayList<Point>();
        ArrayList<Point> XR = new ArrayList<Point>();

        for (int i = 0; i < X.size(); i++) {
            if ((X.get(i)).getX() <= lX) {
                XL.add(X.get(i));
            } else {
                XR.add(X.get(i));
            }
        }

        ArrayList<Point> YL = new ArrayList<Point>();
        ArrayList<Point> YR = new ArrayList<Point>();

        for (int i = 0; i < Y.size(); i++) {
            if ((Y.get(i)).getX() <= lX) {
                YL.add(Y.get(i));
            } else {
                YR.add(Y.get(i));
            }
        }
        
        // 当所有点都移到左边时，退化的情况应谨慎对待。 这种情况发生在当所有点都具有相同的X坐标时。
        // TODO（mikhaildubov）：如果所有点都在Y轴上，则性能可能会降低到 O(n^2) 。
        if (XR.size() == 0) {
            // 临时解决方案：只需将“最右边”的点从XL移到XR
            Point repl = XL.get(XL.size()-1);
            
            XL.remove(repl);
            XR.add(repl);
            
            YL.remove(repl);
            YR.add(repl);
        }
        

        // ... 治 ...
        ArrayList<Point> ClosestLeft = ClosestPair(XL, YL);
        ArrayList<Point> ClosestRight = ClosestPair(XR, YR);
        ArrayList<Point> ClosestBetween = ClosestBetweenSubsets(X, Y,
                                            Math.min(dist(ClosestLeft), dist(ClosestRight)));

        double distLeft = dist(ClosestLeft);
        double distRight = dist(ClosestRight);
        double distBetween = dist(ClosestBetween);

        // ... 结合
        // ... resultPair = min{distLeft, distRight, distBetween}
        if (distLeft < distRight) {
            if (distBetween < distLeft) {
                resultPair = ClosestBetween;
            } else {
                resultPair = ClosestLeft;
            }
        } else {
            if (distBetween < distRight) {
                resultPair = ClosestBetween;
            } else {
                resultPair = ClosestRight;
            }
        }
    }

    return resultPair;
}

screenShot.png

1. 按 X 坐标进行排序，获得点序列 X ，取序列的中位数 lX
- 将 [0 , lX] 的点分别加入点集 XL 和 YL
- 将 [lX , size - 1] 的点分别加入点集 XR 和 YR ；
2. 左右子集分别调用 ClosestPair() 进行递归，分别获得左右子集中的最近点对，其距离分别为 distLeft 和 distRight
3. 取 distLeft 和 distRight 的最小值 distMin ，即 distMin = min { distLeft, distRight }
4. 调用 ClosestBetweenSubsets() 方法，取中线左右间距 distMin 区域内的点加入点集 Y2 ，找到其中的最近点对，距离为 distBetween
5. 结果取 resultPair = min{distLeft, distRight, distBetween}

  • 图中情况为：
L R Y2
P0P_0，P1P_1，P2P_2，P3P_3 P4P_4，P5P_5，P6P_6 P2P_2，P3P_3，P4P_4，P5P_5
  • 其中：distMin = distLeft ，区域取中线左右间距 distMin ，获得点集 Y2
  • 调用 ClosestBetweenSubsets() 方法后，找到最近点对 P3−P4P_3-P_4 和间距 distBetween
  • 最后 resultPair = distBetween

2.2.3 子集间最接近的点对

对于每个点只需要检查水平间距最近的 8 个点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
private static ArrayList<Point> ClosestBetweenSubsets(ArrayList<Point> X, ArrayList<Point> Y, double d) {
    double lX = (X.get(X.size() / 2)).getX();

    // 填写 Y2 列表
    ArrayList<Point> Y2 = new ArrayList<Point>();
    for (int i = 0; i < Y.size(); i++) {
        if (Math.abs((Y.get(i)).getX() - lX) <= d) {
            Y2.add(Y.get(i));
        }
    }

    // 遍历 Y2 以寻找最近的点
    if (Y2.size() < 2) {
        return null;
    }

    Point p1 = Y2.get(0);
    Point p2 = Y2.get(1);

    // 仅检查 7 个点就足够
    for (int i = 0; i < Y2.size() - 1; i++) {
        for (int j = i + 1; j <= Math.min(i + 8, Y2.size() - 1); j++)
            if (dist(Y2.get(i), Y2.get(j)) < dist(p1, p2)) {
                p1 = Y2.get(i);
                p2 = Y2.get(j);
            }
    }

    ArrayList resultPair = new ArrayList();
    resultPair.add(p1);
    resultPair.add(p2);

    return resultPair;
}

2.3 比较器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 依据X坐标比较
static class PointComparatorX implements Comparator<Point> {

    @Override
    public int compare(Point p1, Point p2) {
        
        if (p1.getX() < p2.getX()) return -1;
        if (p1.getX() > p2.getX()) return 1;
        return 0;
    }
}

// 依据Y坐标比较
static class PointComparatorY implements Comparator<Point> {
    
    @Override
    public int compare(Point p1, Point p2) {
            
        if (p1.getY() < p2.getY()) return -1;
        if (p1.getY() > p2.getY()) return 1;
        return 0;
    }
}

2.4 其他方法

2.4.1 计算点对的间距

1
2
3
4
5
6
7
8
9
10
private static double dist(ArrayList<Point> pair) {
    if (pair == null || pair.size() != 2) {
        return Double.POSITIVE_INFINITY;
    } else {
        return Math.sqrt(((pair.get(1)).getX() - (pair.get(0)).getX()) * ((pair.get(1)).getX() - (pair.get(0)).getX()) +
                        ((pair.get(1)).getY() - (pair.get(0)).getY()) * ((pair.get(1)).getY() - (pair.get(0)).getY()));
    }
}