2
$\begingroup$

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) ?

$\endgroup$
  • $\begingroup$ Are you performing weighted (by area) averages to piece together the centers of mass to find the overall center of mass? If you're doing that, the two-dimensional ideasseem good (but I haven't read closely enough to say for sure). $\endgroup$ – pjs36 May 31 '16 at 6:03
  • $\begingroup$ There is a standard formula of C.M. or C.G. namely $\frac{\sum m_{i} \mathbf{x}_{i}}{\sum m_{i}}$ $\endgroup$ – Ng Chung Tak May 31 '16 at 9:52
  • $\begingroup$ You consistently say 'polyhedron' (which is a 3-dimensionsl solid) but what you show in the images is a 'polygon' (a planar figure)... $\endgroup$ – CiaPan Jun 29 '16 at 13:01
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You do not have to draw $n-3$ diagonals from a single vertex. It's quite obvious with convex polygons, but not so easy with concave ones. There are even polygons which can not be dissected into triangles by a family of diagonals meeting all in a single vertex. Anyway you do not have to try it at all – just make $n$ triangles, each spanning between a single side of a polygon as its base and the coordinate system's origin as an apex. Some of them will overlap, some will also have negative area, but the summation will be much simpler (less cancellations) while leading to the same final result. $\endgroup$ – CiaPan Jun 29 '16 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy