Algorithm to fit windows on desktop (like tile)

Question

I searching algorithm to solve problem like this:

I have few windows, each window can be moved and re sized but with specified ratio between width and height, eg. 2:1 (height:width).

Each window can't be on other window and all windows must be fully visible. Free area (desktop wallpaper visibility) must be minimal.

Can anyone tell me what algorithm i need for this type of problem?

Greetings,

Answer 1

Another approach, which might be simpler to implement than packing, would be to subdivide your screen size into the required number of panes, then fit a window which satisfies your other requirements inside the pane. Since you'll probably have a small number of windows open at any time, and since your screen doesn't change its size dynamically, you can probably pre-compute all the arrangements you need for 1 up to O(100) open windows.

Answer 2

One approach would be to treat it as a 2D packing problem, like the 1D bin packing problem. There's a sample algorithm posted here, for example, with some good references.

Answer 3

If you can relax the requirement that all windows have a given "aspect ratio" then the problem becomes very simple. Suppose you have N "tiles" to arrange on a single screen, then these can be arranged in columns where the number of columns, NumCols is the square root of N rounded up when N is not a perfect square. All columns of tiles are of equal width. The number of tiles in each column is then N/NumCols rounded either up or down as necessary to make the total number of columns be N. This is what Microsoft Excel does under View > Arrange All > Tiled. Excel chooses to put the columns with one fewer tiles on the left of the screen.