凸包を求める - jarvisのマーチ

凸包を求めるアルゴリズム、最後にjarvisのマーチという方法をやってみます。
考え方としては、まず最初にy座標が一番小さいものを選んで、その点からの角度が一番小さい点を選んでいきます。

角度は内積で求めます。

このアルゴリズムの場合、凸包上の頂点ごとに点の数の繰り返しを行うので、点の数n、頂点数hとすると、計算量はO(hn)になります。

    static List<Point> points = new ArrayList<Point>();
    static List<Point> hull;
    
    static void createConvexHull(){
        //Y座標で並べ替え
        Collections.sort(points, new Comparator() {
            public int compare(Object o1, Object o2) {
                return ((Point)o1).y - ((Point)o2).y;
            }
        });
        
        //凸包を求める
        hull = new ArrayList<Point>();
        //一番上の点を求める
        Point first = points.get(0);
        hull.add(first);
        int vx = 1;
        int vy = 0;
        Point oldpoint = first;
        for(;;){
            //前回の辺との角度が一番小さい点を求める。
            Point minpoint = null;
            int minvecx = 0;
            int minvecy = 0;
            double maxcos = -1;
            for(Point p : points){
                if(p == oldpoint) continue;
                int ox = p.x - oldpoint.x;
                int oy = p.y - oldpoint.y;
                //角度を求める
                double cos = (ox * vx + oy * vy) / 
                        (Math.sqrt(ox * ox + oy * oy) * Math.sqrt(vx * vx + vy * vy));
                if(cos > maxcos){
                    //いままでの中で一番角度が小さいとき
                    maxcos = cos;
                    minvecx = ox;
                    minvecy = oy;
                    minpoint = p;
                }
            }
            if(minpoint == first){
                //最初の点に戻ったら終わり
                break;
            }
            vx = minvecx;
            vy = minvecy;
            oldpoint = minpoint;
            hull.add(minpoint);
        }
    }