Filling stuff up with boxes
category: general [glöplog]
Ok, so I have this two-colour bitmap. Pixels in the bitmap are either on or off in no particular pattern, except for the most part on-pixels will be clustered together to form "natural" shapes (think silhouettes of natural objects, sort of thing). Now I want to construct n non-overlapping rectangles so that they cover the largest amount of on-pixels without covering any off-pixels. Or in other words I want to fill up as much as possible of a bitmap shape using n non-overlapping rectangles, or, alternatively, an arbitrary number of rectangles as long as I can impose some restrictions like a minimum size for each rectangle.
I don't necessarily need a perfect solution, just a reasonably good one, and it mustn't take several hours to compute. Does anyone have any ideas on this?
I don't necessarily need a perfect solution, just a reasonably good one, and it mustn't take several hours to compute. Does anyone have any ideas on this?
just an ugly, fast idea..
1. create arrays containing something like: scanline number, start pixel, end pixel (one array for each single-horizontal-line part of image, in case you have in some part of image several horizontal lines, you'll need to split it into several arrays)
2. create a function returning the biggest possible rectangle for any given array of start-end pixels (i don't have one, hey, it's a fast and ugly solution:P)
3. call that function, remember that rectangle and split that array into 4 other arrays (top, bottom, right, left) - top and bottom should be straightforward, for left and right just set end and start pixels to rectangle boundary, respectively.
1. create arrays containing something like: scanline number, start pixel, end pixel (one array for each single-horizontal-line part of image, in case you have in some part of image several horizontal lines, you'll need to split it into several arrays)
2. create a function returning the biggest possible rectangle for any given array of start-end pixels (i don't have one, hey, it's a fast and ugly solution:P)
3. call that function, remember that rectangle and split that array into 4 other arrays (top, bottom, right, left) - top and bottom should be straightforward, for left and right just set end and start pixels to rectangle boundary, respectively.
oh, and one more.
4. repeat step 3 for every single array, with those created during that process included (recursion?), until there's nothing left :P
4. repeat step 3 for every single array, with those created during that process included (recursion?), until there's nothing left :P
No idea whether this will be anywhere near optimal (or indeed whether it's stupidly obvious), but what the hell...
Code:
Generate quadtree representation of image (or something similar, perhaps using binary subdivision instead).
Begin with an empty set of rectangles.
while size of set < n:
Take next biggest square out of quadtree, add to the set
See if that square can be merged with any other rectangle in the set
(and if so, repeat that test with the resulting rectangle)
end
Well, I guess I would just scan through the image, from top to bottom, detect on-stripes ( bounds(x,y,1,stripe_height) ), save them, divide them if needed (obviously not needed, if height=1), and be done with it. I _think_ that's basically what unic0rn said. But I guess gasman's approach makes more sense and gives better results.
You could also throw random rectangles at your 1-bit image. if the rectangle covers only on-material, keep it and save it, if not discard it. Repeat n-times to get a close enough approximation. So, yes, this is "stupid" and brute-force, but it is easy to implement and it looks differently every time you run it. If you don't want any overlap, you'd have to check for that too. :)
You could also throw random rectangles at your 1-bit image. if the rectangle covers only on-material, keep it and save it, if not discard it. Repeat n-times to get a close enough approximation. So, yes, this is "stupid" and brute-force, but it is easy to implement and it looks differently every time you run it. If you don't want any overlap, you'd have to check for that too. :)
