I have a 2D SDF describing my shape, but it's fine to think of it as a black/white image (black="inside" white="outside").
I want to generate a small set of rectangles (say, 8 of them) covering the image, which are allowed to overlap, and which minimize the amount of error. Error would be any leftover "black" areas of the image that are not covered.
The image could be convex, have holes, etc. It is general.
I realize that minimal rectangle covering is NP-hard, though that's not exactly what I'm asking for: I'm asking for minimizing error given a finite set of rectangles to work with. Maybe it's just as hard though; not sure.
Anyway, I do not need to find the perfect solution; decent heuristics would be fine.
I could imagine some pretty general "greedy search" traversal of the state space, but wondered if there were any tricks anyone knows of.
Aside: I've also looked at several papers for "rectangular decomposition", and "minimal dissection", but those problems generally assume I want disjoint rectangles. Disjoint would be okay, but really I want maximal coverage while allowing overlap.
Edit Here is an example:
Covering with 4 rectangles (red, green, blue, yellow):
Any uncovered black pixels are the "error". No white pixels are allowed to get covered.