Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I'm hoping someone could help me get a solid algorithm for finding the center of mass of 2D shape without density, based of a set of vertices.

Please explain in simple terms that a non-mathematician could understand (I have no clue how the wikipedia equation works) and easily translate into C++ code for my program! =)

Note: if it makes the algorithm any faster, the complex shapes in my program are really just a group of convex polygons which I can access.

share|improve this question
4  
Like this? Or this and this? –  J. M. Sep 14 '11 at 1:05
    
I have code linked from my web page for this computation: orourke. It is also available in many other locations, of course. –  Joseph O'Rourke Sep 14 '11 at 23:39

1 Answer 1

up vote 7 down vote accepted
  1. Divide your complex polygon into non-overlapping triangles.
  2. The center of mass for each triangle is the simple average of the coordinates of its three corners. (Because this works for an equilateral triangle, and affine transformations preserve centroids and can take any triangle to any other triangle).
  3. Average the centers-of-mass of all the triangles, weighting by the area of each triangle (which you can find as the 2D cross product of two of its sides).
share|improve this answer
    
While this is a valid approach, as @J.M. mentioned, there are much simpler approaches using the coordinates of the vertices directly. Of course, the proof of these formulas relies on Green's theorem or on triangulation, but finding a triangulation is a lot of work for just finding the centroid. –  lhf Sep 14 '11 at 1:39
    
Ah, the OP does mention that the polygons are convex, in which case triangulating them is trivial. –  lhf Sep 14 '11 at 1:40
    
At least one of the methods J. M. links to corresponds exactly to doing this, with a triangulation that consists of choosing a center arbitrarily at (0,0) and drawing lines from there to each vertex of the polygon. If the center is not inside the polygon (or if the polygon is sufficiently nonconvex), some of the triangles must then count negatively -- but the sign of the determinant/cross product handles this automatically. –  Henning Makholm Sep 14 '11 at 1:48
    
Isn't area of the triangle one half of the cross product? –  Alexei Averchenko Sep 14 '11 at 2:46
1  
@Alexei, yes, but the scaling doesn't matter when you're weighting everything with doubled areas. –  Henning Makholm Sep 14 '11 at 11:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.