代码之家 › 专栏 › 技术社区 › grapefrukt

在二维位图上查找质心

language-agnostic algorithm actionscript-3

11

grapefrukt · 技术社区 · 16 年前

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

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

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

它只适用于相当低分辨率(最多50x50)的图像,不需要超精确,速度更可取。

我有一种感觉,有一种正确的方法可以做到这一点,但我真的不知道该在谷歌上搜索什么。

我在Actionscript 3中编写了这个代码,但任何语言的示例都是受欢迎的,如果它们是为了让人类理解的话。

编辑:可以随意假设数据存储在您认为对您的示例最方便的任何数据结构中。我使用位图,但二维数组甚至单个数组也可以!

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

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

3 回复 | 直到 16 年前

1

19

Community CDub 8 年前

这个基于布尔矩阵的算法(psuedo代码)怎么样,就像你的例子一样:

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

2

Brad Gilbert 16 年前

您可以计算相邻单元格的数量,然后以邻居计数最高的单元格为中心。

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

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

在这个例子中,你可以使用唯一一个带有 8 ,作为中心点。

如果你想出了多个具有相同数量邻居的单元格,你只需再次运行计数例程,但这次只是针对高数量的单元格。

例如,让我们假设具有 6 , 7 ,以及 8. 相反,他们都有八个邻居。

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

如果是简单的领带,我会选择离中心更近的领带。在这种情况下,它将是两者中的上一个。

注意:我假设您没有将其用于精确的物理模拟。

3

1

Sparr 16 年前

根据您的actionscript解释器的性质和对形状进行的预处理,您可能会看到速度的提高(与Yuval指出的直接方法相比),首先创建对角镜像的位图/数组的第二个副本,然后使用行或字符串操作函数在单个步骤中对每行和每列上的点求和。这将是O(2m n) 而不是O(n n) [见下文],但开销更大。

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)

其中countpoints()连续计算点数。这依赖于计数点(具有O(n)运行时)的常数乘数低于朴素方法的运行时(因此,上面的'm'是计数点的运行时,'n'是解释器循环一行的时间)。countpoints()的性质取决于您的存储方法,这可能涉及对字符串中的字符或位字段中的位进行计数。