3
\$\begingroup\$

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:

Diagram detailing desired rectangles within larger rectangle

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
  • Repeat

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.

\$\endgroup\$
  • \$\begingroup\$ I think you have hit on some of the solution also in your statement of the problem. When I meant some, you can shrink the problem space such as minimum size of rect. I will ask, could you make the minimum size rect the granularity/unit size of your box generation? OR at least a multiple of your unit size, therefore you can then enforce some basic rules to ensure you limit your edge cases (in regards to filling the space). If your minimum box size is your base unit size, then every box you generate will be a multiple of that, and therefore any gaps will be at the worst your unit size. \$\endgroup\$ – ErnieDingo Aug 16 '18 at 21:50
3
\$\begingroup\$

I would say... start with the fixed rectangle. Extend either the vertical or horizontal sides to the edges of the area; this gives you 5 rectangles (including the fixed one). Randomly choose any of the N non-fixed rectangles, cut it in half vertically or horizontally, giving you N+1 rectangles. Repeat until you have the number of rectangles you want.

\$\endgroup\$
  • \$\begingroup\$ This seems like the simplest option, and some rudimentary testing seems to show it works quite nicely. I've opted to go with another approach that doesn't require the fixed size square, but thank you! \$\endgroup\$ – codinghands Dec 5 '13 at 4:58
  • \$\begingroup\$ You're welcome, happy to help :) \$\endgroup\$ – ggambett Dec 5 '13 at 9:58
1
\$\begingroup\$

I suspect that positioning rectangles completely randomly could let to a lot of failed solutions, and no clear idea why a solution failed.

My suggestion would be to start at the fixed rectangle and randomly generate adjacent rectangles. In a similar manner to a search such as A*, you would end up with a closed list and an open list, e.g. closed contains rectangles which are completely surrounded and open contains rectangles with at least one free edge. Because they would be generated adjacently, there would be readily available data on potential clashes that may lead to no solution, and at that point you could backtrack. You may also find some heuristics that help the search, e.g. process the open list in order of shortest free edge.

\$\endgroup\$
1
\$\begingroup\$

I would suggest a sweep approach. Starting from the origin, choose one axis (for example y, which I will consider as the columns axis) and generate random sizes for the rects until you reach the end of the axis. This will setup column[0]. For each rect[i] in column[j], you should save rect[i].finalX as the final x coordinate of this rect.

To generate the next column[j + 1] you should, for each rect[i] in column[j], create new rects starting from column[j].rect[i].finalX until you fill all y interval of column[j].rect[i]. The algorithm finishes when one column cannot insert more rects.

It is important to note that this algorithm will create rects with smaller y size as the sweep proceeds. To fix that you could randomly create adjacent rects with same finalX. In the next column you can consider these adjacent rects as one, boosting the y size to work on.

If the procedure is not clear, ask me and I edit the answer with a formal algorithm.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.