凸包を求める - 改良版

前回のアルゴリズムでは、点の数分のループが４重になっていたので、計算時間がO(n^4)になってしまいます。
ということで、別のアルゴリズム。

ここでは、上側の凸包と下側の凸包をわけて取得します。上側の凸包をとるには、点をX座標でソートしておいて、連続する３点が時計回りの三角形になるように点を取っていきます。

時計回りの逆になっていた場合には、上側の凸包にはなりません。

そうすることで、計算量はソートの計算量O(n log n)に支配されるようになります。
ということで、ソース。
前回のソースで凸包を得る部分をcreateConvexHullメソッドとして抜き出しておきました。その部分だけを変更します。

    static List<Point> points = new ArrayList<Point>();
    static List<Point> hull;
    
    static void createConvexHull(){
        //X座標で並べ替え
        Collections.sort(points, new Comparator() {
            public int compare(Object o1, Object o2) {
                return ((Point)o1).x - ((Point)o2).x;
            }
        });
        
        //凸包を求める
        hull = new ArrayList<Point>();
        List<Point> proc = hull;
        for(int k = 0; k < 2; ++k){
            //1回目で上側、2回目で下側の凸包を得る
            proc.add(points.get(0));
            proc.add(points.get(1));
            for(int i = 2; i < points.size(); ++i){
                Point p = points.get(i);
                for(;;){
                    Point q1 = proc.get(proc.size() - 2);
                    Point q2 = proc.get(proc.size() - 1);
                    int s = getSignedArea(q1, q2, p);
                    if(k == 0){
                        if(s < 0) break;
                    }else{
                        if(s > 0) break;
                    }
                    proc.remove(proc.size() - 1);
                    if(proc.size() < 2) break;
                }
                proc.add(p);
            }
            if(k == 0) proc = new ArrayList<Point>();
        }

        //あわせる
        for(int i = 0; i < proc.size(); ++i){
            hull.add(proc.get(proc.size() - i - 1));
        }
    }

参考文献

計算幾何―理論の基礎から実装まで (アルゴリズム・サイエンスシリーズ―数理技法編)