Challenge: Bitmap Centroid
I'd like to calculate the centro开发者_如何学JAVAid of a bitmap (black and white) stored as a bit-packed array of integers. I know there are fast algorithms for counting the number of set bits in an integer, but this doesn't help me calculate a centroid. Any ideas?
As an example, if my bitmap looks like this:
111000
111000
111000
000000
000000
000000
The centroid is at 1, 1. Packed into 32 bit integers (you choose the Endian), it might look like this: {width: 6, height: 6} { 3817734144, 0 }.
Bonus points if you can also get the mass (9 in the example) without iterating over each bit.
Let's assume you're going to process this a row at a time. (Once you've got the total mass, and center of mass of each row, it's a weighted average to get the x and y coordinates of the centroid).
So in other words you've got a row of bits bi and you want to calculate the sum of bif(i) for some functions f. If f(i)=1, that's the bit count (let's call that C), and if f(i)=i, it'll give the total moment of the mass M (which you'll divide by C to get the center of mass).
For inputs less than 8 bits, you can easily store tables for C and M, each 256 bytes wide. Let's write numbers bigger than 8 bits as h:l, where l is the lower 8 bits of the number, and h is the rest of the bits.
Then
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)
the only tricky bit being the 8C(h), corresponding to those C(h) bits being shifted down 8 places when we calculated M(h) instead of M(h:0).
Non-recursively, if your input as bytes is 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) + ...
and then you can pass M and C to average over all lines.
精彩评论