Unterschiedlich große Bilder optimal zu einem zusammenfassen

[jim_raynor]

Angenommen ich habe mehrere Bilder die unterschiedlich groß sein können. Ich suche jetzt einen Ansatz, wie ich diese ohne große Freiräume (also verschenkter Platz) auf ein großes Bild verteilen kann. Die größe soll dabei dynamisch ermittelt werden um sowenig Platz wie möglich zu verlieren.

Vereinfacht könnte man sagen, dass ich unterschiedlich viele Rechtecke auf einer möglichst kleinen Fläche unterbringen möchte.

Wozu das ganze: Für mein Projekt möchte ich die Grafiken für die Animationen optimieren, da mit festen Framegrößen doch sehr viel Arbeitsspeicher verloren geht, wenn nichtmal 20% des Bildes tatsächlich genutzt werden.

Also hat jemand vielleicht einen Ansatz um dieses Problem zu lösen.

[marabu]

Hallo Christian,

du hast da ein Optimierungsproblem, welches - schön für dich - geradezu ein Standardproblem des Operation Researchs ist. Du findest sicher massenhaft Hinweise, wenn du nach Rucksack-Problem bzw. -Algorithmus oder Zuschnitts-Problem suchst. Eventuell findest du eine Musterlösung auf der BWI Seite.
Letzten Endes ist es ein kombinatorisches Problem. Du hast eine Liste mit Bildern und ihren Abmessungen und eine zu optimierende Funktion (bounding rect von allen Bildern soll minimal sein). Du nimmst ein Bild und kombinierst es mit einem zweiten. Eine Ecke und eine Kante fallen aufeinander, mehrere Anordnungen sind denkbar. Die Gesamtfläche ist einfach zu berechnen, aber die Zahl der möglichen Anordnungen explodiert sehr schnell. Eventuell ist ein genetischer Algorithmus mit Zeitbeschränkung ein guter Ansatz.

Viel Spaß und Grüße vom marabu

[jim_raynor]

Hallo,

danke für deine Antwort, denn sie hat mir die Augen geöffnet. Da ich über 100 Bilder aufteilen wollte, ist mir klar geworden, dass es nicht mit vertretbaren Aufwand realisierbar ist. Hab jetzt eine recht einfache Lösung genommen.

Und zwar sortiere ich die Bilder der Höhe nach so dass ich innerhalb einer Bilderreihe nicht zu viel Platz verschenke. Durch einen Parameter wird angegeben wieviele Bilder in der ersten Reihe seien sollen. Dadurch ergibt sich die Breite des Bildes. Alle weiteren Reihen werden dann aufgefüllt, solange bis ein Bild nicht mehr in die Reihe passt. Da dadurch eventuell am Ende viel Platz verschenkt wird, kann man die Anzahl in der ersten Reihe sehr einfach ändern um so die optimale Anzahl zu finden. Ich hab mal ein Bild als Anhang angefügt, die das Ergebnis präsentiert.

Vorher hatte diese Grafik eine Größe von 1680x960. Jetzt nur 603x591. Sollte erstmal für den Anfang reichen