05 - 点集的最小凸包 - Graham扫描算法

1. 算法思路：

1. 选定y坐标最小（y坐标相同时取x最小）的点作为极点，这个点必在凸包上；

2. 将其余点按极角排序，在极角相同的情况下比较与极点的距离，离极点比较近的优先；

3. 用一个栈 pointStack 存储凸包上的点，先将按极角和极点排序最小的两个点入栈；

4. 按序扫描每个点，检查栈顶的两个元素与这个点构成的折线段是否“拐”向右侧；
（ ! isLeftTurn(nextToTop, top, pi) 即 (crossProduct(nextToTop, top, pi) <= 0) ）

5. 如果满足，则弹出栈顶元素，并返回第 4. 步再次检查，直至不满足。将该点入栈，并对其余点不断执行此操作；

6. 最终栈中元素为凸包的顶点序列。

时间复杂度 ：$O(nlogn)$
主要花在点集的排序上面，快排平均 $O(nlogn)$

2. 示例代码：

2.1 极角比较器

使用叉积比较两个点的极角

static class PointComparator implements Comparator<Point> {
        
        private Point p0;
        
        public PointComparator(Point p0) {
            this.p0 = p0;
        }

        // 依据两点相对于 p0 的极角，比较两个点；
        // 如果角度相同，则依据到点 p0 的距离
        @Override
        public int compare(Point p1, Point p2) {
            
            double crossProduct = crossProduct(p0, p1, p2);
            
            if (crossProduct > 0) return -1;
            if (crossProduct < 0) return 1;

            // cross_product = 0 => 向量是共线的，距离 p0 更远的顶点应被视为“更大”
            double d1 = p0.dist(p1);
            double d2 = p0.dist(p2);
            
            if (d1 < d2) return -1;
            if (d1 > d2) return 1;
            
            return 0;
        }
    }

• crossProduct(p0, p1, p2) > 0 : $P_0P_1 \times P_0P_2 > 0 \Rightarrow P_1 < P_2$
  

• crossProduct(p0, p1, p2) < 0 : $P_0P_1 \times P_0P_2 < 0 \Rightarrow P_1 > P_2$
  

• crossProduct(p0, p1, p2) == 0 : $P_0$，$P_1$，$P_2$ 三点共线

  • $|P_0P_1| < |P_0P_2| \Rightarrow P_1 < P_2$
    
  • $|P_0P_1| > |P_0P_2| \Rightarrow P_1 > P_2$
    

2.2 Graham扫描算法

public static Polygon Graham(ArrayList<Point> pointsList) {

    // 拷贝点表，以便在算法期间更改。
    // 假设 pointsList.size >= 3。
    ArrayList<Point> points = (ArrayList<Point>)pointsList.clone();
    Stack<Point> pointStack = new Stack<Point>();
    
    // 获取最左的最低点 - 作为凸包的第一个顶点 - O(n)
    Point p0 = getLowestPoint(points);
    pointStack.push(p0);
    points.remove(p0);
    
    // 按其极角对其余点进行排序 - O(n*log(n))
    Collections.sort(points, new PointComparator(p0));
    
    // 开始Graham扫描之前，向 stack 中再添加两个点
    Iterator<Point> iter = points.iterator();
    
    Point p1 = iter.next();
    pointStack.push(p1);
    
    Point p2 = iter.next();
    pointStack.push(p2);
    
    // 遍历排序后的点表，确定哪些点应加入到凸包 - O(n)
    while (iter.hasNext()) {
        Point pi = iter.next();
        Point top = pointStack.elementAt(pointStack.size() - 1);
        Point nextToTop = pointStack.elementAt(pointStack.size() - 2);
        
        while (! isLeftTurn(nextToTop, top, pi)) {
            pointStack.pop();
            
            // 更新 "top" 顶点
            top = nextToTop;
            nextToTop = pointStack.elementAt(pointStack.size() - 2);
        }
        
        pointStack.push(pi);
    }

    // 凸包已构建，现在按逆时针顺序 (CCW) 返回其顶点列表
    ArrayList<Point> polygon = new ArrayList<Point>();
    while(! pointStack.empty()) {
        polygon.add(pointStack.pop());
    }
    Collections.reverse(polygon);
    
    return new Polygon(polygon);
}

