[数据结构与算法]凸包算法leetcode.587

// Jarvis算法
//如果最外层的点都按某个方向面朝下一个外点,形成逆时针的圆,
    //那么对于某个外点及其面向的点所连的线,所有点都在线上或者左侧
    public int[][] Jarvis(int[][] points){
        int n=points.length;
        if(n<=3)
            return points;
        List<int[]> list=new ArrayList<>();//存储外点
        boolean[] mark=new boolean[n];//标记已经添加的点
        int begin=0;//以最左边的点作为开始,一定为外点
        for (int i = 0; i < n; i++) {
            if(points[i][0]<points[begin][0])
                begin=i;
        }
        int p=begin;//每次寻找的基点
        while (true){
            int q=(p+1)%n;//从p下一个点开始,记录最右边的点
            //寻找相对pq最右边的点r
            for (int r = 0; r <n ; r++) {
                //只要叉乘<0,说明r在pq右边
                if(cross(points[p],points[q],points[r])<0)
                    q=r;
            }
           //寻找pq线上的点
            for (int i = 0; i < n; i++) {
                if(mark[i]||i==p||i==q)
                    continue;
                if(cross(points[p],points[q],points[i])==0){
                    list.add(points[i]);
                    mark[i]=true;
                }
            }
            //q可能已经被某条线上其他点标记
            if(!mark[q]){
                list.add(points[q]);
                mark[q]=true;
            }
            if(q==begin)//回到起点
                break;
            p=q;
        }
        return list.toArray(new int[][]{});
    }
    //叉乘pq*pr
    public int cross(int[] p, int[] q, int[] r) {
        return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0]);
    }

阅读世界，共赴山海

423全民读书节，邀你共读