Finding the center of mass on a 2D bitmap

Question

I'm coding a game, and I'd like to be able to find the center of mass of an arbitrary shape on a black and white bitmap such as this:

 012345678
0.XX......
1..XXX....
2...XXX...
3..XXXXXXX
4...XXX...

All "cells" have the same weight. Diagonally adjacent cells are not considered to be connected, and the shape will always be a single one since it's already split by another function before this.

It's only going to be used for reasonably low resolution (maybe 50x50 at most) images and it doesn't need to be super accurate, speed is preferable.

I get a feeling there's a proper way to do this, but I don't really know what to google for.

I'm coding this in Actionscript 3, but examples in any language are appreciated, moreso if they're made to be understood by humans.

EDIT: Feel free to assume that the data is stored in whatever data structure you think is most convenient for your example. I'm using bitmaps, but two-dimensional arrays or even a single array is just fine too!

EDIT: This is the code I ended up using, it can most likely be done faster, but I find this to be very readable:

// _bmp is a private BitmapData instance
public function getCenterOfMass():Point {
    var avg  :Point  = new Point(0, 0);
    var points :uint  = 0;

    for (var ix:uint = 0; ix < _bmp.width; ix++) {
     for (var iy:uint = 0; iy < _bmp.height; iy++) {
      if (_bmp.getPixel(ix, iy) == ACTIVE_COLOR) {
       avg.x += ix;
       avg.y += iy;
       points++;
      }
     }
    }

    avg.x /= points;
    avg.y /= points;

    return avg;
}

Answer 1

How about this algorithm (psuedo-code) based on a boolean matrix like in your example :

xSum = 0
ySum = 0
points = 0

for point in matrix
    if point is marked
        xSum += pointX
        ySum += pointY
        points++

return (xSum/points, ySum/points)

Nothing too complicated, calculate where X is the most present, same for Y, divide by number of points you counted, and you got the center of mass. You can further complicate this by giving certain points different weight in the averaging, but this should be your main direction.

---

This question got me thinking about an expansion to this question which I could not find a good answer to. I posted the question here: http://stackoverflow.com/questions/411837/finding-clusters-of-mass-in-a-matrix-bitmap

Answer 2

Depending on the nature of your actionscript interpreter and the pre-processing done on the shapes, you may see a speed improvement (over the direct approach pointed out by Yuval) by initially creating a second copy of the bitmap/array mirrored diagonally, then using row or string manipulation functions to sum the points on each row and column in single steps. This would be O(2m*n) instead of O(n*n) [see below], but with more overhead.

xSum = 0
ySum = 0
points = 0

for row in matrix
  ySum += rowX * countpoints(row)
  points += countpoints(row)
for row in mirroredmatrix
  xSum += rowX * countpoints(row)

return (xSum/points, ySum/points)

Where countpoints() counts the on-points in a row. This relies on countpoints (which has O(n) runtime) having a lower constant multiplier than the naive approach's runtime (hence above, 'm' being the runtime of countpoints and 'n' being the time for the interpreter to loop through a row). The nature of countpoints() depends on your storage method, which may involve counting characters in a string, or bits in a bitfield.

Answer 3

You could count the number of adjoining cells, then center on the cells with the highest neighbor count.

 012345678
0 XX      |
1  XXX    |
2   XXX   |
3  XXXXXXX|
4   XXX   |

 012345678
0 23      |
1  454    |
2   775   |
3  3686421|
4   454   |

In this example you could use the only cell with an 8, as the center point.

If you came up with multiple cells with the same number of neighbors, you would just run the counting routine again, but this time just with the high number cells.

For example, lets pretend that the cells that had 6, 7, and 8, instead all had eight neighbors.

 012345678
0 23      |
1  454    |
2   885   |
3  3888421|
4   454   |

 012345678
0 --      |
1  ---    |
2   XX-   |
3  -XXX---|
4   ---   |

 012345678
0 --      |
1  ---    |
2   34-   |
3  -342---|
4   ---   |

 012345678
0 --      |
1  ---    |
2   -X-   |
3  --X----|
4   ---   |

In the case of a simple tie, I would go with the one that was nearer the center. In this case it would be the upper one of the two.

Note: I'm assuming your not using this for an accurate physics simulation.