Algorithm to find center of mass. 
Author Message
 Algorithm to find center of mass.

I am writing an "Asteroids" clone game.

When generating the asteroid I have values for the polygon vertices
coordinates relative to each other. What I need is to find the coordinate
of the center of mass so that I can rotate the vertices around this point.

At the moment I just draw it on paper and take a guess as to the center.
When rotating, this can generate a "lop sided" effect which is not nice.

Can anyone detail an algorithm that could calculate this point?

The game is 2D so one can assume that the asteroid is a flat plate of
uniform density.

I vaguely remember center of mass calculations from my Physics days but
it's all a loss to me now :)

Thanks in advance for any help.

Keith



Mon, 19 May 1997 22:47:21 GMT  
 Algorithm to find center of mass.

If I remember correctly that you can do the following:

Each corner i of the polygon is determined by a set of coordinates (x(i), y(i)).

To this pair of reals there is associated a vector. Now, we set the origin
of the vector space to be the corner 1, so that a corner i has associated to
it the vector v (i) := (x(i) - x(1), y(i) - y(1)) (the relative coordinates you
mention).

Add up these vectors, divide the sum by the number of corners, and you should
end up with the coordinates of the center of gravity, relative to corner 1.

    v(c) :=  (sum ((1..n), x(i) - x(1))/n, sum ((1..n), y(i) - y(1))/n)

(c being the center, n being the number of corners)

This works of course for every thinkable origin of the vector space, but
you wanted relative coordinates.

Best regards,   Roland



Tue, 20 May 1997 16:44:02 GMT  
 Algorithm to find center of mass.

[re the question: "How do you find the centre of mass of a polygon cut
from a flat plate of uniform density?"]

Quote:
> If I remember correctly that you can do the following:

> Each corner i of the polygon is determined by a set of coordinates (x(i), y(i)).

> To this pair of reals there is associated a vector. Now, we set the origin
> of the vector space to be the corner 1, so that a corner i has associated to
> it the vector v (i) := (x(i) - x(1), y(i) - y(1)) (the relative coordinates you
> mention).

> Add up these vectors, divide the sum by the number of corners, and you should
> end up with the coordinates of the center of gravity, relative to corner 1.

>     v(c) :=  (sum ((1..n), x(i) - x(1))/n, sum ((1..n), y(i) - y(1))/n)

> (c being the center, n being the number of corners)

> This works of course for every thinkable origin of the vector space, but
> you wanted relative coordinates.

This can't be right, can it? If we start with the unit square and then
add an extra vertex (x, -x) where x is very small, it is clear the CG
is still very close to (0.5, 0.5), whereas by your argument it's now
very close to (0.4, 0.4). I think you've found the CG of a set of unit
masses at the vertices of the polygon, not that of the polygon itself.

The only thing I can suggest for the original problem is to cut the
polygon into triangles, find the CG and mass of each (fairly easy) and
then use a weighted version of Roland Schmitt-Hartmann's method to
combine these into an overall CG. This sound horribly inefficient,
though.


<a href="http://www.maths.qmw.ac.uk/~tdb/homepage.html">WWW homepage</a>



Tue, 20 May 1997 18:17:45 GMT  
 Algorithm to find center of mass.

Quote:

> [re the question: "How do you find the centre of mass of a polygon cut
> from a flat plate of uniform density?"]

[...]

> This can't be right, can it? If we start with the unit square and then
> add an extra vertex (x, -x) where x is very small, it is clear the CG
> is still very close to (0.5, 0.5), whereas by your argument it's now
> very close to (0.4, 0.4). I think you've found the CG of a set of unit
> masses at the vertices of the polygon, not that of the polygon itself.

True. Sorry about the mistake - I didn't remember correctly...

Roland



Tue, 20 May 1997 18:55:45 GMT  
 Algorithm to find center of mass.

Quote:
> I am writing an "Asteroids" clone game.
> When generating the asteroid I have values for the polygon vertices
> coordinates relative to each other. What I need is to find the coordinate
> of the center of mass so that I can rotate the vertices around this point.

 From my calculus days, I seem to remember something that might do the
 trick:

1) Assume that the asteroid can be modeled by a function, such as
        f(x) = 2.3 * x (1.0 < x < 10.0)
        f(x) = 9.0 * x (10.0 < x < 12.0)
        etc ...

2) Integrate f(x) * x

3) Divide the result by the length of the asteroid along the x_axis.

4) This gives the center of mass along the x-axis.  Repeat the procedure
        for the y_axis, but use f(y) instead.

Hope this helps.

--
Joe Nardelli



Tue, 20 May 1997 21:09:19 GMT  
 Algorithm to find center of mass.

I prefer to call it the centroid, because a polygon has a centroid,
while it does not have a center of mass.

I guess some algorithm suggestions have been given, I don't know
how correct any of them are, but I kknow of one that I have used.

The calculation computes two values, namely the x and y coordinates of
the centroid. The two are unrelated, but the calculations are identical.
I will give the algorithm for finding the x coordinate of the centroid.

The x-coord of the centroid is given by the first moment of the figure
about the y-axis divided by the area of the figure. The easiest way that
I know of to calculate the area of the figure is to divide it into
trapezoids. If the figure is a simple polygon, this is very easy.

Presumably the polygon is stored as some kind of ordered list of vertices,
where the edges go from one vertex in the list to the next. For simplicity,
consider that the entire figure lies in the first quadrant. The are
of the trapezoid between an edge (x1,y1)->(x2,y2) and the x-axis is given
by the formula
        a1 = (x2-x1)*((y1+y2)/2);

The moment of the same trapezoid about the y-axis is given by the formula
which is a little ugly because I just made it up:

        m1_y = (x1+(x2-x1)/2))(x2-x1)y2  + ((y1-y2)(x2-x1)/2)(x1 +(x2-x1)/3));

Now if you look at these equations you will see that the (x2-x1) terms will be
either greater than or less than zero  and this will determine the sign of the
trapezoids contribution to the area or moment. I can't draw a picture here,
unfortunately. To find the area of the polygon, just traverse all of the edges
and add up the areas given by the first formaul above. To find the
moment about the y axis, do the same with the second formula. now divide
the moment by the area and you have the x coordinate of the centroid.

my only disclaimer is that i do not specialize in efficiency, or
typing. as far as geometry goes, i can usually be counted on for either
a correct answer or an "i dunno"

good luck,
jlp



Wed, 21 May 1997 00:49:26 GMT  
 Algorithm to find center of mass.

: I am writing an "Asteroids" clone game.

: When generating the asteroid I have values for the polygon vertices
: coordinates relative to each other. What I need is to find the coordinate
: of the center of mass so that I can rotate the vertices around this point.

: Can anyone detail an algorithm that could calculate this point?

: The game is 2D so one can assume that the asteroid is a flat plate of

        - Split it to triangles;
        - Calculate the center of mass for each triangle;
        - Calculate the center of mass for the whole thing using
          the triangles' centers and their weights.

Each of these three steps is easy.
----------------------------------------------------------------------------
IMHO. Igor Chudov,      Resource Solutions Intl         office (918)588-2309
Systems Engineer,       for WilTel.                     home   (918)585-5862

                                          http://m-net.arbornet.org/~ichudov
                                     1819 South Jackson #32-P Tulsa OK 74107

                 f u cn rd ths, u cn gt a gd jb n cmptr prgrmmng.



Wed, 21 May 1997 05:35:35 GMT  
 Algorithm to find center of mass.


Quote:
>When generating the asteroid I have values for the polygon vertices
>coordinates relative to each other. What I need is to find the coordinate
>of the center of mass so that I can rotate the vertices around this point.

Hmm... this is hardly comp.lang.c material, but before more incorrect
followups come in...

Suppose you have n fragments, with masses m[1], m[2], ... m[n],
at positions (x[1], y[1], z[1]), ...

The x - coodinate of the centre of mass is:

x = (x[1]*m[1] + x[2]*m[2] + ... + x[n]*m[n])/(m[1] + m[2] + ... + m[n])

Same goes for the y and z coordinates.
--

The joy of engineering is to find a straight line on a double
logarithmic diagram.



Wed, 21 May 1997 03:41:55 GMT  
 Algorithm to find center of mass.

Quote:

> When generating the asteroid I have values for the polygon vertices
> coordinates relative to each other. What I need is to find the coordinate
> of the center of mass so that I can rotate the vertices around this point.
> Can anyone detail an algorithm that could calculate this point?
> The game is 2D so one can assume that the asteroid is a flat plate of
> uniform density.

Given a flat plate P, with area A, then its mass center is given by
m_x= integral of x over P (area integral);
m_y= integral of y over P (area integral).

For a flat plate bounded by a polygon, I don't think you need to do
double integrals. For example, the mass center of triangle is given by
m_x = 2*(x1+x2+x3)/3; m_y = 2*(y1+y2+y3)/3.
And given two polygons, with their areas (i.e., masses) and mass centers
known, the combined mass center is given by
m_x = (m_x1*area1+m_x2*area2)/(area1+area2);
m_y = (m_y2*area2+m_y2*area2)/(area1+area2).

This is essentially sufficient to find the mass center of any polygons.

Huayong



Thu, 22 May 1997 00:09:39 GMT  
 Algorithm to find center of mass.

:  From my calculus days, I seem to remember something that might do the
:  trick:

: 1) Assume that the asteroid can be modeled by a function, such as
:       f(x) = 2.3 * x (1.0 < x < 10.0)
:       f(x) = 9.0 * x (10.0 < x < 12.0)
:       etc ...

: 2) Integrate f(x) * x

: 3) Divide the result by the length of the asteroid along the x_axis.

: 4) This gives the center of mass along the x-axis.  Repeat the procedure
:       for the y_axis, but use f(y) instead.

       m
        T
  r = ----

       A

  x m = (x rf(x))dx
   b b

       b             b
      ___           ___
      \             \            
       >   x m       >   x m     INT(x rf(x),x,a,b)     INT(x rf(x),x,a,b)
      /__   i i     /__   i i    
      i=a           i=a
 x = ----------- = ----------- = ------------------- = -------------------- =
       b
      ___
      \                 m               m                       A r
       >   m             T            T                    
      /__   i
      i=a

     INT(x f(x),x,a,b)
    -------------------
             A

 A, being the total area, r = areadensity f(x) the function that describes
 the asteriod, and x {a,b}.... *sigh* I have to learn to do this more elegantly
 But, hey, isn't this right? this aplies ofcourse for y and z... not exactly
 alike, but same principle.
                            -1
 for y.. it is... y m = (y f  (y))dy
                   d d

             -1
      INT(y f  (y),y,c,d)
 y = ---------------------
               A

 hmh, I think that's what I mean :).. not sure though, never be sure :)



Thu, 22 May 1997 21:47:25 GMT  
 Algorithm to find center of mass.



|>
|> >When generating the asteroid I have values for the polygon vertices
|> >coordinates relative to each other. What I need is to find the coordinate
|> >of the center of mass so that I can rotate the vertices around this point.
|>
|> Hmm... this is hardly comp.lang.c material, but before more incorrect
|> followups come in...
|>
|> Suppose you have n fragments, with masses m[1], m[2], ... m[n],
|> at positions (x[1], y[1], z[1]), ...
|>
|> The x - coodinate of the centre of mass is:
|>
|> x = (x[1]*m[1] + x[2]*m[2] + ... + x[n]*m[n])/(m[1] + m[2] + ... + m[n])
|>
|> Same goes for the y and z coordinates.
|> --

|> The joy of engineering is to find a straight line on a double
|> logarithmic diagram.

True, but you would have to do this for a very large number of points,
and you have to use points that are inside the polygon, which is a mildly
cumbersome task.

--
Joe Nardelli



Fri, 23 May 1997 20:53:14 GMT  
 Algorithm to find center of mass.

Quote:

> When generating the asteroid I have values for the polygon vertices
> coordinates relative to each other. What I need is to find the coordinate
> of the center of mass so that I can rotate the vertices around this point.
> Can anyone detail an algorithm that could calculate this point?

Did I miss any posts of the line integral method? Although the posted
methods are OK they're based on surface integrals e.g. mass=integral(1 dxdy)
But the likely method of presenting an asteroid in this setting makes
it useful to use Green's theorem:
         _                   _
       _/  P dx + Q dy  =  _/   (dQ/dx - dP/dy) dxdy

so we can get the surface integrals of  1,  x,  and  y  respectively by
integrating  x,  x^2/2,  and  xy  w.r.t. y along the curve describing the
exterior of the asteroid.

You'll need to know that the curve joining two points (x0 y0) and (x1, y1)
has a parameterization   (x,y) = ( (1-t) x0 + t x1,  (1-t) y0 + t y1 )
so that  dy = (y1 - y0) dt. Thus, the integral of   x dy along this
curve is  integral_[0,1]  ( (1-t) x0 + t x1 ) . (y1-y0) dt   which
comes out to  (x0+x1)/2 . (y1-y0). Compute this product over all consecutive
pairs of vertices (don't forget to rejoin the last to the first) and
you'll have the area of the polygon.

Likewise you can compute the integrals of  x^2/2  and  xy  on this curve;
If I haven't messed up, the first is  (x0^2 + x0 x1 + x1^2)/6 . (y1-y0)  
and the latter is  ( (y0 x1 + x0 y1) + 2(x1 y1 + x0 y0) )/6 . (y1 - y0).

So here's a procedure to find the enclosed area:
Clear counters  Area, Xcoord, Ycoord.
For each  i= index of the points x[i], y[i]:
        Let  x0=x[i], y0=y[i]
        Let  x1=x[i+1], y1=y[i+1], where  i+1=first index if  i=last
        Compute factors  a1=(x0+x1)/2,
                a2=(x0^2+x0x1+x1^2)/6, and
                a3=(x0y1+y0x1+2(x1y1+x0y0))/6, as well as
                b=y1-y0
        Adjust counters Area=Area+a1. b,
                Xcoord=Xcoord+a2. b,  and
                Ycoord=Ycoord+a3. b.
Then the center of mass is at  (Xcoord/Area,  Ycoord/Area).

If you need to do this computation very often (i.e. you need it fast each
time) it makes sense to keep various partial products handy; I'll
leave this to professional programmers.

dave



Sat, 24 May 1997 03:52:59 GMT  
 Algorithm to find center of mass.
Is it really that critical to use the actual center of mass?
The center of the bounding rectangle is a lot cheaper to compute and
might be sufficient.

Ken Walter



Sun, 25 May 1997 03:53:30 GMT  
 Algorithm to find center of mass.

Quote:
> Is it really that critical to use the actual center of mass?
> The center of the bounding rectangle is a lot cheaper to compute and
> might be sufficient.

> Ken Walter

        Seems to me that this computation only has to be done once
for each mass. I don't see how it's going to be a performance
bottleneck.
        -- Pete


Sun, 25 May 1997 23:33:33 GMT  
 Algorithm to find center of mass.
Here's a C program to compute center of mass.  Somebody previously showed how to integrate 1, x, and y over the area of the polygon by evaluating line integrals around the perimeter.  Kudos to them, who I am unable to name at the moment; this news server appears to expire articles quickly.

I was proceeding along the same lines, thinking of the problem in terms of adding in the contribution of each trapezoid formed by adjacent points on the polygon and their projections onto the x axis.  Using trapezoids yields the same formulae the earlier poster gave.

Once I had those, I changed it to triangles with vertices at the origin and two adjacent vertices of the polygon.  This yields the slightly simpler formulae used below.

/* Find center of mass of polygon.  Written by Eric Postpischil.  */

#include        <malloc.h>
#include        <stdio.h>
#include        <stdlib.h>

/* Define a point to be an ordered pair. */
typedef struct
{
        double  x, y;

Quote:
} Point;

/* This is a safe allocation routine for points.  Input is a pointer to an
   array of points, a pointer to the current number of allocated points,
   and the index (not number) of the last desired point.

   If sufficiently many points are allocated, nothing is done.  Otherwise,
   enough memory is allocated to provide for the desired point, and then
   some.

   Initially, when no points are allocated, p must be NULL and current
   must be zero.  */
Point   *spalloc(Point **p, int *current, int desired)
{
        if (desired >= *current)
        {
                *current = desired < 8 ? 8 : 2 * desired;
                *p = realloc(*p, *current * sizeof **p);
                if (*p == NULL)
                {
                        fprintf(stderr, "Out of memory\n");
                        exit(1);
                }
        }

Quote:
}

/* Read points describing the vertices of a polygon and compute its center
   of mass.  */
void    main(void)
{
        Point   *p = NULL;
        double  area, t, x, y;
        int     allocated = 0, i, n;

        /* Read each pair of points.  */
        for (n = 0; 2 == scanf("%lg%lg", &x, &y); n++)
        {
                spalloc(&p, &allocated, n);
                p[n].x = x;
                p[n].y = y;
        }

        if (n == 0)
                printf("Undefined\n");
        else
        {
                /* Copy the 0-th point to the n-th point, to close the loop.  */
                spalloc(&p, &allocated, n);
                p[n] = p[0];

                /* Compute the center of mass.  See comments below.  */
                area = x = y = 0;
                for (i = 0; i < n; i++)
                {
/* Define x0, x1, y0, and y1 to refer to the current and next x and y
   values.  These just make the following formulae a little less cumbersome.  */
#define x0      (p[i].x)
#define x1      (p[i+1].x)
#define y0      (p[i].y)
#define y1      (p[i+1].y)

/* Consider a triangle with vertices at (0,0), (x0,y0), (x1,y1).  The union of
each such triangle, as the points (x0,y0) and (x1,y1) are iterated through the
vertices of the polygon, are the entire polygon.  This is clear if the origin
is inside the polygon, but, even if the polygon does not contain the origin,
some of these triangles will have negative area, and the sum will be correct
for the polygon.

Given this, we can compute the integral of a function over area of the polygon
by computing the integrals for each triangle and summing them.  */
                        /* Sum integral of 1 over that triangle.  */
                        area += (y1*x0-y0*x1)/2;
                        /* Sum integral of x over that triangle.  */
                        x += (x0+x1)*(y1*x0-y0*x1)/6;
                        /* Sum integral of y over that triangle.  */
                        y += (y1+y0)*(y1*x0-y0*x1)/6;
                }
                /* Now divide to get int x dA / int 1 dA and
                   int y dA / int 1 dA.  */
                x /= area;
                y /= area;
                printf("area = %lg, center = (%lg, %lg)\n", area, x, y);
        }

Quote:
}

                                -- edp (Eric Postpischil)
                                "Always mount a scratch monkey."

PGP key fingerprint:  8E AD 63 61 BA 0C 26 86  32 0A 7D 28 DB E7 6F 75



Mon, 26 May 1997 08:38:26 GMT  
 
 [ 16 post ]  Go to page: [1] [2]

 Relevant Pages 

1. Algorithm to find center of mass

2. Need center of circle algorithm...

3. Djykestra's Algorithm Problem To Find Shortest Distance

4. Find and Replace algorithm?

5. efficient algorithm to find duplicates in an array

6. help needed finding algorithms

7. gif color-finding algorithm

8. Utility to find out modified record using Checksum algorithm

9. Where can find info about algorithm?

10. Need algorithm to find permutations of a set

11. algorithm finding common strings in a buffer

12. need a fast algorithm to find power of two ceilings

 

 
Powered by phpBB® Forum Software