Algorithmus gesucht

Beginner

Tuesday, January 11th 2011, 12:37am

Algorithmus gesucht

Hallo,
mich beschäftigt momentan folgendes Problem:

Gegeben habe ich mehrere Rechtecke. Diese Rechtecke sollen in ein variables großes Rechteck eingeschrieben werden. (Die Fläche sollte aber ausgefüllt sein dH die kleinen Rechtecke sollen über den Rand hinaus gehen.)
Ich suche momentan einen Algorithmus der nicht stumpf die rechtecke aneinanderreiht, sondern diese zuerst analysiert und geeignete kleine Rechtecke auswählt, um möglichst effektiv Löcher innerhalb des Rechteckes zu vermeiden, diese Recktecke nicht zu weit
über den Rand hinaus gehen lässt und diese natürlich auch entsprechend positioniert.

Meine Frage nun:
Hat jemand eine Idee wie man dies am besten berechnen kann oder gibt es bereits irgendwelche Algorithmen, die man nutzen könnte?

n0x-f0x

Trainee

Posts: 50

Tuesday, January 11th 2011, 9:15am

Das simpelste zu programmieren aber auch das rechenintensivste wäre alle möglichen lösungen durchzuprobieren.

Rechtecke oder Quadrate?

Verbesserung zu alles durchprobieren währe nach zwei kleinen rechtecken zu suchen die zusammen ungefähr die seitenlänge eines großen haben.
So kann man sich immer neue Verbesserungen überlegen.

Oder glaubt ihr das Bubblesort an einem Tag erfunden wurde (bzw. der algorithmus dazu)?

Schreib erstmal ein programm das ähnliche rechtecke nebeneinander schiebt (kaum lücken) und mit den restlichen guckt, ob die ähnlich sind, wenn man 2 davon nimmt.
beachte das man rechtecke auch drehen kann und das du bei jedem schritt jede drehmöglichkeit beachtest!

Hoffe ich konnte helfen