1. 找最低点 $P_0$，进行排序
   

2. 具体步骤

points	pointStack
$P_0$，$P_1$，$P_2$，$P_3$，$P_4$，$P_5$，$P_6$，$P_7$，$P_8$，$P_9$
$P_1$，$P_2$，$P_3$，$P_4$，$P_5$，$P_6$，$P_7$，$P_8$，$P_9$	$P_0$
$P_3$，$P_4$，$P_5$，$P_6$，$P_7$，$P_8$，$P_9$	$P_0$，$P_1$，$P_2$
$P_4$，$P_5$，$P_6$，$P_7$，$P_8$，$P_9$	$P_0$，$P_1$，$P_2$，$P_3$	$P_1P_2$ 到 $P_1P_3$ 左转，$P_3$ 压入
$P_5$，$P_6$，$P_7$，$P_8$，$P_9$	$P_0$，$P_1$，$P_2$，$P_3$，$P_4$	$P_2P_3$ 到 $P_2P_4$ 左转，$P_4$ 压入
$P_5$，$P_6$，$P_7$，$P_8$，$P_9$	$P_0$，$P_1$，$P_2$，$P_3$ ( $P_4$ )	$P_3P_4$ 到 $P_3P_5$ 右转，$P_4$ 弹出
$P_5$，$P_6$，$P_7$，$P_8$，$P_9$	$P_0$，$P_1$，$P_2$ ( $P_3$ )	$P_2P_3$ 到 $P_2P_5$ 右转，$P_3$ 弹出
$P_6$，$P_7$，$P_8$，$P_9$	$P_0$，$P_1$，$P_2$，$P_5$	$P_1P_2$ 到 $P_1P_5$ 左转，$P_5$ 压入
$P_7$，$P_8$，$P_9$	$P_0$，$P_1$，$P_2$，$P_5$，$P_6$	$P_2P_5$ 到 $P_2P_6$ 左转，$P_6$ 压入
$P_8$，$P_9$	$P_0$，$P_1$，$P_2$，$P_5$，$P_6$，$P_7$	$P_5P_6$ 到 $P_5P_7$ 左转，$P_7$ 压入
$P_8$，$P_9$	$P_0$，$P_1$，$P_2$，$P_5$，$P_6$ ( $P_7$ )	$P_6P_7$ 到 $P_6P_8$ 右转，$P_7$ 弹出
$P_9$	$P_0$，$P_1$，$P_2$，$P_5$，$P_6$，$P_8$	$P_5P_6$ 到 $P_5P_8$ 左转，$P_8$ 压入
	$P_0$，$P_1$，$P_2$，$P_5$，$P_6$，$P_8$，$P_9$	$P_6P_8$ 到 $P_6P_9$ 左转，$P_9$ 压入

2.3 其他方法

2.3.1 叉积

// 计算叉积
private static double crossProduct(Point p0, Point p1, Point p2) {
    return (p1.getX() - p0.getX()) * (p2.getY() - p0.getY()) -
            (p2.getX() - p0.getX()) * (p1.getY() - p0.getY());
}

// 计算 p0p1 和 p0p2 的相对位置
private static boolean isLeftTurn(Point p0, Point p1, Point p2) {
    return (crossProduct(p0, p1, p2) > 0);
}

$P_0P_1 \times P_0P_2$

2.3.2 获得最低点

• 比较规则：
  • 先比较Y坐标
  • Y坐标相同时再比较X坐标

lowest-then-leftmost point（LTL）

private static Point getLowestPoint(ArrayList<Point> points) {
    Point result = points.get(0);

    // 候选点
    Point candidate;

    for (int i = 1; i < points.size(); i++) {
        candidate = points.get(i);
        
        if (candidate.getY() < result.getY() ||
                candidate.getY() == result.getY() && candidate.getX() < result.getX()) {
            result = candidate;
        }
    }
    
    return result;
}