Java实现最近点对问题（分治法解决计算几何经典难题）

上图展示了分治过程：红线为划分线，绿色区域表示需要额外检查的“带状区域”（strip）。

Java 实现代码

首先定义一个 Point 类：

class Point {    double x, y;        Point(double x, double y) {        this.x = x;        this.y = y;    }}

辅助函数：计算两点距离

public static double distance(Point p1, Point p2) {    return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) +                        (p1.y - p2.y) * (p1.y - p2.y));}

主函数：使用分治法求解

public static double closestUtil(Point[] Px, Point[] Py, int n) {    // 点数较少时直接暴力计算    if (n <= 3) {        double min = Double.MAX_VALUE;        for (int i = 0; i < n; ++i)            for (int j = i + 1; j < n; ++j)                if (distance(Px[i], Px[j]) < min)                    min = distance(Px[i], Px[j]);        return min;    }    // 划分    int mid = n / 2;    Point midPoint = Px[mid];    // 将 Py 分成左右两部分（保持 y 排序）    Point[] Pyl = new Point[mid];    Point[] Pyr = new Point[n - mid];    int li = 0, ri = 0;    for (int i = 0; i < n; i++) {        if (Py[i].x <= midPoint.x && li < mid)            Pyl[li++] = Py[i];        else            Pyr[ri++] = Py[i];    }    // 递归求左右最小距离    double dl = closestUtil(Px, Pyl, mid);    double dr = closestUtil(Px + mid, Pyr, n - mid);    double d = Math.min(dl, dr);    // 构建 strip：距离中线小于 d 的点    Point[] strip = new Point[n];    int j = 0;    for (int i = 0; i < n; i++)        if (Math.abs(Py[i].x - midPoint.x) < d)            strip[j] = Py[i];            j++;    // 检查 strip 中的点（最多只需检查后7个点）    return Math.min(d, stripClosest(strip, j, d));}public static double stripClosest(Point[] strip, int size, double d) {    double min = d;    for (int i = 0; i < size; ++i)        for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min; ++j)            if (distance(strip[i], strip[j]) < min)                min = distance(strip[i], strip[j]);    return min;}public static double closest(Point[] points) {    int n = points.length;        // 按 x 和 y 分别排序    Point[] Px = points.clone();    Point[] Py = points.clone();    Arrays.sort(Px, (a, b) -> Double.compare(a.x, b.x));    Arrays.sort(Py, (a, b) -> Double.compare(a.y, b.y));        return closestUtil(Px, Py, n);}

为什么 strip 中只需检查后7个点？

这是一个关键优化！数学上可以证明：在 d×2d 的矩形区域内，最多只能有8个点（包括边界），且任意两点距离 ≥ d。因此，每个点最多只需与后面7个点比较即可。这保证了合并步骤的时间复杂度为 O(n)。

总结

通过本教程，你已经掌握了如何用Java最近点对算法高效解决问题。我们使用了分治算法将时间复杂度从 O(n²) 降低到 O(n log n)，这是计算几何中的经典优化技巧。

掌握这个算法不仅能帮你应对面试题，还能加深你对递归、排序和空间划分的理解。快去动手试试吧！

如果你喜欢这篇关于Java几何算法的教程，欢迎分享给更多学习者！