数学-ジオメトリ-離散点外接凸多角形

シェルツールクラス

public class ConvexHull {

    //        Point 
    public static List makeHull(List points) {
        List newPoints = new ArrayList<>(points);
        Collections.sort(newPoints);
        return makeHullPresorted(newPoints);
    }

    //          O(n)
    public static List makeHullPresorted(List points) {
        if (points.size() <= 1)
            return new ArrayList<>(points);

        /*     */
        List upperHull = new ArrayList<>();
        for (Point p : points) {
            while (upperHull.size() >= 2) {
                Point q = upperHull.get(upperHull.size() - 1);
                Point r = upperHull.get(upperHull.size() - 2);
                if ((q.x - r.x) * (p.y - r.y) >= (q.y - r.y) * (p.x - r.x))
                    upperHull.remove(upperHull.size() - 1);
                else
                    break;
            }
            upperHull.add(p);
        }
        //            
        upperHull.remove(upperHull.size() - 1);

        /*     */
        List lowerHull = new ArrayList<>();
        for (int i = points.size() - 1; i >= 0; i--) {
            Point p = points.get(i);
            while (lowerHull.size() >= 2) {
                Point q = lowerHull.get(lowerHull.size() - 1);
                Point r = lowerHull.get(lowerHull.size() - 2);
                if ((q.x - r.x) * (p.y - r.y) >= (q.y - r.y) * (p.x - r.x))
                    lowerHull.remove(lowerHull.size() - 1);
                else
                    break;
            }
            lowerHull.add(p);
        }
        //            
        lowerHull.remove(lowerHull.size() - 1);

        if (!(upperHull.size() == 1 && upperHull.equals(lowerHull)))
            upperHull.addAll(lowerHull);
        return upperHull;
    }
}

ポイントクラス

public class Point implements Comparable {

    public final double x;
    public final double y;

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

    public String toString() {
        return String.format("Point(%g, %g)", x, y);
    }

    public boolean equals(Object obj) {
        if (!(obj instanceof Point))
            return false;
        else {
            Point other = (Point)obj;
            return x == other.x && y == other.y;
        }
    }

    public int hashCode() {
        return Objects.hash(x, y);
    }

    public int compareTo(Point other) {
        if (x != other.x)
            return Double.compare(x, other.x);
        else
            return Double.compare(y, other.y);
    }
}

Convex hull algorithm
ディスクリートポイント最小(凸)境界検索
C#地図離散点外接凸多角形を探す
度度度熊保護村(凸包、floyd最小環)