Minimum area enclosing rectangles?

Question

I need an idea for an algorithm to solve the following problem (I already tried some personal solutions but they don't seem to be optimal)

If given a surface with marked and unmarked zones (in matrix form), and 2 rectangles that you can manipulate in any form or position, find the possible shape and position of the rectangles such that they cover all the marked zones while keeping the minimum surface area possible.

Answer 1

This answer is assuming you can not rotate the rectangles and the sides are always parallel to the x and y axis.

First, find the rectangle that encloses the complete area. An algorithm for that goes like this (assuming the origin is at the topleft):

For each marked spot in the matrix:
    if spot.x < rectangle.left:
        rectangle.left = spot.x
    if spot.x > rectangle.right:
        rectangle.left = spot.x
    if spot.y < rectangle.top:
        rectangle.left = spot.x
    if spot.y < rectangle.bottom:
        rectangle.left = spot.x

Then, find the largest horizontal gap like this:

largest_gap = -1
For each column in matrix:
     last_marked_spot = 0, 0
     For each spot in column:
         if spot.marked:
             if spot.x - last_marked_spot.x > largest_gap:
                 largest_gap = spot.x - last_marked_spot.x
             last_marked_spot = spot

Same goes for vertical gap. Then check which gap is the biggest.

Then divide the all-including rectangle in two parts using the biggest gap as seperator. The final step is to collapse the two rectangles (using the reverse of the algorithm on the top).