Suche Ideen zur Realisierung

CChrissi

Hallo,

Ich suche nach einer Möglichkeit dieses Problem zu implementieren:
Ich will einen Quader in einem größeren Quader anordnen, und zwar genau so, dass er eine Seite möglichst maximal ausfüllt. Also z.b. wenn ich einen großen Quader der Abmessungen (30,20,10) habe und einen kleinen mit (18, 10, 5). Dann soll dieser an die Wand mit größe 20 gestellt werden mit 10 Breite und in x-Richtung dann die 5.

Irgendwie weiss ich nur leider überhaupt nicht, wie ich da ran gehen könnte.

Falls irgendjemand eine Idee hat, wäre ich wirklich sehr dankbar.

Vielen Dank und liebe Grüße,
Chrissi

Hi

Hört sich für mich nach Optimierung an und ist somit ein fall für die KI ( suchbäume)

den programm stellt wahl los die kisten in den raum und kontrolliert dann nach jedem reinsetzen ob das effektif war schrott. problem ist das du verdamt viele möglichkeiten hast eine neue kiste in dem raum zu positionieren. (je grösser desto mehr) 3 ausrichtungen an n positionen. dadurch wird der ansatz fast nicht mehr tragbar ( wer wartet 3 tage auf eine lösung ) . ggf kann man aber bei der setzrotine etwas manipolieren. nächter punkt wie sieht eine brauchbare bewertungsfunktion aus.

Ok es ging vileicht auch einfacher und schneller.

gruss Termite

ups übersehen das du nur die seitenaufüllung wissen wolltest nicht die anzahl der maximal enthaltenen kisten. Vereinfacht die sache ein bischen. geht aber im prinzip nach dem gleichen schema

CChrissi

Danke für die Antwort, dass das ganze Problem ziemlich schwierig ist, ist mir bekannt. Bin ich gerade am arbeiten daran. Und versuche daher diese maximale Seitenausfüllung als Bewertungsfunktion herzunehmen. Da es ja immer nur um einen Quader in einen größeren geht, dürfte das ganze nicht mehr ganz so kompliziert sein. Ich habs schonmal über die Seitenflächen versucht, aber irgendwie tut er noch nicht so ganz, was ich will.

hiermal der c++ code, falls es jemanden interessiert:

Box positionDist(Box box1, Box space)
{
    Box temp(-1, -1, -1, -1, -1, -1);
    int squareSpace1, squareSpace2, squareSpace3, squareBox1, squareBox2, squareBox3;

    squareSpace1 = space.Length * space.Width;
    squareSpace2 = space.Length * space.Height;
    squareSpace3 = space.Height * space.Width;
    squareBox1   = box1.Length  * box1.Width;
    squareBox2   = box1.Length  * box1.Height;
    squareBox3   = box1.Height  * box1.Width;

    if ((max(max(squareBox1, squareBox2), squareBox3) <= min(min(squareSpace1, squareSpace2), squareSpace3)))
    {
        if (min(min(squareSpace1, squareSpace2), squareSpace3) == squareSpace1)
        {
             temp.Height = box1.minDim();
             if (min(squareSpace2, squareSpace3) == squareSpace2)
             {
                  temp.Length = box1.maxDim();
                  temp.Width  = box1.medDim();
             }
             else
             {
                  temp.Length = box1.medDim();
                  temp.Width  = box1.maxDim();
             }
        }
        else if (min(min(squareSpace1, squareSpace2), squareSpace3) == squareSpace2)
             {
                 temp.Width = box1.minDim();
                 if (min(squareSpace1, squareSpace3) == squareSpace1)
                 {
                     temp.Length = box1.maxDim();
                     temp.Height = box1.medDim();
                 }
                 else
                 {
                     temp.Length = box1.medDim();
                     temp.Height = box1.maxDim();
                 }
             }
             else
             {
                 temp.Height = box1.minDim();
                 if (min(squareSpace1, squareSpace2) == squareSpace1)
                 {
                     temp.Length = box1.maxDim();
                     temp.Width  = box1.medDim();
                 }
                 else
                 {
                     temp.Length = box1.medDim();
                     temp.Width = box1.maxDim();
                 }
             }
    }
    else if (max(max(squareBox1, squareBox2), squareBox3) <= med(squareSpace1, squareSpace2, squareSpace3))
         {
              if (med(squareSpace1, squareSpace2, squareSpace3) == squareSpace1)
              {
                  temp.Height = box1.minDim();
                  if (min(squareSpace2, squareSpace3) == squareSpace2)
                  {
                      temp.Length = box1.maxDim();
                      temp.Width  = box1.medDim();
                  }
                  else
                  {
                      temp.Length = box1.medDim();
                      temp.Width  = box1.maxDim();
                  }
              }
              else if (med(squareSpace1, squareSpace2, squareSpace3) == squareSpace2)
                   {
                       temp.Width = box1.minDim();
                       if (min(squareSpace1, squareSpace3) == squareSpace1)
                       {
                           temp.Length = box1.maxDim();
                           temp.Height = box1.medDim();
                       }
                       else
                       {
                           temp.Length = box1.medDim();
                           temp.Height = box1.maxDim();
                       }
                   }
                   else
                   {
                       temp.Height = box1.minDim();
                       if (min(squareSpace1, squareSpace2) == squareSpace1)
                       {
                           temp.Length = box1.maxDim();
                           temp.Width  = box1.medDim();
                       }
                       else
                       {
                           temp.Length = box1.medDim();
                           temp.Width = box1.maxDim();
                       }
                   }
         }
         else
         {
              if (med(squareSpace1, squareSpace2, squareSpace3) == squareSpace1)
              {
                  temp.Height = box1.minDim();
                  if (min(squareSpace2, squareSpace3) == squareSpace2)
                  {
                      temp.Length = box1.maxDim();
                      temp.Width  = box1.medDim();
                  }
                  else
                  {
                      temp.Length = box1.medDim();
                      temp.Width  = box1.maxDim();
                  }
              }
              else if (med(squareSpace1, squareSpace2, squareSpace3) == squareSpace2)
                   {
                       temp.Width = box1.minDim();
                       if (min(squareSpace1, squareSpace3) == squareSpace1)
                       {
                           temp.Length = box1.maxDim();
                           temp.Height = box1.medDim();
                       }
                       else
                       {
                           temp.Length = box1.medDim();
                           temp.Height = box1.maxDim();
                       }
                   }
                   else
                   {
                       temp.Height = box1.minDim();
                       if (min(squareSpace1, squareSpace2) == squareSpace1)
                       {
                           temp.Length = box1.maxDim();
                           temp.Width  = box1.medDim();
                       }
                       else
                       {
                           temp.Length = box1.medDim();
                           temp.Width = box1.maxDim();
                       }
                   }
         }
    temp.xPos = space.xPos;
    temp.yPos = space.yPos;
    temp.zPos = space.zPos;
    return temp;
}

