Comment concevoir un algorithme pour disposer des fenêtres (redimensionnables) à l'écran pour couvrir autant d'espace que possible?

Je voudrais écrire un programme simple qui accepte un ensemble de fenêtres (largeur + hauteur) et la résolution d'écran et affiche une disposition de ces fenêtres à l'écran de sorte que les fenêtres prennent le plus d'espace. Il est donc possible de redimensionner une fenêtre, tout en conservant output size >= initial sizeet le rapport hauteur / largeur. Donc, pour la fenêtre $i$ , j'aimerais que l'algorithme retourne un tuple $(x, y, width, height)$ .

Je pense que c'est peut-être une variante du sac à dos 2D. J'ai essayé de passer en revue les résultats sur le Web, mais ils avaient pour la plupart beaucoup d'expérience (et aucune implémentation), ce qui m'a rendu difficile à suivre.

Je suis moins intéressé par l'algorithme le plus rapide possible, mais plus par quelque chose de pratique pour mes besoins spécifiques.

Bien que votre question ne le dise pas, je suppose que vous ne voulez pas que les fenêtres se chevauchent.

Une approche de ce problème consiste à utiliser un solveur de contraintes tel que Choco . On écrit simplement les contraintes codant votre problème, ajuste le solveur pour qu'il agisse de manière intelligente, puis laissez-le s'exécuter. Cela signifie que toute la réflexion que vous devrez faire sera consacrée à trouver un bon moyen de coder le problème, pas à concevoir un algorithme et à faire la programmation et le réglage. Voici une réponse partielle pour vous aider à démarrer.

Supposons que la taille de l'écran soit .$x_{max}\times y_{max}$

Pour chaque fenêtre, , vous aurez un ensemble de variables et des contraintesx i , y i , h i , w $W_i$$x_i, y_i, h_i, w_i$

• $x_i,y_i,h_i,w_i\ge 0$
• $x_i + w_i \le x_{max}$
• $y_i + h_i \le y_{max}$
• Peut-être aussi quelques contraintes sur la taille minimale des fenêtres, par exemple et ainsi de suite.$h_i\ge 100$
• Contraintes d'aspect: si le rapport d'aspect est de 3: 4, la contrainte pourrait être quelque chose comme , où est un petit terme d'erreur non nul pour permettre une non-perfection la taille des fenêtres, sinon vous imposeriez une contrainte excessive au problème.$4h_i - \epsilon \le 3 w_i \le 4 h_i + \epsilon$$\epsilon$

Vous devez maintenant prendre soin du chevauchement des fenêtres. Pour chaque paire de fenêtres, , où , vous générerez des contraintes comme les suivantes, qui capturent qu'aucun coin de n'apparaît dans . Pour , générer une contrainte:$W_i, W_j$$i\neq j$$W_j$$W_i$$(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)\}$

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

Les contraintes spécifiées jusqu'à présent ne décrivent que des fenêtres qui ne se chevauchent pas, qui ne débordent pas sur les côtés de l'écran, qui satisfont à certaines contraintes de taille minimales et qui préservent leur rapport hauteur / largeur.

Pour obtenir un bon ajustement, vous devez spécifier une métrique qui capture ce que signifie être une bonne mise en page. Une possibilité consiste à supposer que vous souhaitez conserver des fenêtres de taille à peu près égale et / ou que vous souhaitez minimiser les "espaces blancs". Je ne pense pas que cela puisse être spécifié en utilisant Choco, mais cela peut être possible avec une autre résolution de contrainte (quelqu'un d'autre pourrait être en mesure d'aider ici).

Choco permet de maximiser wrt à une fonction objective spécifiée comme une seule variable. Sur la base de cette idée, vous pouvez maximiser les éléments suivants:

• $\sum_i (h_i + w_i)$

en écrivant une contrainte et en disant à Choco de maximiser .c o s $\mathit{cost}=\sum_i (h_i + w_i)$$\mathit{cost}$

J'ai commencé à écrire un prototype pour une solution de force brute, qui, espérons-le, peut être optimisée au point où elle sera pratique.

Tout d'abord, quelques définitions: Soit l'ensemble de toutes les fenêtres. Chaque fenêtre est composée de pour les coordonnées x, y et la largeur et la hauteur. Une fenêtre est initialisée avec une largeur et une hauteur minimales.$W$$w$$x_w, y_w, w_w, h_w$

L'entrée de l'algorithme est l'écran, , qui a une largeur et une hauteur et une liste de fenêtres.$S$

Cela fonctionne à peu près ainsi:

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()

Il y a quelques choses qui devraient être améliorées:

• S.coordinates()est très lent en ce moment. Il itère tous les points S.width x S.heightet vérifie si chacun se trouve dans l'une des fenêtres de S.

• S.put()vérifie si son paramètre chevauche le reste des fenêtres de S en effectuant le test mentionné dans la réponse de Dave. Peut-être que cela peut être amélioré en utilisant des arbres d'intervalle ?

• S.score()renvoie actuellement qui est simplement l'aire de toutes les fenêtres. Il doit prendre en compte d'autres variables pour produire de meilleures dispositions.$\sum_{w \in S.windows} (h_w \cdot w_w)$

• La fonction ci-dessus doit essayer toutes les permutations de pour obtenir le meilleur résultat possible.$W$

J'essaie actuellement de trouver une structure de données appropriée pour représenter l'écran et ses fenêtres, il doit prendre en charge ces requêtes:

• renvoie une liste de coordonnées où une fenêtre donnée peut être positionnée sans se chevaucher avec d'autres
• insérer la fenêtre à la position x, y (déjà vérifié qu'elle ne se chevauche pas)
• retourner toutes les fenêtres