《算法技术手册》一3.5.4 解决方案

3.5.4 解决方案

如果手动计算凸包，你应该可以很轻松地处理好各种极端情况。但是如果需要用计算机语言来描叙每一个步骤，我们可能会觉得比较困难。Graham扫描算法的关键点在于计算和最低点的极角大小。一旦计算并且排序之后，算法只需要遍历所有的点，不断地构建凸包并且根据新发现的信息调整结构即可。代码见例3-1。
例3-1：Graham扫描算法的实现
public class NativeGrahamScan implements IConvexHull {

public IPoint[] compute(IPoint[] pts) {
    int n = pts.length;
    if (n < 3) {
        returnpts;
    }
    // 如果最后一个点不是最低点，
    // 那么找到最低点，然后和数组中最后一个点交换
    int lowest = 0;
    double lowestY = pts[0].getY();
    for (inti = 1; i < n; i++) {
        if (pts[i].getY() < lowestY) {
            lowestY = pts[i].getY();
            lowest = i;
        }
    }
    if (lowest != n - 1) {
        IPoint temp = pts[n - 1];
        pts[n - 1] = pts[lowest];
        pts[lowest] = temp;
    }

    // 将pts[0...n-2]按照和pts[n-1]的极角按照从大到小降序排列
    new HeapSort<IPoint>().sort(pts, 0, n - 2,
                                new ReversePolarSorter(pts[n - 1]));
   
    // 有三个点一定在凸包上，它们分别是:
    // 极角最小点pts[n-2]、最低点pts[n-1]还有极角最大点p[0]
    // 初始化凸包，从pts[n-2]和pts[n-1]开始
    DoubleLinkedList<IPoint> list = new DoubleLinkedList<IPoint>();
    list.insert(pts[n - 2]);
    list.insert(pts[n - 1]);
    // 先处理多点共线的情况
    double firstAngle = Math.atan2(pts[0].getY() - lowest, 
                                   pts[0].getX() - pts[n - 1].getX());
    double lastAngle = Math.atan2(pts[n - 2].getY() - lowest, 
                                  pts[n - 2].getX() - pts[n - 1].getX());
    if (firstAngle == lastAngle) {
        return new IPoint[]{pts[n - 1], pts[0]};
    }

    // 顺序访问每个点，删掉不正确的点
    // 一定会出现某个点"向右转"，
    // 所以这个while循环必然能够结束
    for (int i = 0; i < n - 1; i++) {
        while (isLeftTurn(list.last().prev().value(), 
                          list.last().value(),
                          pts[i])) {
            list.removeLast();
        }

        // 将下一个点加入凸包中
        list.insert(pts[i]);
    }

    // 最后一个点是重复的，所以我们只需要从最低的点开始取n-1个点即可
    IPoint hull[] = new IPoint[list.size() - 1];
    DoubleNode<IPoint> ptr = list.first().next();
    intidx = 0;
    while (idx < hull.length) {
      hull[idx++] = ptr.value();
      ptr = ptr.next();
    }

    return hull;
}
/** 使用共线性检查来确定左拐 */
public static boolean isLeftTurn(IPoint p1, IPoint p2, IPoint p3) {
    return (p2.getX() - p1.getX()) * (p3.getY() - p1.getY()) -
           (p2.getY() - p1.getY()) * (p3.getX() - p1.getX()) > 0;
}

}

/* 排序类。按照和指定点的极角值降序排列 /
class ReversePolarSorter implements Comparator {

/** 存储用于比较的指定点的x、y坐标 */
final double baseX;
final double baseY;

/** ReversePolarSorter将所有点和指定点比较 */
public ReversePolarSorter(IPoint base) {
    this.baseX = base.getX();
    this.baseY = base.getY();
}

public int compare(IPoint one, IPoint two) {
    if (one == two) { return 0; }

    // 确保使用atan2方法来计算极角，
    // 这个办法可行是因为当前点的y值永远大于指定点的y值
    double oneY = one.getY();
    double twoY = two.getY();
    double oneAngle = Math.atan2(oneY - baseY, one.getX() - baseX);
    double twoAngle = Math.atan2(twoY - baseY, two.getX() - baseX);

    if (oneAngle > twoAngle) { return -1;}
    else if (oneAngle < twoAngle) { return +1; }
    
    // 如果角度相同,那么就比较y值,确保凸包算法能够得到正确的值
    if (oneY > twoY) { return -1; }
    else if (oneY < twoY) { return +1; }

    return 0;
}

}
如果整个点集（n > 2）的所有点都在同一条线上，那么在这种特殊情况下，凸包就只是首尾两端的点。在这种情况下计算出来的凸包可能会包含多个共线的连续点，因为算法中并没有逻辑去试图删除这些共线的点。