Das Problem ist, er baut den kleinen Quader irgendwie auch über die Grenzen den großen Quaders hinein.

sieht irgendwer den Fehler?

Lg,
Chrissi

Hi

vileicht hilft es das Problem erst mal 2 Dimensional zu betrachten
Anstelle eines raumes füllst du ein fläche mit 3 verschiedenen rechtecken ( z.b. die seitenflächen des quaders ab, bc, ac) die erweiterung zu 3d ergeben sich dann dadurch, das quader an der flächenkante auswirkungen auf andere flächen haben, und gewisse quader nicht plaziert werden können, da ander im weg sind. 2d kann man auch mal auf papier durchspielen um zu schauen wie du das machst. um dan zu versuchen das verhalten in einen alg zu implementieren

Die Seitenausfüllung als bewertung ist eigentlich ganz gut. nur ist das eine gültige bewertung für einen voll ausgefüllten quader. Vileicht lässt sich noch die Fragmentierung der fläche mit in die bewertung mit einbeziehen.

Auserdem weis ich nicht in welchen werten du bei den Grösen rechnest. sind das ganzzahl Werte (7einheiten auf 3einheiten auf 9) oder Kommazahlen. bei ganz zahlen liese sich fileicht ein bittfeld verwenden in dem markiert wird welche FLächeneinheit bzw raumeinheit bereits belegt ist.

hab den code leider nicht angeschaut. darf mich grad selber durch mehrere duzend quelldateien lesen.

gruss Termite

CChrissi

Hallo Termite,

das mit dem zweidimensional ist gar nicht so schlecht, aber da ist es irgendwie ganz einfach. Wenn ich großes Rechteck (L, und kleines (l,b)
dann frag ich einfach :
max(l,b)<min(L,B) ?
ja: dann pack ichs so rein, dass max(l,b) auf min(L,B) liegt
nein: dann andersrum

nur im dreidimensionalen ist das irgendwie trickreicher. Ich habe es wie gesagt mit den Seitenflächen probiert und eben gefragt
max(l*b, l*h, b*h) <= min ( L*B, L*H, B*H),
wenn ja, kann mans wieder so packen, dass die entsprechenden Seitenflächen aufeinanderliegen.
Dass Problem ist nur, dass es passieren kann, dass es flächenmäßig zwar passen würde, aber die Abmessungen trotzdem zu groß sind. Ich könnte das natürlich jedes mal wieder abfragen, aber ich denke es gibt sicherlich eine bessere Lösung.
Nur wie das ist die Frage?

Lg,
Chrissi