Optimierung von Flächen

[CptK]

Hallo,
ich habe 5 Flächen mit unterschiedlichen Maßen, die zu einer möglichst kleinen Fläche zusammen geschlossen werden sollen. Mein Problem ist jetzt, dass ich ein bisschen auf dem Schlauch stehe, was das logische Denken angeht. Ich finde leider keinen richtigen Ansatz, wie ich an dieses Problem herangehen soll und würde mich deshalb freuen, wenn mir jemand helfen könnte.

 

[MoxxiManagarm]

• Was sind das für Flächen? Sind es alles Rechtecke?
• Was heißt zusammengeschlossen? Ist es das kleinste Rechteck, dass alle Flächen umschließt?

Angenommen es ist das kleinste Rechteck, was alle anderen Flächen umschließt....

Dann musst du 4 Punkte finden, welche jeweils ein Minimum bzw. Maximum darstellen:

• Der östlichste Punkt von allen östlichsten Punkten einer Fläche (xo/yo)
• Der nördlichste Punkt von allen nördlichsten Punkten einer Fläche (xn/yn)
• Der westlichste Punkt von allen westlichsten Punkten einer Fläche (xw/yw)
• Der südlichste Punkt von allen südlichsten Punkten einer Fläche (xs/ys)

Daraus kannst du dir die Eckpunkte des Rechteckes zusammenfügen
(xw, yn) (xw, ys) (xo, ys) (xo, yn)



Wobei beispielsweise bei einem Kreis der Nordpunkt wäre: (x_center, y_center + radius)

 

[CptK]

Also es handelt sich um Rechtecke mit beispielsweise den Maßen 4 x 4, 2 x 3, 6 x 1, 5 x 2, 3 x 5. Diese sollen so angeordnet werden, dass das Rechteck ,das alle umschließt möglichst klein ist, Flächen sollen aber nicht gedreht werden.

 

[MoxxiManagarm]

Siehst du, es kam in deinem initialen Beitrag nicht heraus, dass die Flächen umgelegt werden müssen. Bitte immer die Aufgabe korrekt formulieren

Versuch dir doch mal die 5 Rechtecke zusammenzuschneiden aus Papier, wie würdest du vorgehen wenn du es per Hand machen würdest? Ich würde tendenziell mit dem Größten anfangen...
Entweder mit dem Flächengrößten (4x4)
Oder mit einem Seitengrößten (6x1 bzw 3x5)

 

[CptK]

AAAABBB
AAAABBBD
AAAA..EED
AAAA..EED
CCCCCEED
CCCCCEED
CCCCCEED

So würde das bei mir aussehen(Punkte sind nur Platzhalter). Ich schaue welche Flächen zusammen gleiche Längen haben, aber ich habe keine Ahnung wie ich das mathematisch richtig ausdrücken soll.

 

[Xyz1]

Das Problem ist nicht trivial und aktueller forschungsgegenstand.

 

[MoxxiManagarm]

Ändert nichts daran dass man Heuristiken anwenden kann. Möglichst kleines rechteck ist nicht zwangsläufig das kleinste. Genauso wie beim Rundreisenden.

 

[CptK]

Okay könnte mir trotzdem jemand einen Denkanstoß geben wie ich dem Computer sagen kann, dass er das machen soll, ich meine ich habe mir die Aufgabe ja nicht selber ausgedacht, also muss sie ja irgendwie zu lösen sein

 

[MoxxiManagarm]

Wie gesagt Versuch mit einer heuristik, denke daran wie du dir die rechtecke zusammengeschoben hast. Du kannst das dem Computer auf viele weißen sagen das kommt daran an wie dein Input, deine datanhaltung und dein output aussieht.

Im einfachsten Fall hast du vermutlich nur ein Array dass du mit Zeichen befüllst so wie in deinem Beispiel.

 

[CptK]

Ich kriege das nicht hin xD. Ich habe jetzt versucht alle Seiten a und alle Seiten b zusammenzurechen und so die gemeinsamen Größen zu finden, das klappt auch, ich weiß nur nicht, wie ich diese jetzt sinnvoll zusammensetzen kann. Außerdem gibt es mehrere Größen die vier Flächen gleich haben und ich weiß nicht wie ich weiter machen soll.