actionscript-3 - 在 2D 位图上找到质心

Question

我正在编写一个游戏，我希望能够在黑白位图上找到任意形状的质心，如下所示:

 0123456780.XX......1..XXX....2...XXX...3..XXXXXXX4...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

这个基于 bool 矩阵的算法(伪代码)怎么样，就像在你的例子中一样:

xSum = 0
ySum = 0
points = 0

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

return (xSum/points, ySum/points)

没什么太复杂的，计算X在哪里最存在，Y也一样，除以你计算的点数，你就得到了质心。您可以通过在平均中给某些点不同的权重来进一步复杂化，但这应该是您的主要方向。

---

这个问题让我想到了这个问题的扩展，但我找不到很好的答案。我在这里发布了问题:Finding clusters of mass in a matrix/bitmap