凸包(Andrew's monotone chain convex hull algorithm)

目的

$n$個のxy平面上の点について、凸包をAndrew's monotone chain convex hull algorithmに従って$O(n\log{n})$で求めます。

計算量

$O(n\log n)$

使い方

int[] convexHull(double[] x,double[] y)
$n$個の点$(x[i],y[i])$に対して、凸包上の点の番号を反時計周りに並べた配列をreturnします。

ソースコード

int[] convexHull(final double[] x, final double[] y) {
    int n = x.length;
    Integer[] ord = new Integer[n];
    for (int i = 0; i < n; ++i) {
	ord[i] = i;
    }
    Arrays.sort(ord, new Comparator<Integer>() {
	    @Override
		public int compare(Integer o1, Integer o2) {
		if (x[o1] != x[o2]) {
		    return Double.compare(x[o1], x[o2]);
		} else  {
		    return Double.compare(y[o1], y[o2]);
		}
	    }
	});

    int[] ret = new int[n + 1];
    int p = 0;
    for (int i = 0; i < n; ++i) {
	if (p >= 1 && x[ord[i]] == x[ret[p - 1]] && y[ord[i]] == y[ret[p - 1]])
	    continue;
	while (p >= 2 && Line2D.relativeCCW(x[ret[p - 2]], y[ret[p - 2]], x[ret[p - 1]], y[ret[p - 1]], x[ord[i]],
					    y[ord[i]]) >= 0)
	    p--;
	ret[p++] = ord[i];
    }

    int inf = p + 1;
    for (int i = n - 2; i >= 0; --i) {
	if (x[ret[p - 1]] == x[ord[i]] && y[ret[p - 1]] == y[ord[i]])
	    continue;
	while (p >= inf && Line2D.relativeCCW(x[ret[p - 2]], y[ret[p - 2]], x[ret[p - 1]], y[ret[p - 1]], x[ord[i]],
					      y[ord[i]]) >= 0)
	    p--;
	ret[p++] = ord[i];
    }
    return Arrays.copyOf(ret, p - 1);
}

Verified

yukicoder No.199 星を描こう