I'm trying to divide a rectangular image into a fixed number of smaller rectangular image parts (of random but bounded width / height), with the exception of 1 rectangle which is predefined in position and size.
So, for example:
My first thought was:
- Generate list of possible points
- From this list remove all points in the fixed size rect
- From this list remove all points that can't possibly meet the other requirements (e.g. points close to the image edges that wouldn't meet the required bounded min / max rect size)
- Then randomly pick a point, generate a random bounded width / height, see if this intersects any current rect, until we find one that doesn't
- Record rect, remove all points in rect from list
However this seems slow, overly-complex and still results in holes because sometimes there's no more room for the minimum size of rect to fill the last bit of space.
I've looked into algorithms involving squaring the square, packing routines and such like, but nothing I've found helps with the additional constraint that one rectangle is predefined and the rest can be random.
Not looking necessarily for a full algorithm, but hints at an approach would be appreciated.