Mosaic of rectangles

I have a large window in which there are n small windows. Task to place small windows so that between them there was no intersection, or say that it's impossible to do.

All windows are rectangular and have the coordinates of all vertices.

I understand how easy it is to determine whether cross one of the rectangles with the others. It's enough to look at include whether the coordinates of the vertices in any other rectangle.

But here's how to find a free area where you could move this rectangle?

In my case, small windows appear in the big one. And the problem looks like. 开发者_JAVA百科

---

This looks somewhat like a Rectangle Packing problem. There are examples and implementations out there that can help.

The thing that differs is that you're dealing with an UI, not textures or some other problem. You can go for the above mentioned solutions, but I imagine you will need some sort of transition animation so the user sees/understands where all his/her window will end up.

It depends how this feature works I presume. Is the user allowed to intersect windows in the first place ?

I imagine all rectangles will need to fit into a larget one (the display)

I've been playing with different sized rectangles of paper on my desk and here is something that comes to mind:

1st determine if all you've got enough space: split the left over space into rectangles and add the rectangle areas then check if the space areas are larger or equal to the intersection areas. If so continue.

1. Loop through all rectangles and find intersections.
2. For each intersection, store the rectangles involved.
3. Loop through all the rectangles that have intersections and store the available space in
   the remaining directions (e.g. left,top-left,top,etc.)
4. For each rectangle with intersections, add the horizontal left over space to check if it its larger than the width of the intersection rectangle, then do the same with vertical left over space. This step should allow to determine if you can move only the rectangles with intersections to get enough space to clear intersections.
5. If the above aplies use the remaining space to determine how much you need to move each rectangle. Choose the direction of separation (vertical or horizontal) based on which left over spacing is larger (e.g. total top+bottom vs total left+right). Then move each box in the direction of separation(e.g if horizontal move the rectangle with the smallest horizontal space by that amount, then the other rectangle towards it's remaining space) and re-evaluate the intersection for this case. If there are no intersections, hooray...otherwise, do the same with vertical space.
6. If this pint 4 does not apply that means you can't move the rectangles slightly using the space around them, you need to use more space. Include the nearest box and it's space then check again if the extra space is sufficient.

Here's what I mean by splitting the remaining space into boxes to find the area:

I would suggest first checking the rectangle packing solutions I've linked to, as they use the available space optimally and it actually works, not something I came with by playing with paper :) I haven't coded/tested my solution yet.

HTH

---

A trivial solution is brute force. Take all permutations of the small rectangles and place them one at a time at the top left most position. If you managed to place them, you have a solution. If you fail, you back track to the next permutation and try again. If you run out of options, then you fail. This will work, but obviously it will quickly be unusable when the number of rectangles increases.