Good rectangular covering of an SDF

(I do not claim any optimality, or that I have thought of every detail)

1. Downsample and brute force: You project your black and white map onto a low resolution. On this lower resolution, you may represent any rectangle by two points marking the upper left and lower right corner. If your resolution is low enough, you can iterate through all non-redundant combinations of points, test if they overlap with white areas (i.e. at the enclosed islands), and if not, then you may efficently calculate their area. As you have four rectangles the skaling of the problem will be very bad, but for low resolution you might get away with it.

2. Heuristic: 'growing' rectangles: You pick four locations that lie within the black area. For each of these locations, you 'grow' rectangles outwards until they touch any white area. If you only hit white in x- or y- direction you may still grow into the other one.

You repeat the above process for a large number of seeding points (preferrably in parallel), and then pick the winner. You might also do variations in that you only pick the first point, optimize the corresponding maximally grown rectangle, and then move to the second one etc.

3. Projection : You go to a high resolution grid, and integrate for every row and column, how many black and white pixels there are. In the vertical profile you get for the integration along your rows, and the horizontal profile you get from integrating your columns you can easily determine the maxima, which would be a good place for starting to place (or grow) a rectangle. Then, when you place the second one, you do the same process but take into account the area that you already covered with the first one. You will have to do some corrections for corner cases, but it might save you a lot (numerical) work. I apologize in advance for the following sketch of what i mean:

As I said, this does not really solve your problem, but might be starting points for constructing a heuristic.