《算法技术手册》一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]开始    Double edList<IPoint> list = new Double edList<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  X;final double  Y;/** ReversePolarSorter将所有点和指定点比较 */public ReversePolarSorter(IPoint  ) {    this. X =  .getX();    this. Y =  .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 -  Y, one.getX() -  X);    double twoAngle = Math.atan2(twoY -  Y, two.getX() -  X);    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）的所有点都在同一条线上，那么在这种特殊情况下，凸包就只是首尾两端的点。在这种情况下计算出来的凸包可能会包含多个共线的连续点，因为算法中并没有逻辑去试图删除这些共线的点。