概念

凸包(Convex Hull)是一個(gè)計(jì)算幾何（圖形學(xué)）中的概念。用不嚴(yán)謹(jǐn)?shù)脑拋碇v，給定二維平面上的點(diǎn)集，凸包就是將最外層的點(diǎn)連接起來構(gòu)成的凸多邊型，它能包含點(diǎn)集中所有點(diǎn)的。

問題

給定平面的點(diǎn)集，求出凸包的所有頂點(diǎn)。

算法思路

Grahanm's Scan算法的主要思路如下：
1，選擇P中y坐標(biāo)最小的點(diǎn)為起始點(diǎn)p0，若有多個(gè)這樣的點(diǎn)則進(jìn)一步選取其中x坐標(biāo)最小的點(diǎn)為p0;

2，設(shè)<p1,p2,……,pm>是P中剩余的點(diǎn)，對(duì)其按逆時(shí)針方向相對(duì)p0的極角進(jìn)行從小到大排序，若有多個(gè)點(diǎn)有相同的極角，則離p0點(diǎn)近的排在前面；

3，設(shè)排序后的點(diǎn)的順序?yàn)?strong>p1,p2,……,pm，分別計(jì)算向量p0p1與p1p2的叉積，二維矢量的叉積a × b = IaI?IbIsinθ，θ為從a到b的夾角，如果b在a的逆時(shí)針方向，則sinθ為正，叉積也就為正，在我們逆時(shí)針遍歷的情況下，如果b在a的順時(shí)針方向，則p1點(diǎn)必定不是凸包上的點(diǎn)，反之則是在凸包上的點(diǎn)。所以我們使用棧來保存凸包上的點(diǎn)，遍歷過程中發(fā)現(xiàn)棧頂?shù)狞c(diǎn)不是凸包上的點(diǎn)就pop出來，如果是就繼續(xù)把接下來的點(diǎn)放入棧中。

圖片可能更容易理解，這里就放幾張別人博客的圖片：

Grahanm's Scan

JAVA實(shí)現(xiàn)

import java.util.*;

public class Main {

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }

    // 用于存儲(chǔ)起始點(diǎn)
    public static Point centerPoint;

    // 叉積
    public static int CJ(int x1, int y1, int x2, int y2){
        return x1*y2 - x2*y1;
    }

    // 計(jì)算向量(p1->p2)和(p2->p3)兩個(gè)向量的叉積
    public static int compare(Point p1, Point p2, Point p3){
        return CJ(p2.x-p1.x, p2.y - p1.y, p3.x-p2.x, p3.y-p2.y);
    }

    public static void main(String arg[]){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<Point> points = new ArrayList<>();
        for (int i=0; i<n; i++){
            int x = in.nextInt();
            int y = in.nextInt();
            Point point = new Point(x, y);
            // 找到x,y都最小的點(diǎn)作為起始點(diǎn)
            if (centerPoint == null || centerPoint.y>point.y || (centerPoint.y==point.y && centerPoint.x>point.x)){
                centerPoint = point;
            }
            points.add(point);
        }
        // 把起始點(diǎn)拿出去
        points.remove(centerPoint);

        // 按照與起始點(diǎn)向量的極角排序
        Collections.sort(points, (p1, p2) -> {
            if (Math.atan2(p1.y- centerPoint.y, p1.x- centerPoint.x) != Math.atan2(p2.y- centerPoint.y, p2.x- centerPoint.x)){
                // atan2可以計(jì)算極角
                return Math.atan2(p1.y- centerPoint.y, p1.x- centerPoint.x) < Math.atan2(p2.y- centerPoint.y, p2.x- centerPoint.x)? -1 : 1;
            }
            // 極角相同與中心點(diǎn)距離越近，則x坐標(biāo)也就越近
            return Math.abs(p1.x- centerPoint.x) - Math.abs(p2.x- centerPoint.x);
        });

        // 用數(shù)組模擬棧
        Point[] stack = new Point[n];
        stack[0] = centerPoint;
        // 棧頂指針
        int top = 0;

        // 遍歷點(diǎn)集中每一個(gè)點(diǎn)
        for (int i=0; i<points.size();){
            //如果棧中元素大于等于2并且(p2->p3)在(p1->p2)的順時(shí)針方向，棧頂?shù)狞c(diǎn)拋出
            while (top>=1&&compare(stack[top-1], stack[top], points.get(i)) < 0) top--;
            // 找到在逆時(shí)針方向的點(diǎn)了，將p2放入棧頂
            stack[++top] = points.get(i++);
        }

        // 輸出棧中的所有點(diǎn)就是凸包上的點(diǎn)
        for (int i=0; i<=top; i++){
            System.out.println(stack[i]);
        }
    }
}

參考

算法作業(yè)-凸包問題-Graham方法
凸包：Graham's Scan