在 2D 位图上找到质心 [英] Finding the center of mass on a 2D bitmap

问题描述

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

<前>0123456780.XX……1..XXX....2...XXX...3..XXXXXXX4...XXX...

所有细胞"都具有相同的权重.对角相邻的单元格不被认为是连接的，并且形状将始终是单个的，因为在此之前它已经被另一个函数分割了.

它只会用于相当低的分辨率(最多可能是 50x50)图像，它不需要非常准确，速度更可取.

我觉得有一种正确的方法可以做到这一点，但我真的不知道该用谷歌搜索什么.

我在 Actionscript 3 中编写代码，但任何语言的示例都值得赞赏，更重要的是，如果它们能够被人类理解.

随意假设数据存储在您认为对示例最方便的任何数据结构中.我用的是位图，但二维数组甚至单个数组也可以！

这是我最终使用的代码，它很可能可以更快地完成，但我发现这非常易读:

//_bmp 是一个私有的 BitmapData 实例公共函数 getCenterOfMass():Point {var avg :Point = new Point(0, 0);变量点:uint = 0;for (var ix:uint = 0; ix <_bmp.width; ix++) {for (var iy:uint = 0; iy <_bmp.height; iy++) {如果 (_bmp.getPixel(ix, iy) == ACTIVE_COLOR) {平均.x += ix;avg.y += iy;积分++；}}}avg.x/= 点数；avg.y/= 点数；平均回报；}

解决方案

这个基于布尔矩阵的算法(伪代码)怎么样，比如你的例子:

xSum = 0y总和 = 0点数 = 0对于矩阵中的点如果点被标记xSum += pointXySum += pointY积分++返回(xSum/点数，ySum/点数)

没什么太复杂的，计算 X 出现最多的位置，Y 也一样，除以你计算的点数，你就得到了质心.您可以通过在平均值中为某些点赋予不同的权重来进一步复杂化，但这应该是您的主要方向.

<小时>

这个问题让我想到了这个问题的扩展，我找不到一个好的答案.我在这里发布了这个问题:在矩阵/位图中寻找质量簇

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;
}

解决方案

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: Finding clusters of mass in a matrix/bitmap

这篇关于在 2D 位图上找到质心的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！