Wie erstelle ich einen Algorithmus, um (veränderbare) Fenster auf dem Bildschirm so anzuordnen, dass so viel Platz wie möglich abgedeckt wird?

20

Ich möchte ein einfaches Programm schreiben, das eine Reihe von Fenstern (Breite + Höhe) und die Bildschirmauflösung akzeptiert und eine Anordnung dieser Fenster auf dem Bildschirm ausgibt, so dass die Fenster den größten Platz beanspruchen. Daher ist es möglich, die Größe eines Fensters unter Beibehaltung output size >= initial sizedes Seitenverhältnisses zu ändern . Also für Fenster , würde ich den Algorithmus wie ein Tupel zurück .( x , y , w i d t h , h e i g h t )i(x,y,width,height)

Ich glaube, dies könnte eine Variante von 2D Knapsack sein. Ich habe versucht, die Ergebnisse im Web durchzusehen, aber die meisten hatten viel Hintergrundwissen (und keine Implementierung), was es mir schwer machte, zu folgen.

Ich interessiere mich weniger für den schnellstmöglichen Algorithmus, sondern mehr für etwas, das für meine spezifischen Bedürfnisse praktisch ist.

daniel.jackson
quelle
1
Wenn Sie die Größe eines Fensters ändern, behalten Sie nicht die ursprüngliche Größe bei, sondern nur das Seitenverhältnis, nehme ich an.
Emre
1
Sie können die Größe eines Fensters ändern, um den Bildschirm zu verdecken. Wo liegt das Problem?
2
Ich bin Saeeds Kommentar gefolgt. Sie benötigen zusätzliche Einschränkungen wie minimale Größen, um die Summe der Größenänderungen zu minimieren, wenn Sie triviale Lösungen ausschließen möchten. Anmerkung: Mathematiker scheinen Kachelprobleme als Tessellationen zu bezeichnen .
Raphael
1
Vielleicht ist es besser zu sagen, Sie möchten die minimale sichtbare Fensterfläche maximieren und die maximale sichtbare Fensterfläche minimieren, aber Konflikte sind zulässig oder nicht? Bitte bearbeiten Sie Ihre Frage, um sie fehlerfrei zu machen. Das Nachdenken über die aktuelle Problemstellung ist nicht einfach.
2
WminwWsize(w)W

Antworten:

9

Obwohl Ihre Frage es nicht sagt, gehe ich davon aus, dass Sie nicht möchten, dass sich Fenster überlappen.

Ein Ansatz für dieses Problem ist die Verwendung eines Constraint-Lösers wie Choco . Man schreibt einfach die Einschränkungen auf, die Ihr Problem codieren, stimmt den Löser so ab, dass er intelligent agiert, und lässt ihn dann laufen. Dies bedeutet, dass Sie nur überlegen müssen, wie Sie das Problem gut codieren können, statt einen Algorithmus zu entwickeln und die Programmierung und Abstimmung vorzunehmen. Hier ist eine Teilantwort, um Ihnen den Einstieg zu erleichtern.

Angenommen, die Bildschirmgröße ist .xmax×ymax

Für jedes Fenster haben Sie eine Reihe von Variablen und Einschränkungenx i , y i , h i , w iWixi,yi,hi,wi

  • xi,yi,hi,wi0
  • xi+wixmax
  • yi+hiymax
  • Möglicherweise gibt es auch einige Einschränkungen für die minimale Größe von Fenstern, z. B. und so weiter.hi100
  • Aspektbeschränkungen: Wenn das Seitenverhältnis 3: 4 beträgt, könnte die Beschränkung etwa , wobei ein kleiner Nicht-Null-Fehlerbegriff ist, um Nicht-Perfektes zuzulassen Fenstergrößen, da Sie sonst das Problem übermäßig einschränken würden.& egr;4hiϵ3wi4hi+ϵϵ

