每日算法 — 使用java实现旋转卡壳：凸包对踵点与最远点对查找优化

引言

旋转卡壳（Rotating Calipers）是计算几何中一种优雅而高效的算法技术，由Shamos于1978年提出。它常用于解决与凸包相关的各种问题，如凸包直径、最小面积外接矩形、凸包间距离等。算法的核心思想如同用一对平行线”夹住”凸包，然后绕凸包旋转这对平行线，在旋转过程中统计所需信息。

算法原理

1. 对踵点（Antipodal Points）

对于凸多边形的每条边，都存在一个或两个顶点，使得过该顶点与边平行的直线距离这条边最远。这样的顶点与边（或边的两个端点）称为对踵点对。

2. 旋转过程

1. 先计算点集的凸包（使用Graham扫描或Andrew单调链）
2. 找到初始对踵点对（如y坐标最小和最大的点）
3. 依次旋转平行线，每次旋转角度等于当前边与下一条边的夹角
4. 在旋转过程中维护所需的最优值

3. 核心性质

• 对踵点对的数量不超过3n/2个（n为凸包顶点数）
• 可在O(n)时间内找到所有对踵点对

Java实现

import java.util.*;

/**
 * 旋转卡壳算法实现
 * 用于求解凸包直径、最小外接矩形等问题
 */
public class RotatingCalipers {

    /**
     * 二维点类
     */
    static class Point {
        double x, y;
        Point(double x, double y) { this.x = x; this.y = y; }

        @Override
        public String toString() {
            return String.format("(%.2f, %.2f)", x, y);
        }
    }

    /**
     * 向量减法
     */
    static Point sub(Point a, Point b) {
        return new Point(a.x - b.x, a.y - b.y);
    }

    /**
     * 叉积：OA × OB
     */
    static double cross(Point o, Point a, Point b) {
        return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
    }

    /**
     * 向量叉积
     */
    static double cross(Point a, Point b) {
        return a.x * b.y - a.y * b.x;
    }

    /**
     * 点积
     */
    static double dot(Point a, Point b) {
        return a.x * b.x + a.y * b.y;
    }

    /**
     * 向量长度平方
     */
    static double dist2(Point a, Point b) {
        double dx = a.x - b.x, dy = a.y - b.y;
        return dx * dx + dy * dy;
    }

    /**
     * 向量长度
     */
    static double dist(Point a, Point b) {
        return Math.sqrt(dist2(a, b));
    }

    /**
     * Andrew单调链算法求凸包
     * 时间复杂度：O(n log n)
     */
    static List<Point> convexHull(List<Point> points) {
        int n = points.size();
        if (n <= 1) return new ArrayList<>(points);

        // 按x排序，x相同按y排序
        List<Point> sorted = new ArrayList<>(points);
        sorted.sort((a, b) -> {
            if (Math.abs(a.x - b.x) > 1e-9) return Double.compare(a.x, b.x);
            return Double.compare(a.y, b.y);
        });

        List<Point> hull = new ArrayList<>();

        // 下凸包
        for (Point p : sorted) {
            while (hull.size() >= 2 && 
                   cross(hull.get(hull.size()-2), hull.get(hull.size()-1), p) <= 1e-9) {
                hull.remove(hull.size() - 1);
            }
            hull.add(p);
        }

        // 上凸包
        int lowerSize = hull.size();
        for (int i = n - 2; i >= 0; i--) {
            Point p = sorted.get(i);
            while (hull.size() > lowerSize && 
                   cross(hull.get(hull.size()-2), hull.get(hull.size()-1), p) <= 1e-9) {
                hull.remove(hull.size() - 1);
            }
            hull.add(p);
        }

        hull.remove(hull.size() - 1); // 移除重复的第一个点
        return hull;
    }

    /**
     * 旋转卡壳求凸包直径（最远点对距离）
     * 时间复杂度：O(n)，n为凸包顶点数
     */
    static double diameter(List<Point> hull) {
        int n = hull.size();
        if (n == 0) return 0;
        if (n == 1) return 0;
        if (n == 2) return dist(hull.get(0), hull.get(1));

        // 找到y坐标最大和最小的点作为初始对踵点
        int j = 1;
        double maxDist = 0;

        for (int i = 0; i < n; i++) {
            int ni = (i + 1) % n;
            // 当i-j边与j+1点的距离不增加时停止
            while (true) {
                int nj = (j + 1) % n;
                double cur = Math.abs(cross(hull.get(i), hull.get(ni), hull.get(j)));
                double nxt = Math.abs(cross(hull.get(i), hull.get(ni), hull.get(nj)));
                if (nxt > cur + 1e-9) {
                    j = nj;
                } else {
                    break;
                }
            }

            // 更新最大距离
            double d = dist2(hull.get(i), hull.get(j));
            if (d > maxDist) maxDist = d;
            d = dist2(hull.get(ni), hull.get(j));
            if (d > maxDist) maxDist = d;
        }

        return Math.sqrt(maxDist);
    }

