Flächenunterteilung

[FinalFantasy]

Hi,

wo mir im Moment langweilig ist, ist mir ein altes Problem eingefallen, welches ich bis jetzt noch nicht lösen konnte:

Man geht mal davon aus, dass man eine Glasplatte mit 3x2m Grösse hat. Jetzt will ich aus dieser Glasplatte kleiner Teilflächen in unterschiedlichen Grössen herrausschneiden, wobei ich nur immer gerade Schnitte durch die ganze Platte machen kann.

Ich wollte mir jetzt ein Programm schreiben, dass mir alle möglichen Anordnungen der kleineren Teilplatten, auf der grossen Platte angibt. Am besten noch grafisch aufgezeichnet.

Leider hab ich nichtmal einen funktionierenden Ansatz zur Problemlösung gefunden.

Ich bin nur zu dem Schluss gekommen, dass es wohl Rekursiv am einfachsten zu Lösen wäre, wobei die Rekursion öfter durchlaufen muss, da ich die Teile ja in unterschiedlicher Reihenfolge ausschneiden könnte.

Zudem muss ich mir die ganzen Positionen der Teilplatten merken, um am Schluss die Lösungen zeichnen zu können.

Ich will das ganze am besten in C++/MFC machen, aber im Prinzip geht es ja hier nur um den Algorithmus.

Jemand ne Idee, wie man das lösen kann?

[M.A.Knapp]

Dazu eigenen sich Branch&Bound und/oder Backtracking Methoden. Solche Zuschnittprobleme werden in der Regel als 2-Dimensionales "Bin-Packing" Problem behandelt. (nach "Bin-Packing" in Google suchen)

Es gibt sogar eine Diplomarbeit über Zuschnitt-Probleme,

mit Schwerpunkt Glaszuschnitt:

http://www.informatik.uni-osnabrueck.de/prakt/pers/dipl/doc/andy/diplom.ps

MfG, Michael