I want to find the convex hull of a set of $n$ three-dimensional spheres. The spheres can have different sizes and can overlap. What algorithm do you suggest for finding the convex hull? In the simplest case, I only have three spheres. Accordingly, I value
- simplicity over efficiency.
- the possibility of representing the resulting "enclosed volume" analytically (preferable but not essential).
I am a novice to convex hull algorithms and all suggestions are highly appreciated. I suspect that a marching cubes algorithm would satisfy my criteria. Do you agree? If so, what marching cube algorithm do you suggest?
This is an uneasy problem. A possible solution can be based on a primitive geometric operation: find the planes of contact of three spheres.
Using this operation
try every triple of spheres; there are $\dfrac{n(n-1)(n-2)}6$ of them;
check it the plane contains a flat face of the hull: all spheres must be on the same side of it;
from the hull triples, generate all distinct pairs and all singletons, respectively corresponding to edges and vertices. And edge corresponds to a conic patch (tangent to two spheres) and a vertex to a spherical patch.
Unfortunately, this is an $O(n^4)$ process.
The computation of the volume is an endeavor. You can dissect the hull using flat polygons internally so that it is split in a convex polyhedron, one conical "segment" per edge and one spherical "tetrahedron" per vertex.
An approximate solution is more accessible:
Generate points on the surfaces of the sphere using some uniform distribution.
Find the hull of all points, using a standard 3D points algorithm.