    /**
     * 旋转卡壳求最小面积外接矩形
     * 返回：{最小面积, 最小周长, 矩形四个顶点}
     */
    static Object[] minAreaEnclosingRectangle(List<Point> hull) {
        int n = hull.size();
        if (n <= 1) return new Object[]{0.0, 0.0, null};
        if (n == 2) {
            double len = dist(hull.get(0), hull.get(1));
            return new Object[]{0.0, 2 * len, null};
        }

        // 预计算每条边的方向向量长度
        int[] nxt = new int[n];
        for (int i = 0; i < n; i++) nxt[i] = (i + 1) % n;

        // 找到四条边上的最远点（初始状态）
        int i = 0, j = 0, k = 0, l = 0;

        // 找到x最大、y最大、x最小的点
        for (int idx = 1; idx < n; idx++) {
            if (hull.get(idx).x > hull.get(i).x) i = idx;
            if (hull.get(idx).y > hull.get(j).y) j = idx;
            if (hull.get(idx).x < hull.get(k).x) k = idx;
            if (hull.get(idx).y < hull.get(l).y) l = idx;
        }

        double minArea = Double.MAX_VALUE;
        double minPerimeter = Double.MAX_VALUE;
        List<Point> bestRect = null;

        // 当前四条边的角度（与x轴的夹角）
        double[] angles = new double[n];
        for (int idx = 0; idx < n; idx++) {
            Point edge = sub(hull.get(nxt[idx]), hull.get(idx));
            angles[idx] = Math.atan2(edge.y, edge.x);
        }

        // 旋转n次，每次处理一条边
        for (int edgeIdx = 0; edgeIdx < n; edgeIdx++) {
            Point edge = sub(hull.get(nxt[edgeIdx]), hull.get(edgeIdx));
            double edgeLen = Math.sqrt(dot(edge, edge));
            Point unitEdge = new Point(edge.x / edgeLen, edge.y / edgeLen);
            Point perp = new Point(-unitEdge.y, unitEdge.x); // 垂直单位向量

            // 计算四个方向的投影范围
            double minProj = Double.MAX_VALUE, maxProj = -Double.MAX_VALUE;
            double minPerp = Double.MAX_VALUE, maxPerp = -Double.MAX_VALUE;

            for (Point p : hull) {
                double proj = dot(sub(p, hull.get(0)), unitEdge);
                double perpProj = dot(sub(p, hull.get(0)), perp);
                minProj = Math.min(minProj, proj);
                maxProj = Math.max(maxProj, proj);
                minPerp = Math.min(minPerp, perpProj);
                maxPerp = Math.max(maxPerp, perpProj);
            }

            double width = maxProj - minProj;
            double height = maxPerp - minPerp;
            double area = width * height;
            double perimeter = 2 * (width + height);

            if (area < minArea) {
                minArea = area;
                minPerimeter = perimeter;
                // 计算矩形四个顶点
                bestRect = new ArrayList<>();
                Point origin = hull.get(0);
                Point base = new Point(origin.x + minProj * unitEdge.x + minPerp * perp.x,
                                       origin.y + minProj * unitEdge.y + minPerp * perp.y);
                bestRect.add(base);
                bestRect.add(new Point(base.x + width * unitEdge.x, base.y + width * unitEdge.y));
                bestRect.add(new Point(base.x + width * unitEdge.x + height * perp.x,
                                       base.y + width * unitEdge.y + height * perp.y));
                bestRect.add(new Point(base.x + height * perp.x, base.y + height * perp.y));
            }
        }

        return new Object[]{minArea, minPerimeter, bestRect};
    }

    public static void main(String[] args) {
        // 测试案例：随机点集
        List<Point> points = new ArrayList<>();
        points.add(new Point(0, 0));
        points.add(new Point(2, 0));
        points.add(new Point(3, 1));
        points.add(new Point(2, 2));
        points.add(new Point(0, 2));
        points.add(new Point(1, 1)); // 内部点

        List<Point> hull = convexHull(points);
        System.out.println("凸包顶点：" + hull.size() + "个");
        for (Point p : hull) System.out.println("  " + p);

        double diam = diameter(hull);
        System.out.println("凸包直径：" + String.format("%.4f", diam));

        Object[] result = minAreaEnclosingRectangle(hull);
        System.out.println("最小外接矩形面积：" + String.format("%.4f", (Double)result[0]));
        System.out.println("最小外接矩形周长：" + String.format("%.4f", (Double)result[1]));
    }
}

复杂度分析

应用场景

1. 碰撞检测：计算物体包围盒，快速排除不相交的情况
2. 模式识别：形状描述与特征提取
3. 计算机视觉：物体定位与姿态估计
4. GIS系统：区域覆盖与边界分析

总结

旋转卡壳算法展示了计算几何中”旋转扫描”思想的强大威力。通过与凸包结合，它能在O(n)时间内解决许多看似复杂的几何问题。掌握这一技巧对于处理二维几何问题具有重要价值。