0

I have lists of coordinates for "good" rectangles and "bad" rectangles. Rectangles may or may not be adjacent to others from either list, but will never overlap. I need to generate the fewest possible number of new rectangles that fully overlap the good rectangles, without intersecting any of the bad ones (or each other). The new rectangles are allowed to cover any amount of empty space as long as they don't violate the other criteria; the area of them doesn't matter at all, only the quantity. If there are multiple equivalent solutions I just need one, chosen arbitrarily.

Here's an illustration of what I mean. When drawing the new rectangles by hand, we can see that the fewest amount possible is three.

This is very similar to this question, but the biggest difference is my bad rectangles list. My original idea was to define a rectilinear polygon by outlining the area enclosing all good rectangles (and any empty space necessary), and treating the bad rectangles as holes. Then, I'd dissect this polygon, and delete any resultant rectangles that enclose purely empty space.

However, I quickly realized that while this method could lead to this correct answer, it could also easily lead to this very incorrect answer. My outline would need to be "shrinkwrapped" to the good rectangles somewhat in order to force a correct answer, but not too much either, so I'm not sure if there's a different approach that would be simpler and more reliable.

goodRectangles = [

[(-7, 4), (3, 4), (3, -1), (-7, -1)],
[(4, 3), (11, 3), (11, 1), (4, 1)],
[(2, 6), (3, 6), (3, 5), (2, 5)],
[(3, 6), (7, 6), (7, 3), (3, 3)],
[(7, 9), (9, 9), (9, 7), (7, 7)]

]

badRectangles = [

[(8, 4), (10, 4), (10, 3), (8, 3)] 
[(-2, 8), (1, 8), (1, 5), (-2, 5)],

]


def enclosingRectangles( goodRectangles, badRectangles ):
    
    [...]

    return newRectangles

    
newRectangles = enclosingRectangles(goodRectangles, badRectangles)
eyelash
  • 1

0 Answers0