Ordnen Sie rechteckige UI-Objekte auf eine abstrakte Weise ohne Lücken programmatisch an
Wie wäre es angesichts einer Sammlung von etwa 50 Bildern mit verschiedenen Breiten und Höhen, sie programmatisch auf eine interessante * abstrakte Weise zu arrangieren? (siehe Bild unten)
- Mit interessant meine ich, keine großen Lücken und keine leicht unterscheidbaren Reihen oder Spalten (der negative Raum bildet viele T-ähnliche Schnittpunkte).
Für meinen speziellen Fall haben alle Bilder eine maximale Größe von 150px, was bedeuten könnte, dass die Höhe ODER Breite maximal 150px beträgt (könnte 150px mal 450px oder 378px mal 150px sein).
Es scheint, als könnte es eine klassische Programmierherausforderung sein, aber ich finde das Thema schwer zu Google ...
BEARBEITEN: Geändertes Bild, um zu zeigen, dass es keine Einschränkung gibt, wie die Gesamtanordnung sein muss (muss nicht in einen festgelegten Bereich passen)
3 Antworten
Ihr Problem ist NP-Hard .
Dieser Thread zeigt, dass es sogar mit einem Typ von nXm-Rechtecken ist ist NP-Schwer zu finden, wenn es eine Lösung gibt, also ist Ihr verallgemeinertes Problem natürlich auch NP-Hard [Die einzige Art von Rechteck ist ein Privatfall dieses Problems]
Sie können eine Backtracking -Lösung ausprobieren, wenn Sie nach einer optimierten Lösung suchen, oder einen heuristischen Ansatz wie genetische Algorithmen oder Bergsteigen , das wird schneller sein - aber wird normalerweise ein nicht optimales Ergebnis finden.
Wenn Sie nicht gegen das jquery-Plugin sind, können Sie dies überprüfen - Ссылка
Ich habe etwas ähnliches gebaut (obwohl es wahrscheinlich nicht die ausgeklügeltste Lösung ist). Mein Ansatz war, einen Quadtree zu verwenden, um die Rechtecke zu organisieren, die ich auf der Leinwand platziert hatte. Ich bin dann im Prinzip nur spiralförmig um den Mittelpunkt herumgegangen, habe versucht, neue Rechtecke zu platzieren und mit dem Quadtree Kollisionen zu erkennen. Wenn ich eine Kollision feststellen würde, würde ich das Rechteck, das ich versuchte, an den Rand des Rechtecks verschieben, mit dem es kollidiert ist, das am weitesten von der Mitte entfernt ist, und den Kollisionsüberprüfungsprozess wiederholen.
Auch hier ist es wahrscheinlich nicht die ausgeklügeltste Methode, und es neigt dazu, größere Lücken zwischen den Rechtecken zu hinterlassen (die Grenzen zwischen ihnen sind nicht einheitlich), aber nach meinem Geschmack hat es gute Ergebnisse erzielt.
Tags und Links algorithm user-interface layout image-processing