algorithm - 挑战 : Bitmap Centroid

Question

我想计算存储为位压缩整数数组的位图(黑白)的质心。我知道有一些快速算法可以计算整数中设置位的数量，但这并不能帮助我计算质心。有什么想法吗？

举个例子，如果我的位图是这样的:

111000
111000
111000
000000
000000
000000

质心位于 1, 1。打包成 32 位整数(您选择 Endian)，它可能看起来像这样:{width: 6, height: 6} { 3817734144, 0 }。

如果您还可以在不迭代每一位的情况下获得质量(示例中为 9)，则加分。

Answer 1

假设您要一次处理一行。 (一旦你得到了总质量和每一行的质心，它就是一个加权平均值来获得质心的 x 和 y 坐标)。

所以换句话说，你有一行位 b_i 并且你想为某些函数 f 计算 b_if(i) 的总和。如果 f(i)=1，那就是位数(我们称之为 C)，如果 f(i)=i，它将给出质量 M 的总力矩(你我将除以 C 以获得质心)。

对于少于 8 位的输入，您可以轻松地存储 C 和 M 的表，每个 256 字节宽。让我们将大于 8 位的数字写成 h:l，其中 l 是数字的低 8 位，h 是其余位。

然后

C(h:l) = C(h:0) + C(0:l) = C(h) + C(l)
M(h:l) = M(h:0) + M(0:l) = M(h) + 8C(h) + M(l)

唯一棘手的位是 8C(h)，对应于当我们计算 M(h) 而不是 M(h:0) 时，那些 C(h) 位被向下移动了 8 个位置。

非递归的，如果你输入的 bytes 是 x0, x1, x2, x3...

C(x) = C(x0) + C(x1) +   C(x2) +   C(x3) + ...
M(x) = M(x0) + M(x1) +   M(x2) +   M(x3) + ...
             +8C(x1) + 16C(x2) + 24C(x3) + ...

然后您可以通过 M 和 C 对所有行进行平均。