Nun müssen Sie auf die Fensterüberlappung achten. Für jedes Fensterpaar , in dem , generieren Sie Einschränkungen wie die folgenden, die erfassen, dass in keine Ecke von erscheint . für die Einschränkung: i j W j W i ( x , y ) { ( x j , y j ) , ( x j + w j , y j ) , ( x j , y j + h j ) , ( x j + w j , y j + h jWi,WjijWjWi(x,y){(xj,yj),(xj+wj,yj),(xj,yj+hj),(xj+wj,yj+hj)}

  • ¬(xixxi+wjyiyyi+hj) .

Die bisher angegebenen Einschränkungen beschreiben nur nicht überlappende Fenster, die nicht über die Seiten des Bildschirms verlaufen, die einige minimale Größenbeschränkungen erfüllen und deren Seitenverhältnis beibehalten.

Um eine gute Anpassung zu erhalten, müssen Sie eine Metrik angeben, die erfasst, was es heißt, ein gutes Layout zu sein. Eine Möglichkeit besteht darin anzunehmen, dass Sie die Fenster ungefähr gleich groß halten und / oder den "Leerraum" minimieren möchten. Ich glaube nicht, dass dies mit Choco spezifiziert werden kann, aber es kann mit einer anderen Einschränkung gelöst werden (jemand anderes könnte hier helfen).

Mit Choco kann man die Anzahl auf eine Zielfunktion maximieren, die als einzelne Variable angegeben ist. Basierend auf dieser Idee können Sie Folgendes maximieren:

  • i(hi+wi)

indem Sie eine Bedingung und Choco , zu maximieren .c o s tcost=i(hi+wi)cost

Dave Clarke
quelle
Das sieht vielversprechend aus und ich werde auf jeden Fall mit Choco spielen, um zu sehen, wie das funktioniert und wie schnell es geht.
Daniel Jackson
Aber warum sollte man das überhaupt so ausdrücken? Ich denke, Sie können die Einschränkungen als lineare Ungleichungen ausdrücken, was bedeutet, dass Sie ein lineares Vanille-Programm haben.
Suresh
@ Suresh: Fühlen Sie sich frei zu erarbeiten. Ich verstehe nicht sofort, wie es geht.
Dave Clarke
1

Ich habe angefangen, einen Prototyp für eine Brute-Force-Lösung zu schreiben, der hoffentlich so weit optimiert werden kann, dass er praktisch ist.

Zunächst einige Definitionen: Sei die Menge aller Fenster. Jedes Fenster setzt sich aus für die x-, y-Koordinaten und die Breite und Höhe zusammen. Ein Fenster wird mit einer minimalen Breite und Höhe initialisiert.w x w , y w , w w , h wWwxw,yw,ww,hw

Die Eingabe des Algorithmus ist der Bildschirm , der eine Breite und Höhe und eine Liste von Fenstern aufweist.S

Es funktioniert ungefähr 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()

Es gibt einige Dinge, die verbessert werden sollten:

  • S.coordinates()ist gerade sehr langsam. Es iteriert alle Punkte S.width x S.heightund prüft, ob sich jeder in einem der Fenster von S befindet.

  • S.put()prüft, ob sich sein Parameter mit den übrigen Fenstern von S überschneidet, indem der in Daves Antwort erwähnte Test durchgeführt wird. Vielleicht kann dies durch die Verwendung von Intervallbäumen verbessert werden ?

  • S.score()Derzeit wird was einfach der Bereich aller Fenster ist. Es muss andere Variablen berücksichtigen, um bessere Layouts zu erstellen.wS.wichndOws(hwww)

  • Die obige Funktion muss alle Permutationen von ausprobieren , um das bestmögliche Ergebnis zu erzielen.W

Ich versuche gerade, eine geeignete Datenstruktur zu finden, um den Bildschirm und seine Fenster darzustellen. Diese Abfragen müssen unterstützt werden:

  • Gibt eine Liste von Koordinaten zurück, in denen ein bestimmtes Fenster positioniert werden kann, ohne sich mit anderen zu überschneiden
  • Fenster an Position x, y einfügen (bereits überprüft, dass es nicht überlappt)
  • kehre zu allen Fenstern zurück
daniel.jackson
quelle