From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Subject: Re: Centroid coordinates
Date: 8 Feb 2001 17:34:00 GMT
Newsgroups: sci.math.num-analysis
Summary: Calculating center of mass of polytopes efficiently

In article <3A7D276F.A68F5CD6@t-online.de>,
Georg Matejko  <Matejko-Witten@t-online.de> wrote:

>Who can give me formulae for centroid coordinates of irregular
>polyhedrons? They should use only the vertices instead of integrals.

Vertex information is not enough; you need the combinatorial information
specifying which sets of vertices are joined to make cells.

The center of mass is indeed computed with integrals, but may be reduced
to simple arithmetic for polyhedra. The x-coordinate, for example, of
the center of mass may be computed by dividing the integral of  x  (over
the solid) by the integral of  1.  Each of these integrals is additive,
that is, we need only partition the solid into tetrahedra (or other
easy cells of our choosing) and add the integrals together. As for
the integral over a single tetrahedron, that's easy too. If the
vertices are  P0, P1, P2, P3  then the linear map
	 (t,u,v) -> P0 + t*(P1 - P0) + u*(P2 - P0) + v*(P3 - P0)
maps the unit simplex { (t,u,v) : t>0, u>0, v>0, t+u+v < 1 }  to the given one,
so the change of variables theorem reduces the integral to that of
a linear function on the unit simplex. (Just _which_ unit function it is
depends on the points  P_i  and on the function such as  x  which you
wish to integrate over the original tetrahedron.) These last integrals
can be computed directly, of course: the integral of  1  over the
unit simplex is  1/6,  and the integrals of  x, y, and  z  are each  1/24.


>I´m especially interested in the formulae for a solid beased on a
>trapezoid with a linear "rising roof". (Soory for my English)

Does this mean the region lying over a trapezoid in R^2 and under a plane
in R^3 ? Without loss of generality we may set coordinates so that the
trapezoid has vertices  (0,0), (1,0), (a,b), (c,d)  in cyclic order,
and so that the plane is  z = e x + f y + g.  I would split the trapezoid
into two triangles and integrate  1, x, y, and  z  over each of the
two resulting solids. For example, the integral of  x  over the
region lying over triangle (0,0)-(a,b)-(c,d)  is  |a d - b c| times Maple's
 int(int(int(t*a+u*c, z=0 .. e*(t*a+u*c)+f*(t*b+u*d)+g),u=0..1-t), t=0..1);   
which evaluates to 
 (f*b*c+f*d*a+2*e*c^2+2*e*a^2+2*f*d*c+2*e*a*c+2*f*b*a+4*g*c+4*g*a)/24
The integral of  x  over the other solid is obtained by replacing (c,d) with
(1,0). Add the two together to get the integral of  x  over the whole box.
Divide by the volume of the box to get the x-coordinate of the centroid.
Repeat for the y- and z- coordinates.

dave


[slightly edited from original --djr]