AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Zuschnittsproblem

Ein Thema von Bjoerk · begonnen am 16. Dez 2011 · letzter Beitrag vom 17. Dez 2011
Antwort Antwort
Seite 1 von 2  1 2   
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#1

Zuschnittsproblem

  Alt 16. Dez 2011, 17:18
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..
  Mit Zitat antworten Zitat
Benutzerbild von Codewalker
Codewalker

Registriert seit: 18. Nov 2005
Ort: Ratingen
945 Beiträge
 
Delphi XE2 Professional
 
#2

AW: Zuschnittsproblem

  Alt 16. Dez 2011, 17:45
Klingt verdächtig nach dem Rucksackproblem: http://de.wikipedia.org/wiki/Rucksackproblem
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

Registriert seit: 20. Jan 2006
Ort: Lübbecke
9.846 Beiträge
 
Delphi 11 Alexandria
 
#3

AW: Zuschnittsproblem

  Alt 16. Dez 2011, 17:59
Klingt verdächtig nach dem Rucksackproblem: http://de.wikipedia.org/wiki/Rucksackproblem
Eher schon dieses: The Two Dimensional Cutting Stock Problem
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#4

AW: Zuschnittsproblem

  Alt 16. Dez 2011, 18:51
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 ??
  Mit Zitat antworten Zitat
Jens01

Registriert seit: 14. Apr 2009
654 Beiträge
 
#5

AW: Zuschnittsproblem

  Alt 16. Dez 2011, 20:22
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
Achtung: Bin kein Informatiker sondern komme vom Bau.

Geändert von Jens01 (16. Dez 2011 um 20:29 Uhr)
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#6

AW: Zuschnittsproblem

  Alt 16. Dez 2011, 20:57
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
function GetRest(Rest, FCurrent.First.Subtyp) sowas:

GetRest(Rest, FCurrent.First.Width, FCurrent.First.Height).
  Mit Zitat antworten Zitat
Jens01

Registriert seit: 14. Apr 2009
654 Beiträge
 
#7

AW: Zuschnittsproblem

  Alt 16. Dez 2011, 21:29
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
Achtung: Bin kein Informatiker sondern komme vom Bau.
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#8

AW: Zuschnittsproblem

  Alt 16. Dez 2011, 21:32
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.
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.289 Beiträge
 
Delphi 10.4 Sydney
 
#9

AW: Zuschnittsproblem

  Alt 16. Dez 2011, 23:21
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...
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#10

AW: Zuschnittsproblem

  Alt 17. Dez 2011, 00:04
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/
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 08:20 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf