Algorithm to find center of mass.
Author 
Message 
Keith Sibs #1 / 16

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 


Roland SchmittHartmann US/ENB 60/1/86 #491 #2 / 16

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 


Thomas D Bendi #3 / 16

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 SchmittHartmann'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 


Roland SchmittHartmann US/ENB 60/1/86 #491 #4 / 16

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 


Joe Nardel #5 / 16

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 xaxis. 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 


James Prest #6 / 16

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 xcoord of the centroid is given by the first moment of the figure about the yaxis 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 xaxis is given by the formula a1 = (x2x1)*((y1+y2)/2); The moment of the same trapezoid about the yaxis is given by the formula which is a little ugly because I just made it up: m1_y = (x1+(x2x1)/2))(x2x1)y2 + ((y1y2)(x2x1)/2)(x1 +(x2x1)/3)); Now if you look at these equations you will see that the (x2x1) 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 


Igor Chud #7 / 16

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)5882309 Systems Engineer, for WilTel. home (918)5855862
http://mnet.arbornet.org/~ichudov 1819 South Jackson #32P 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 


Thomas Koen #8 / 16

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 


Huayong YA #9 / 16

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 


Teddy Grenm #10 / 16

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 xaxis. 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 


Joe Nardel #11 / 16

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 


Dave Rus #12 / 16

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) = ( (1t) x0 + t x1, (1t) y0 + t y1 ) so that dy = (y1  y0) dt. Thus, the integral of x dy along this curve is integral_[0,1] ( (1t) x0 + t x1 ) . (y1y0) dt which comes out to (x0+x1)/2 . (y1y0). 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 . (y1y0) 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=y1y0 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 


Solution Technolo #13 / 16

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 


Pete Becke #14 / 16

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 


Eric Postpisch #15 / 16

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 0th point to the nth 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*x0y0*x1)/2; /* Sum integral of x over that triangle. */ x += (x0+x1)*(y1*x0y0*x1)/6; /* Sum integral of y over that triangle. */ y += (y1+y0)*(y1*x0y0*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 


Page 1 of 2

[ 16 post ] 

Go to page:
[1]
[2] 
