计算最远点对距离 | Baeldung中文网

1. 概述

在本教程中，我们将探讨如何从一组给定的二维点中找出距离最远的点对，并计算其欧几里得距离。

我们会先定义问题并举例说明，接着介绍两种不同的解法：

暴力解法：遍历所有点对，计算它们之间的距离，找出最大值。时间复杂度为 O(N²)。
旋转卡壳法（Rotate Calipers）：利用凸包（Convex Hull）和凸多边形直径（Diameter）的性质，将问题优化到 O(N log N) 的时间复杂度。

2. 问题定义

给定一组二维平面上的点，我们要找出其中距离最远的一对点。点对之间的距离定义为欧几里得距离：

$$ \text{distance}(P, Q) = \sqrt{(P.x - Q.x)^2 + (P.y - Q.y)^2} $$

示例

假设我们有如下三个点：

$ P_1(0, 3) $
$ P_2(0, 0) $
$ P_3(4, 0) $

它们构成的点对有三种组合：

$ P_1 - P_2 $ 距离为 3
$ P_1 - P_3 $ 距离为 5 ✅
$ P_2 - P_3 $ 距离为 4

因此，最大距离为 5，对应点对 $ P_1 $ 和 $ P_3 $。

geo1

3. 暴力解法

3.1 核心思想

遍历所有点对，计算它们之间的距离，并记录最大值。

3.2 算法实现（Java）

public double maxDistanceBruteForce(List<Point> points) {
    double maxDist = 0;
    int n = points.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            double dist = distance(points.get(i), points.get(j));
            maxDist = Math.max(maxDist, dist);
        }
    }
    return maxDist;
}

private double distance(Point a, Point b) {
    return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
}

3.3 时间复杂度

时间复杂度：O(N²)
空间复杂度：O(1)

适用于点数较少的场景。当 N 较大时，性能下降明显，不推荐使用。

4. 旋转卡壳法（Rotate Calipers）

4.1 核心思想

最远点对一定出现在凸包的顶点上，并且其距离等于该凸多边形的直径（Diameter）。

该方法分为两个阶段：

构建凸包（Convex Hull）
使用旋转卡壳法（Rotate Calipers）找出凸包上的最远点对

4.2 构建凸包（Graham Scan 实现）

public List<Point> convexHull(List<Point> points) {
    if (points.size() < 3) return points;

    // 找出最左下角的点作为起点
    Point start = Collections.min(points, (a, b) -> {
        if (a.x != b.x) return Integer.compare(a.x, b.x);
        return Integer.compare(a.y, b.y);
    });

    // 按极角排序
    List<Point> sorted = new ArrayList<>(points);
    sorted.remove(start);
    sorted.sort((a, b) -> {
        int orientation = orientation(start, a, b);
        if (orientation == 0) {
            return Double.compare(start.distanceTo(a), start.distanceTo(b));
        }
        return orientation < 0 ? -1 : 1;
    });

    List<Point> hull = new ArrayList<>();
    hull.add(start);

    for (Point p : sorted) {
        while (hull.size() >= 2 &&
               orientation(hull.get(hull.size() - 2), hull.get(hull.size() - 1), p) <= 0) {
            hull.remove(hull.size() - 1);
        }
        hull.add(p);
    }

    return hull;
}

private int orientation(Point o, Point a, Point b) {
    double cross = (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
    if (cross < 0) return -1;
    else if (cross > 0) return 1;
    else return 0;
}

示例图

geo2

4.3 计算凸多边形直径（Rotate Calipers）

public double rotateCalipers(List<Point> hull) {
    int n = hull.size();
    if (n == 2) return hull.get(0).distanceTo(hull.get(1));

    int q = 1;
    double maxDist = 0;

    for (int p = 0; p < n; p++) {
        while (area(hull.get(p), hull.get((p + 1) % n), hull.get((q + 1) % n)) >
               area(hull.get(p), hull.get((p + 1) % n), hull.get(q))) {
            q = (q + 1) % n;
        }

        double dist = hull.get(p).distanceTo(hull.get(q));
        maxDist = Math.max(maxDist, dist);
    }

    return maxDist;
}

private double area(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

示例图

geo3

4.4 时间复杂度分析

构建凸包：O(N log N)
旋转卡壳计算直径：O(N)
总复杂度：O(N log N)

适合大规模数据集，是性能更优的解法。

5. 总结

方法	时间复杂度	适用场景
暴力解法	O(N²)	小规模数据
旋转卡壳法	O(N log N)	大规模数据

本文我们介绍了如何找出二维平面上最远的点对，以及两种解决方法：

暴力解法：简单直接，但效率低。
旋转卡壳法：结合凸包与旋转卡壳技巧，效率更高，适合处理大量数据。

在实际应用中，如果点数较多，建议优先使用旋转卡壳法。

Persistence

REST

Security