《算法》BEYOND 部分程序 part 3

▶ 书中第六章部分程序，加上自己补充的代码，包括 Graham 扫描生成凸包，计算最远点对

● Graham 扫描生成凸包

package package01;

import java.util.Arrays;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.Stack;

public class class01
{
    private Stack<Point2D> hull = new Stack<Point2D>();

    public class01(Point2D[] points)
    {
        if (points == null || points.length == 0)
            throw new IllegalArgumentException("argument is null");
        int n = points.length;
        Point2D[] a = new Point2D[n];
        for (int i = 0; i < n; i++)
            a[i] = points[i];

        Arrays.sort(a);                             // Y 坐标升序排序，等值的按 X 坐标升序排序，保证 a[0] 为最下最左，a[1] 为
        Arrays.sort(a, 1, n, a[0].polarOrder());    // 以 a[0] 为原点，幅角升序排序
        hull.push(a[0]);                            // 第一个点
        int k1;                                     // 找到下一个相异点
        for (k1 = 1; k1 < n; k1++)
        {
            if (!a[0].equals(a[k1]))
                break;
        }
        if (k1 == n)
            return;
        int k2;                                     // 找到下一个非共线点
        for (k2 = k1 + 1; k2 < n; k2++)
        {
            if (Point2D.ccw(a[0], a[k1], a[k2]) != 0)
                break;
        }
        hull.push(a[k2 - 1]);                       // a[k2-1] 是与 a[0]，a[k1] 共线的最后一个点（也可以先压 a[k1] 然后跳过 a[k2-1]）
        for (int i = k2; i < n; i++)
        {
            Point2D top = hull.pop();
            for (; Point2D.ccw(hull.peek(), top, a[i]) <= 0; top = hull.pop()); // 倒数第 2 点、倒数第 1 点和当前点计算三角形面积，逆时针方向为正
                                                                                // 吐栈吐到这 3 点的面积为正为止，压入倒数第 2 点当前点
            hull.push(top);
            hull.push(a[i]);
        }
        assert isConvex();
    }

    public Iterable<Point2D> hull()                 // 得到凸包的迭代器
    {
        Stack<Point2D> s = new Stack<Point2D>();
        for (Point2D p : hull)
            s.push(p);
        return s;
    }

    private boolean isConvex()                      // 检查凸性
    {
        int n = hull.size();
        if (n <= 2) return true;

        Point2D[] points = new Point2D[n];
        int k = 0;
        for (Point2D p : hull())
            points[k++] = p;

        for (int i = 0; i < n; i++)
        {
            if (Point2D.ccw(points[i], points[(i + 1) % n], points[(i + 2) % n]) <= 0)
                return false;
        }
        return true;
    }

    public static void main(String[] args)
    {
        int n = StdIn.readInt();
        Point2D[] points = new Point2D[n];
        for (int i = 0; i < n; i++)
        {
            int x = StdIn.readInt(), y = StdIn.readInt();
            points[i] = new Point2D(x, y);
        }
        class01 graham = new class01(points);
        for (Point2D p : graham.hull())
            StdOut.println(p);
    }
}

● 计算最远点对

package package01;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.GrahamScan;

public class class01
{
    private Point2D best1, best2;
    private double bestDistanceSquared = Double.NEGATIVE_INFINITY;  // 当前最远点对距离的平方

    public class01(Point2D[] points)
    {
        if (points == null || points.length <= 1)
            throw new IllegalArgumentException("constructor argument is null");

        GrahamScan graham = new GrahamScan(points);

        int m = 0;// 凸包点数
        for (Point2D p : graham.hull())
            m++;
        Point2D[] hull = new Point2D[m + 1];                        // 凸包顶点放入 a[1] ~ a[m]
        m = 1;
        for (Point2D p : graham.hull())
            hull[m++] = p;
        m--;                                                        // m 等于凸包顶点数

        if (m == 1) // 所有点都相同
            return;
        if (m == 2) // 所有点共线
        {
            best1 = hull[1];
            best2 = hull[2];
            bestDistanceSquared = best1.distanceSquaredTo(best2);
            return;
        }

        int k = 2;
        for (; Point2D.area2(hull[m], hull[1], hull[k + 1]) > Point2D.area2(hull[m], hull[1], hull[k]); k++);   // a[k] 是距离直线 a[1]a[m] 最远的点

        int j = k;
        for (int i = 1; i <= k && j <= m; i++)                      // j 搜索后半部分，i 搜索前半部分
        {
            update(hull[i], hull[j]);                               // i 挪动一位，检查 a[i] 和 a[j] 距离是否更大
            for (j++; (j <= m) && Point2D.area2(hull[i], hull[i + 1], hull[j]) > Point2D.area2(hull[i], hull[i + 1], hull[j - 1]); j++) 
                                                                    // j 挪动保持 a[j] 远离直线 a[i]a[i+1]
                update(hull[i], hull[j]);
        }
    }

    private void update(Point2D x, Point2D y)
    {
        double distanceSquared = x.distanceSquaredTo(y);            
        if (distanceSquared > bestDistanceSquared)
        {
            best1 = x;
            best2 = y;
            bestDistanceSquared = distanceSquared;
        }
    }

    public Point2D either()
    {
        return best1;
    }

    public Point2D other()
    {
        return best2;
    }

    public double distance()
    {
        return Math.sqrt(bestDistanceSquared);
    }

    public static void main(String[] args)
    {
        int n = StdIn.readInt();
        Point2D[] points = new Point2D[n];
        for (int i = 0; i < n; i++)
        {
            int x = StdIn.readInt(), y = StdIn.readInt();
            points[i] = new Point2D(x, y);
        }
        class01 farthest = new class01(points);
        StdOut.println(farthest.distance() + " from " + farthest.either() + " to " + farthest.other());
    }
}