3d hull should allow coplanar points

[simonlindholm]

https://codeforces.com/blog/entry/73366 links to https://github.com/Laakeri/contestlib/blob/master/src/geometry/3dconvexhull.cpp which seems like a good implementation. Need to test/minify it.

[Chillee]

That implementation does add an extra log n factor though. Could be worth it to replace it regardless, depending on benchmark results.

[simonlindholm]

golfed a bit:

bool sameHalf(P3 a, P3 b, P3 p1, P3 p2, P3 p3) {
	P3 hlp = (p2-p1).cross(p3-p1);
	return (hlp.dot(a-p1))*(hlp.dot(b-p1))>=0;
}

vector<tuple<int, int, int>> hull3d_2(vector<P3>& ps) {
	map<tuple<int, int, int>, int> hull;
	hull[{0,1,2}]=3;
	hull[{0,1,3}]=2;
	hull[{0,2,3}]=1;
	hull[{1,2,3}]=0;
	rep(i,4,sz(ps)) {
		vector<array<int, 4>> ch;
		for (auto [tri, q] : hull) if (auto [a,b,c] = tri;
				!sameHalf(ps[i], ps[q], ps[a], ps[b], ps[c])) {
			ch.push_back({a,b,i,c});
			ch.push_back({a,c,i,b});
			ch.push_back({b,c,i,a});
			ch.push_back({a,b,c,i});
		}
		for (auto [a,b,c,q] : ch) {
			auto [it,r] = hull.emplace(make_tuple(a,b,c), q);
			if (!r) hull.erase(it);
		}
	}
	vector<tuple<int, int, int>> ret;
	for (auto [tri, q] : hull) {
		auto [a,b,c] = tri;
		if ((ps[q] - ps[a]).dot((ps[b] - ps[a]).cross(ps[c] - ps[a])) > 0)
			swap(a, b);
		ret.emplace_back(a, b, c);
	}
	return ret;
}

Should be possible to get rid of the log factor by the same method as the current 3d hull implementation -- keeping an O(n^2)-sized map from edges to faces -- though it would add some code.

I wonder how much more code O(n log n) randomized 3d hull would be, it doesn't sound too bad from http://www.inf.fu-berlin.de/lehre/SS13/AG/randinc3d.pdf...

[simonlindholm]

http://www.inf.fu-berlin.de/lehre/SS13/AG/randinc3d.pdf

I tried to code this, and it ended up at ~70 lines (buggy wip implementation)

https://github.com/bqi343/USACO/blob/master/Implementations/content/geometry%20(13)/3D/Hull3D.h looks much better. Would be interesting to benchmark Delaunay triangulation based on that implementation, including with concyclic points.