Zuschnittsproblem

[Bjoerk]

Hat jemand eine Idee für einen Algorithmus, um zu prüfen, ob ein Rechteck in ein anderes Rechteck noch hinein passt, in dem sich mehrere solcher schon befinden.

Beispiel

Anders ausgedrückt, wieviel Kisten unterschiedlicher Abmessungen passen in einen Container..

[Codewalker]

Klingt verdächtig nach dem Rucksackproblem: http://de.wikipedia.org/wiki/Rucksackproblem

[Uwe Raabe]

Zitat:

Zitat von Codewalker (Beitrag 1141814)

Klingt verdächtig nach dem Rucksackproblem: http://de.wikipedia.org/wiki/Rucksackproblem

Eher schon dieses: The Two Dimensional Cutting Stock Problem

[Bjoerk]

Zitat:

Zitat von Uwe Raabe (Beitrag 1141816)

Zitat:

Zitat von Codewalker (Beitrag 1141814)

Klingt verdächtig nach dem Rucksackproblem: http://de.wikipedia.org/wiki/Rucksackproblem

Eher schon dieses: The Two Dimensional Cutting Stock Problem

For solving the given two dimensional cutting stock problem of the flat glass industry an iterative algorithm is developed based on the following idea: In every iteration step some rectangles are paired by a maximum weight matching and the matched pairs are considered as new, larger rectangles, so called meta rectangles. In the following iteration steps these meta rectangles are treated in the same way as ordinary rectangles. The iterative matching automatically takes care of the guillotine structure. The iteration stops if the constructed meta rectangles are traverses. These traverses will be assigned to the stock sheets by a first fit decreasing algorithm. In every iteration step all possible alignments of demand and meta rectangles are considered by making use of shape functions.

Und was heißt das ?? :cyclops::gruebel:

[Jens01]

Werter Kollege,
ich habe auch schon mal nach solch einer Lösung gesucht. Aber mehr aus Interesse.
In meiner Studienzeit habe ich mal eine 1-dimensionale Optimierung programmiert, um KVH-Stangen zu optimieren.
Das 2-dimensionale Problem ist etwas schwieriger. Es gibt aber einige Anbieter im Netz, die für dies Problem Programmkomponenten anbieten.
Gruss Jens

Das ist ein Beispiel

[Bjoerk]

Zitat:

Zitat von Jens01 (Beitrag 1141831)

Werter Kollege,
ich habe auch schon mal nach solch einer Lösung gesucht. Aber mehr aus Interesse.
In meiner Studienzeit habe ich mal eine 1-dimensionale Optimierung programmiert, um KVH-Stangen zu optimieren.
Das 2-dimensionale Problem ist etwas schwieriger. Es gibt aber einige Anbieter im Netz, die für dies Problem Programmkomponenten anbieten.
Gruss Jens

Das ist ein Beispiel

Hallo Jens, ich hab' so ein Programm auch bereits, das teilt allerdings die Mattenpositionen in
gewisse Typen ein und errechnet so den verbleiben Rest.

Delphi-Quellcode:

procedure TForm1.BuildCurrentResult(CurrentTyp: integer);
var
  Rest: integer;
  Item: TMattenResultItem;
begin
  FCurrent.SortBySubtyp; // Vorsortierung
  FCurrentResult.Clear;
  while FCurrent.Count > 0 do
  begin
    Rest:= 1; // Ganze Matte Platz am Anfang
    Item:= ClearMattenResultItem;
    Item.Typ:= CurrentTyp;
    Item.GVerschnitt:= FCurrent.First.GG;
    while Rest <> 0 do // kommt in eine Matte
    begin
      SetCurrentItem(Rest); // Größte Position auf Index Null tauschen
      if GetRest(Rest, FCurrent.First.Subtyp) then // **********
      begin
        Inc(Item.SubtypCount);
        Item.Subtyp[Item.SubtypCount-1]:= FCurrent.First.Subtyp;
        Item.Pos[Item.SubtypCount-1]:= FCurrent.First.Pos;
        Item.GVerschnitt:= Item.GVerschnitt-FCurrent.First.G;
        FCurrent.DelFirst;
        if FCurrent.Count = 0 then Rest:= 0; // Break, alle Positionen abgearbeitet
      end
      else
        Rest:= 0; // Break, diese Postion dann in eine neue Matte
    end;
    FCurrentResult.AddItem(Item);
  end;
end;

Nun wollte ich das ganze etwas allgemeiner halten,
sozusagen für alle möglichen Abmessungen,

also eine statt einer

Delphi-Quellcode:

function GetRest(Rest, FCurrent.First.Subtyp)

sowas:

Delphi-Quellcode:

GetRest(Rest, FCurrent.First.Width, FCurrent.First.Height).

[Jens01]

Also mein Code war etwas umfangreicher. Die einzelnen Hölzer wurden erst nach Länge (lang->kurz) sortiert und dann nacheinander probiert, ob sie in die Stange rein passt. Das ergab gute Ergebnisse.
Ich glaube aber, dass die 2.Dimension mehr Aufwand erfordert.

.. eben noch mal bei MB geguckt. Dort gibt es aber bei dem Einpassen auch eine Vereinfachung. Die sortieren vor und fangen mit der größten an. Die legen auch erst die längste Matte drauf. Seitlich daneben legen sie immer eine, die gleich lang oder kürzer ist.

Hier ein Beispiel aus dem Holzbau

[Bjoerk]

Zitat:

Zitat von Jens01 (Beitrag 1141846)

Also mein Code war etwas umfangreicher. Die einzelnen Hölzer wurden erst nach Länge (lang->kurz) sortiert und dann nacheinander probiert, ob sie in die Stange rein passt. Das ergab gute Ergebnisse.
Ich glaube aber, dass die 2.Dimension mehr Aufwand erfordert.

.. eben noch mal bei MB geguckt. Dort gibt es aber bei dem Einpassen auch eine Vereinfachung. Die sortieren vor und fangen mit der größten an. Die legen auch erst die längste Matte drauf. Seitlich daneben legen sie immer eine, die gleich lang oder kürzer ist.

Hier ein Beispiel aus dem Holzbau

Dann machen die (MB) das genau so wie ich. Dann lasse ich‘s so.

[stahli]

Ich habe das mal in meiner http://www.delphipraxis.net/165177-s...ml#post1141861 mit Rechtecken realisiert.
Vielleicht findest Du da ja noch eine Anregung...

[Bjoerk]

Zitat:

Zitat von stahli (Beitrag 1141862)

Ich habe das mal in meiner http://www.delphipraxis.net/165177-s...ml#post1141861 mit Rechtecken realisiert.
Vielleicht findest Du da ja noch eine Anregung...

Hallo Stahli,

danke für deinen Link.

Auch damit wird’s eigentlich zum Kinderspiel:

http://www.delphi-treff.de/tipps/gra...e-kollidieren/