挑战：位图质心

Question

我想计算一个以整数位压缩数组形式存储的黑白位图的重心。我知道有快速算法来计算一个整数中设置位的数量，但这并不能帮助我计算重心。有什么想法吗？

例如，如果我的位图如下所示：

111000
111000
111000
000000
000000
000000

重心位于点(1, 1)。若使用32位整数（您可以选择端序），则其可能如下所示：{width: 6, height: 6} {3817734144, 0}。

如果能在不迭代每个位的情况下计算出质量（例如为9），则额外加分。

- Stefan Mai

---

我认为这对算法来说并不重要，但是为了记录：您需要浮点精度还是整数坐标就足够了？如果是后者，应该如何进行四舍五入？ - Thomas

质心的计算可能会通过前面提到的一种设置位计数算法变得非常简单。最简单的方法可能是将其作为单独的步骤进行处理。至于质心，我的直觉是你的数据表示方式实际上对你不利，因为将其打包成整数会在空间节省方面进行交换，而对于任何关心位的几何布局的复杂度来说，这会增加时间复杂度。 - Martin DeMello

@Martin 我也有这种感觉，但我需要在这个位图上渲染几何图形并快速查询单个点。实际的渲染过程并不是瓶颈，所以如果你能建议更好的表示方法，我会很感兴趣。 - Stefan Mai

如果空间不是问题，只需将宽度向上舍入到最近的字节，并表示为数组（即填充每行以使其字节对齐；例如，在您引用的示例中，数组将为6x8）。这样计算质心会更容易。 - Martin DeMello

8倍的空间增加，但我不知道在32位或更高架构上如何帮助你？ - Stefan Mai

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 个位置。

非递归地，如果您的输入为 字节 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 来平均所有线路。

- Chris Nash