First, we are able to convert your supply rectangles to cells in your underlying grid, to make the enter extra uniform. (Effectively rasterizing the issue)

This will allow us to discover optimizations that may not be apparent when working immediately with the supply rectangles – significantly when it entails splitting a number of supply rectangles to recombine them otherwise.

Next we are able to discover related areas of the identical color, utilizing depth-first-search or flood filling algorithms. We can think about every related area (a polyomino) in isolation – nothing that we do to a special area must affect this one.

Effectively we wish to discover a approach to dissect this polyomino into rectangles (sadly a lot of the literature I can discover is in regards to the reverse drawback: dissecting rectangles into polyominoes! This makes it tough to seek for leads…)

One simple methodology is to mix horizontal runs of adjoining squares into lengthy skinny rectangles. Then we are able to examine towards the row above and mix if our run begins & ends match up – both as we end every run/row, or as we think about every cell so as to add to the present run.

I do not know but how shut this methodology will get to optimum. It appears it might probably run right into a little bit of bother when a row it hasn’t thought of but suggests a special cut up than the rows it is seen to this point:

Detecting when a run/rectangle is precisely coated by runs above & under, then splitting it and merging them will remedy this specific case, however I have never explored how basic the issue is.

I’ve additionally checked out strategies the place we stroll the perimeter of the polyomino, and reduce throughout anytime we encounter a concave nook, however this method seems extra error-prone to me. Getting optimum outcomes appears to require prioritizing cuts that be a part of two concave corners, and shapes containing hollows want particular dealing with, so the row scan methodology appears to have the simplicity benefit.

One extra methodology I’m taking a look at is to take the primary run discovered within the high row & prolong it down so far as you possibly can. Then take the primary run within the high row of what is left… This will get tripped-up on inverted T shapes although, so it isn’t optimum both.

I really feel like there’s in all probability a manner to make use of dynamic programming to seek out the optimum cut up, however I have never discovered it but.