19
$\begingroup$

I would like to write a simple program that accepts a set of windows (width+height) and the screen resolution and outputs an arrangement of those windows on the screen such that the windows take the most space. Therefore it is possible to resize a window, while maintaining output size >= initial size and the aspect ratio. So for window $i$, I'd like the algorithm to return a tuple $(x, y, width, height)$.

I believe this is might be a variation of 2D Knapsack. I've tried going over results around the web but they mostly had a lot of background (and no implementation) that made it hard for me to follow.

I'm less interested in the fastest possible algorithm, but more in something that is practical for my specific need.

$\endgroup$
  • 1
    $\begingroup$ If you are resizing a window, you are not "maintaining its initial size", just its aspect ratio, I presume. $\endgroup$ – Emre Apr 10 '12 at 23:56
  • 1
    $\begingroup$ You can resize one window to cover the screen, what is the problem? $\endgroup$ – user742 Apr 11 '12 at 7:34
  • 2
    $\begingroup$ I second Saeed's comment. You need additional constraints like minimal sizes the goal of minimising the sum of resizings if you want to exclude trivial solutions. Nota bene: mathematicians seem to call tiling problems tessellations. $\endgroup$ – Raphael Apr 11 '12 at 10:09
  • 1
    $\begingroup$ May be is better to say, you want maximize minimum viewable window area and minimize maximum viewable window area, but conflicts are allowed or not? Please edit your question to make it bug free, thinking about current problem statement is not easy. $\endgroup$ – user742 Apr 11 '12 at 14:27
  • 2
    $\begingroup$ @daniel.jackson: He suggests that you should strive for a constellation where the smallest window is as large as possible, i.e. you don't have really small windows. Mathematically, you can say you maximise $\min_{w \in W} \mathrm{size}(w)$ with $W$ the set of windows. $\endgroup$ – Raphael Apr 11 '12 at 19:57
9
$\begingroup$

Although your question does not say it, I'm assuming that you do not want windows to overlap.

One approach to this problem is to use a constraint solver such as Choco. One simply writes down the constraints encoding your problem, tunes the solver to act in a smart way, and then let it run. This means that all the thinking you need to do will be spent on finding a good way of encoding the problem, not on devising an algorithm and doing the programming and tuning. Here is a partial answer to get you started.

Assume that the screen size is by $x_{max}\times y_{max}$.

For each window, $W_i$, you'll have a set of variables $x_i, y_i, h_i, w_i$ and constraints

  • $x_i,y_i,h_i,w_i\ge 0$
  • $x_i + w_i \le x_{max}$
  • $y_i + h_i \le y_{max}$
  • Perhaps also some constraints on the minimal size of windows, e.g., $h_i\ge 100$ and so forth.
  • Aspect constraints: If aspect ratio is 3:4, the constraint could be something like $4h_i - \epsilon \le 3 w_i \le 4 h_i + \epsilon$, where $\epsilon$ is some small non-zero error term to allow for non-perfect window sizes, as otherwise you'd over constraint the problem.

Now you need to take care of window overlap. For each pair of windows, $W_i, W_j$, where $i\neq j$, you'll generate constraints like the following, which capture that no corner of $W_j$ appears within $W_i$. For $(x,y)\in\{(x_j,y_j), (x_j+w_j,y_j), (x_j,y_j+h_j), (x_j+w_j,y_j+h_j)\}$, generate constraint:

  • $\neg(x_i \le x\le x_i + w_j \wedge y_i\le y \le y_i+h_j)$.

The constraints specified thus far only describe non-overlapping windows that do not spill over the sides of the screen, that satisfy some minimal size constraints, and that preserve their aspect ratio.

In order to get a good fit, you need to specify a metric that captures what it means to be a good layout. One possibility is to assume that you want to keep windows roughly equal in size and/or that you want to minimize "white space". I do not think that this can be specified using Choco, but it may be possible with another constraint solve (someone else might be able to help here).

Choco does allow one to maximize wrt to an objective function specified as a single variable. Based on this idea, you could maximize the following:

  • $\sum_i (h_i + w_i)$

by writing a constraint $\mathit{cost}=\sum_i (h_i + w_i)$ and telling Choco to maximize $\mathit{cost}$.

$\endgroup$
  • $\begingroup$ This looks promising and I'll definitely play with Choco to see how this works, and how fast. $\endgroup$ – daniel.jackson Apr 12 '12 at 15:12
  • $\begingroup$ But why phrase it that generally ? I think you can phrase the constraints as linear inequalities, which means that what you have is a vanilla linear program. $\endgroup$ – Suresh Apr 13 '12 at 19:58
  • $\begingroup$ @Suresh: Feel free to elaborate. I don't immediately see how to. $\endgroup$ – Dave Clarke Apr 13 '12 at 20:04
1
$\begingroup$

I started writing a prototype for a brute force solution, that hopefully can be optimized to a point where it will be practical.

First, some definitions: Let $W$ be the set of all windows. Each window $w$ is composed of $x_w, y_w, w_w, h_w$ for the x, y coordinates and the width and height. A window is initialized with a minimum width and height.

The input of the algorithm is the screen, $S$, which has a width and height and a list of windows.

It works roughly so:

void fit(W, S, i, n, result)
    if i == n
        if S.score() < result.score()
            result = S
        return

    w = W[i]
    foreach x, y in S.coordinates()
        set w position to (x, y)
        while S.put(w) # check that w doesn't overlap with S's other windows and add it
            fit(W, S, i+1, n, result)
            S.windows.pop()
            w.grow()
        w.restoresize()

There are a few things that should be improved:

  • S.coordinates() is very slow right now. It iterates all points in S.width x S.height and checks if each one is in one of S's windows.

  • S.put() checks if its parameter overlaps with the rest of S's windows by doing the test mentioned in Dave's answer. Maybe this can be improved by using interval trees?

  • S.score() currently returns $\sum_{w \in S.windows} (h_w \cdot w_w)$ which is simply the area of all windows. It needs to take into account other variables to produce better layouts.

  • The above function needs to try all permutations of $W$ to get the best possible result.

I am currently trying to figure out a suitable data structure to represent the screen and its windows, it needs to support these queries:

  • return a list of coordinates where a given window can be positioned without overlapping with others
  • insert window at position x, y (already verified that it doesn't overlap)
  • return all windows
$\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.