Calculation of centroid & volume of a polyhedron when the vertices are given

Question

Given the location of vertices of a convex polyhedron (3D), I need to calculate the centroid and volume of the polyhedron. Following code is available at Mathworks site.

function C = centroid(P)
k=convhulln(P);
if length(unique(k(:)))<size(P,1)
    error('Polyhedron is not convex.');
end
T = delaunayn(P);
n = size(T,1);
W = zeros(n,1);
C=0;
for m = 1:n
    sp = P(T(m,:),:);
    [null,W(m)]=convhulln(sp);
    C = C + W(m) * mean(sp);
end
C=C./sum(W);
return
end

The code is elegant but is terribly slow. I need to calculate the volume and centroid of thousands of polyhedrons hundreds of times. Using this code in its current state is not feasible. Does anyone know a better approach or can this code be made faster? There are some minor changes I can think of such as, replacing mean with expression for mean.

Answer 1

There is a much simpler approach to calculate the volume with minimal effort. The first flavour uses 3 local topological information sets of the polyhedron, the tangent unit vector of the edges, the unit vectors of the in-plane normal on this tangent and the unit vector of the facet itself (which are very simple to extract from the vertices). Please refer to Volume of a Polyhedron for further details.

The second flavour uses the face areas, the normal vectors and the face barycenters to calculate the polyhedron volume according to this Wikipedia Article. Both algorithms are rather simple and very easy to implement and through the simple summing structure easy to vectorize too. I suppose that both approaches will be much faster than doing a fully fledged tesselation of the polyhedron.

The centroid of the polyhedron can then be calculated by applying the divergence theorem transferring the integration over the full polyhedron volume into an integration over the polyhedron surface. A detailed description can be found in Calculating the volume and centroid of a polyhedron in 3d. I did not check if the tesselation of the polyhedron into triangles is really necessary or one could work with the more complex polygon surfaces of the polyhedron too, but in any case the area tessellation of the faces is much simpler than the volume tesselation. In total such a combined approach should be much faster than the volume approach.