[Math] Center of mass of convex polyhedron.

algorithmsgeometry

Given a set of 2d points we can find it's convex hull.

convex hull

Now I'm going to explain an algorithm I thought of and you guys let me know where I've gone wrong (because it probably is wrong)

So our goal is to calculate the center of mass.

  1. Split up the polyhedron into n-1 quadrilateral, where n is the number of points that are not extremums or the X axis. The quadrilateral should have 2 sides along the Y axis (you should be able to use any 2 perpendicular axis and this should work fine).
    split

  2. Now (unless I'm wrong) it's very easy to calculate the center of mass of each of these quadrilaterals (or triangles) individually.

2.1 The center of mass of a triangle is the middle of the 3 vertices divided by 3.

2.2 Any other quadrilateral will have 4, 2 or 0 right angle, if it's 4 then we can do the sum of the vertices divided by 4, and if it's 2 or 0 we can calculate the center of mass by splitting the shape again.

Let's take a random slab for example

slab

I can split that slab into 2 triangle and a square

slabsplit

and for those 3 shapes it's easy to calculate the center of mass. (and the area for that matter)

Next, and I need confirmation on this, can I use the position of the center of mass and it's volume to calculate the center of mass for the entire slab.

Then, once I have all the centers of mass for all the slabs, can I use the same trick again (because I have the position and the volume) to calculate the center of mass of the entire polytope ?

Assuming this all works, would it also work in 3D ?

extra:
A little improvement that I thought, is there maybe a relationship that would find the center of mass of one of the slab by taking the center of mass of the 2 parallel lines ?

improvement

Because if yes that should also apply when taking the center of mass of 2 parallel convex polyhedra to find the center of mass of the 3d slab ?

edit: In case this actually works, what's the big O complexity of this algorithm ? O(n^2) ?

Best Answer

Your idea seems fine, but it leads to a lot of computation that is not easily automated. The following already leads to a simplification: Partition your domain in $n-2$ triangles by drawing $n-3$ diagonals from a single vertex.

Note that the data defining your convex domain $B$ are the points ${\bf z}_k=(x_k,y_k)$, numbered modulo $n$ in counterclockwise order. The following approach computes the centroid $(\xi,\eta)$ of $B$ in terms of explicit formulas containing only these data. Note that $$\xi={1\over A}\int_Bx\>{\rm d}(x,y),\quad \eta={1\over A}\int_By\>{\rm d}(x,y)\ ,$$ where ${\rm d}(x,y)$ denotes the euclidean area element, and $A:=\int_B{\rm d}(x,y)$ is the area of $B$. In order to compute these area integrals we use Green's theorem $$\int_B(Q_x-P_y){\rm d}(x,y)=\int_{\partial B}(Pdx+Qdy)$$ with suitable fields ${\bf F}=(P,Q)$. For the area we put ${\bf F}=(0,x)$ and obtain $$A=\int_B 1\>{\rm d}(x,y)=\int_{\partial B}x\>dy\ .$$ Now $\partial B$ consists of $n$ directed segments $$\sigma_k:\quad t\mapsto \bigl((1-t)x_{k-1}+t x_k,\ (1-t)y_{k-1}+ty_k\bigr)\qquad(0\leq t\leq 1))\ .$$ One gets $$\int_{\sigma_k}x\>dy=\int_0^1 \bigl((1-t)x_{k-1}+t x_k\bigr)\>(y_k-y_{k-1})\>dt={1\over2}(x_{k-1}+x_k)(y_k-y_{k-1})\ .$$ Summing over $k$ and taking care of some cancellation we obtain $$A={1\over2}\sum_{k=1}^n x_k(y_{k+1}-y_{k-1})$$ (a well known formula). In a similar way we have $$\int_Bx\>{\rm d}(x,y)=\int_{\partial B}{x^2\over2}\>dy,\qquad \int_By\>{\rm d}(x,y)=\int_{\partial B}xy\>dy\ .$$ I leave it to you to set up and compute the corresponding integrals $\int_{\sigma_k}\ldots$ and to obtain nice final formulas.

Related Question