Anzahl möglicher Rechtecke auf Fläche ermitteln

Question

Hallo,

ich suche eine Beschreibung für die Vorgehensweise, wenn ich berechnen möchte, wieviele Rechtecke auf eine beliebige quadratische oder rechteckige Fläche passen. Konkret geht es darum, die mögliche Anzahl von Kisten (auch um 90 Grad gedreht) auf einer Europalette zu ermitteln. Ziel soll sein, die Größe einer Kiste sowie die Größe der Palette anzugeben und eine Liste mit der Anzahl der Kisten und deren Koordinaten zurückzubekommen. Hab schon nach Bin Packing gegoogled, aber leider nichts für mich verständliches gefunden, was die grundlegende Herangehensweise an das Problem beschreibt.

Hat jemand von Euch einen Tip, einen Link oder ein Snippet?

Für Eure Hilfe dankend,

Klaus

---

No Brain - No Pain

Answer 1

Hallo Klaus,

hier einmal ein Beispiel:

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;

namespace WinPassendeRechtecke
{
  public partial class Form1 : Form
  {
    public Form1()
    {
      InitializeComponent();
      this.Shown += Form1_Shown;
    }

    void Form1_Shown(object sender, EventArgs e)
    {
      Rectangle kiste = new Rectangle(0, 0, 50, 30);
      Rectangle palette = ClientRectangle;
      List<Point> positionen = PassendeRechtecke(kiste, palette);
      ZeichneRechtecke(positionen, kiste);
    }

    private List<Point> PassendeRechtecke(Rectangle einzelRec, Rectangle gesamtRec)
    {
      List<Point> punkte = new List<Point>();
      int horizontaleAnzahl = gesamtRec.Width / einzelRec.Width;
      int vertikaleAnzahl = gesamtRec.Height / einzelRec.Height;
      for (int v = 0; v < vertikaleAnzahl; v++)
        for (int h = 0; h < horizontaleAnzahl; h++)
          punkte.Add(new Point(h * einzelRec.Width, v * einzelRec.Height));
      return punkte;
    }

    private void ZeichneRechtecke(List<Point> positionen, Rectangle einzelRec)
    {
      Graphics g = CreateGraphics();
      foreach (var pos in positionen)
        g.DrawRectangle(Pens.Blue,
          pos.X, pos.Y, einzelRec.Width, einzelRec.Height);
      g.Dispose();
    }
  }
}

Answer 2

Hallo Frank,

vielen Dank für Deinen Tipp. Vom Prinzip her funktioniert das auch, solange die zu packenden Kisten  in ihrer Breite oder Länge einem optimalen Teiler des Palettenmaßes entsprechen. Das Problem tritt ja erst auf, wenn z.B. die erste Reihe auf der Palette aus 2 längs- und einer quer angeordneten Kiste bestehen müsste, um die optimale Packdichte zu erreichen. Dies liesse sich zwar für die Breite und Länge der Palette berechnen, beide Ergebnisse passen allerdings, in Abhängigkeit vom Kistenmaß, nicht immer im gesamten Packmuster zusammen. Und an dieser Stelle komme ich nicht weiter... :(

Schöne Grüße & Thx 4 Help,

Klaus

 

---

No Brain - No Pain

Answer 3

Hier schon mal ein paar Algoritmen dazu:

[Survey for 2-D packing algorithms]
http://www.csc.liv.ac.uk/~epa/surveyhtml.html

Normalerweise schafft man hier die Komplexität (Aufwand) O(n·log n).

Ansonsten auch C# Ansätze hier:

[C# Rectangle Packing | .NET Tips and Tricks]
http://kossovsky.net/index.php/2009/07/cshar-rectangle-packing/

---

ciao Frank

Answer 4

Hallo Frank,

vielen Dank für die Links!!! Ich denke, das ich mit diesen Informationen weiterkomme. Auch ohne Mathematik- und Informatikstudium ;)

Danke!! und schöne Grüße,

Klaus

---

No Brain - No Pain

Answer 5

Hallo,

für alle, die es interessiert anbei ein wenig Code, welchen ich direkt von

http://lagrange.ime.usp.br/~lobato/packing/#intro

aus C++ in C# übersetzt habe (C++ - Source steht unter GNU General Public License). Die u.s. Klasse beinhaltet allerdings nur den rekursiven Partitionierungsalgorithmus und kaum irgenderlei Optimierungen. Rückgabetyp ist eine List<Rectangle>, welche die zu zeichnenden Rechtecke enthält.

sG,

Klaus

---

No Brain - No Pain

 -----------------------------------------------------------------------------------------------------------------------------------------------

using System;
using System.Collections.Generic;
using System.Drawing;

namespace _PalletCalculator {
  internal class CutPoint {
    public int x1 {get; set;}
    public int x2 {get; set;}
    public int y1 {get; set;}
    public int y2 {get; set;}
    public int homogeneous {get;set;}
    public CutPoint(int _x1, int _x2, int _y1, int _y2, int _homogeneous) {
      x1 = _x1;
      x2 = _x2;
      y1 = _y1;
      y2 = _y2;
      homogeneous = _homogeneous;
    }
  }
  internal class Set {
    public int size {get; set;}
    public int[] points {get; set;}
  }
  class PalletCalculator {
    private int[][] lowerBound;
    private int[][] upperBound;
    private int[] indexX;
    private int[] indexY;
    private Set normalSetX = new Set();
    private int[] normalize;
    private int L;
    private int W;
    private int l;
    private int w;
    private static CutPoint[,] cutPoints;
    private const int HOMOGENEOUS = 0;
    private const int HORIZONTAL = 0;
    private const int VERTICAL = 1;
    private const int HORIZONTAL_CUT = 0;
    private const int VERTICAL_CUT = 1;
    private int N = 2000000000;
    private int[][] solutionDepth;
    private int[][] reachedLimit;
    private const int INFINITY_ = 2000000000;
    public List<Rectangle> Rectangles { get; set; }
    public PalletCalculator(int _PalletLength, int _PalletWidth, int _BoxLength, int _BoxWidth) {
      this.L = _PalletLength;
      this.W = _PalletWidth;
      this.l = _BoxLength;
      this.w = _BoxWidth;
      int[] q = new int[4];
      this.Rectangles = new List<Rectangle>();
      int BD_solution;
      int L_n;
      int W_n;
      BD_solution = solve_BD(L, W, l, w, 0);
      L_n = normalize[L];
      W_n = normalize[W];
      q[0] = q[2] = L_n;
      q[1] = q[3] = W_n;
      draw(q);
    }
    private void swap<T>(ref T value1, ref T value2) {
      var tmp = value1;
      value1 = value2;
      value2 = tmp;
    }
    private int insert(int element, Set set) {
      if (set.size == 0 || set.points[set.size - 1] < element) {
        set.points[set.size] = element;
        return set.size + 1;
      } else {
        return set.size;
      }
    }
    private Set newSet(int maxSize) {
      Set set = new Set();
      set.size = 0;
      set.points = new int[maxSize];
      return set;
    }
    private void constructRasterPoints(int L, int W, ref Set rasterPointsX, ref Set rasterPointsY, Set conicCombinations) {
      int x;
      int i;
      int xSize;
      int ySize;
      xSize = conicCombinations.size;
      for (i = xSize - 1; i >= 0 && conicCombinations.points[i] > L; i--)
        xSize--;
      ySize = conicCombinations.size;
      for (i = ySize - 1; i >= 0 && conicCombinations.points[i] > W; i--)
        ySize--;
      rasterPointsX = newSet(xSize + 2);
      rasterPointsY = newSet(ySize + 2);
      for (i = xSize - 1; i >= 0; i--) {
        x = normalize[L - conicCombinations.points[i]];
        rasterPointsX.size = insert(x, (rasterPointsX));
      }
      for (i = ySize - 1; i >= 0; i--) {
        x = normalize[W - conicCombinations.points[i]];
        rasterPointsY.size = insert(x, (rasterPointsY));
      }
    }
    private void constructConicCombinations(int L, int l, int w, ref Set X) {
      int[] inX = new int[L + 2];
      int[] c = new int[L + 2];
      X.points[0] = 0;
      X.size = 1;
      inX[0] = 1;
      for (int i = 0; i <= L; i++) {
        c[i] = 0;
      }
      for (int i = l; i <= L; i++) {
        if (c[i] < c[i - l] + l) {
          c[i] = c[i - l] + l;
        }
      }
      for (int i = w; i <= L; i++) {
        if (c[i] < c[i - w] + w) {
          c[i] = c[i - w] + w;
        }
      }
      for (int i = 1; i <= L; i++) {
        if (c[i] == i && inX[i] == 0) {
          X.points[X.size] = i;
          X.size++;
          inX[i] = 1;
        }
      }
      if (X.points[X.size - 1] != L) {
        X.points[X.size] = L;
        X.size++;
      }
    }
    private int localUpperBound(int iX, int iY) {
      if (solutionDepth[iX][iY] == -1) {
        return lowerBound[iX][iY];
      } else {
        return upperBound[iX][iY];
      }
    }
    private void storeCutPoint(int L, int W, int x1, int x2, int y1, int y2) {
      CutPoint c = new CutPoint(x1, x2, y1, y2, 0);
      cutPoints[indexX[L], indexY[W]] = c;
    }
    private int solve(int L, int W, int l, int w, int n, int numBlocks, int[] L_, int[] W_, ref int z_lb, int z_ub, int x1, int x2, int y1, int y2) {
      int[] z = new int[6];
      int S_lb;
      int S_ub;
      int[] iX = new int[6];
      int[] iY = new int[6];
      int[] zi_ub = new int[6];
      int[] zi_lb = new int[6];
      int i;
      for (i = 1; i <= numBlocks; i++) {
        L_[i] = normalize[L_[i]];
        W_[i] = normalize[W_[i]];
        if (L_[i] < W_[i]) {
          swap(ref L_[i], ref W_[i]);
        }
        iX[i] = indexX[L_[i]];
        iY[i] = indexY[W_[i]];
      }
      if (n < N) {
        S_lb = 0;
        S_ub = 0;
        for (i = 1; i <= numBlocks; i++) {
          zi_lb[i] = lowerBound[iX[i]][iY[i]];
          S_lb += zi_lb[i];
          zi_ub[i] = localUpperBound(iX[i], iY[i]);
          S_ub += zi_ub[i];
        }
        if (z_lb < S_ub) {
          for (i = 1; i <= numBlocks; i++) {
            if (solutionDepth[iX[i]][iY[i]] >= 0) {
              z[i] = BD(L_[i], W_[i], l, w, n + 1);
              lowerBound[iX[i]][iY[i]] = z[i];
              solutionDepth[iX[i]][iY[i]] = -1;
            } else {
              z[i] = lowerBound[iX[i]][iY[i]];
            }
            if (solutionDepth[iX[i]][iY[i]] > n) {
              z[i] = BD(L_[i], W_[i], l, w, n + 1);
              lowerBound[iX[i]][iY[i]] = z[i];
              if (reachedLimit[iX[i]][iY[i]] == 0) {
                solutionDepth[iX[i]][iY[i]] = -1;
              } else {
                solutionDepth[iX[i]][iY[i]] = n;
              }
            } else {
              z[i] = lowerBound[iX[i]][iY[i]];
            }
            if (reachedLimit[iX[i]][iY[i]] == 1) {
              reachedLimit[indexX[L]][indexY[W]] = 1;
            }
            S_lb = S_lb - zi_lb[i] + z[i];
            S_ub = S_ub - zi_ub[i] + z[i];
            if (z_lb >= S_ub) {
              break;
            } else if (S_lb > z_lb) {
              z_lb = S_lb;
              storeCutPoint(L, W, x1, x2, y1, y2);
              if (z_lb == z_ub) {
                solutionDepth[indexX[L]][indexY[W]] = -1;
                reachedLimit[indexX[L]][indexY[W]] = 0;
                return 1;
              }
            }
          }
        }
      } else {
        reachedLimit[indexX[L]][indexY[W]] = 1;
        S_lb = 0;
        for (i = 1; i <= numBlocks; i++) {
          S_lb += lowerBound[iX[i]][iY[i]];
        }
        if (S_lb > z_lb) {
          z_lb = S_lb;
          storeCutPoint(L, W, x1, x2, y1, y2);
          if (z_lb == z_ub) {
            solutionDepth[indexX[L]][indexY[W]] = -1;
            reachedLimit[indexX[L]][indexY[W]] = 0;
            return 1;
          }
        }
      }
      return 0;
    }
    private int BD(int L, int W, int l, int w, int n) {
      int z_lb;
      int z_ub;
      if (W > L) {
        swap(ref L, ref W);
      }
      z_lb = lowerBound[indexX[L]][indexY[W]];
      z_ub = localUpperBound(indexX[L], indexY[W]);
      if (z_lb == 0 || z_lb == z_ub) {
        solutionDepth[indexX[L]][indexY[W]] = -1;
        reachedLimit[indexX[L]][indexY[W]] = 0;
        return z_lb;
      } else {
        int x1;
        int x2;
        int y1;
        int y2;
        int index_x1;
        int index_x2;
        int index_y1;
        int index_y2;
        int[] L_ = new int[6];
        int[] W_ = new int[6];
        Set rasterX = new Set();
        Set rasterY = new Set();
        int solved;
        constructRasterPoints(L, W, ref rasterX, ref rasterY, normalSetX);
        reachedLimit[indexX[L]][indexY[W]] = 0;
        for (index_x1 = 1; index_x1 < rasterX.size && rasterX.points[index_x1] <= L / 2; index_x1++) {
          x1 = rasterX.points[index_x1];
          for (index_x2 = index_x1 + 1; index_x2 < rasterX.size && rasterX.points[index_x2] + x1 <= L; index_x2++) {
            x2 = rasterX.points[index_x2];
            for (index_y1 = 1; index_y1 < rasterY.size && rasterY.points[index_y1] < W; index_y1++) {
              y1 = rasterY.points[index_y1];
              for (index_y2 = index_y1 + 1; index_y2 < rasterY.size && rasterY.points[index_y2] < W; index_y2++) {
                y2 = rasterY.points[index_y2];
                if (x1 + x2 == L && y1 + y2 > W)
                  break;
                L_[1] = x1;
                W_[1] = W - y1;
                L_[2] = L - x1;
                W_[2] = W - y2;
                L_[3] = x2 - x1;
                W_[3] = y2 - y1;
                L_[4] = x2;
                W_[4] = y1;
                L_[5] = L - x2;
                W_[5] = y2;
                solved = solve(L, W, l, w, n, 5, L_, W_, ref z_lb, z_ub, x1, x2, y1, y2);
                if (solved != 0) {
                  return z_lb;
                }
              }
            }
          }
        }
        for (index_x1 = 1; index_x1 < rasterX.size && rasterX.points[index_x1] <= L / 2; index_x1++) {
          x1 = x2 = rasterX.points[index_x1];
          y1 = y2 = 0;
          L_[1] = x1;
          W_[1] = W - y1;
          L_[2] = L - x1;
          W_[2] = W - y2;
          solved = solve(L, W, l, w, n, 2, L_, W_, ref z_lb, z_ub, x1, x2, y1, y2);
          if (solved != 0) {
            return z_lb;
          }
        }
        for (index_y1 = 1; index_y1 < rasterY.size && rasterY.points[index_y1] <= W / 2; index_y1++) {
          y1 = y2 = rasterY.points[index_y1];
          x1 = x2 = 0;
          L_[1] = L - x1;
          W_[1] = W - y2;
          L_[2] = L - x2;
          W_[2] = y2;
          solved = solve(L, W, l, w, n, 2, L_, W_, ref z_lb, z_ub, x1, x2, y1, y2);
          if (solved != 0) {
            return z_lb;
          }
        }
        return z_lb;
      }
    }
    private int barnesBound(int L, int W, int l, int w) {
      int r;
      int s;
      int D;
      int minWaste = (L * W) % (l * w);
      r = L % l;
      s = W % l;
      int A = Math.Min(r * s, (l - r) * (l - s));
      r = L % w;
      s = W % w;
      int B = Math.Min(r * s, (w - r) * (w - s));
      int maxAB = Math.Max(A, B);
      if (minWaste >= maxAB % (l * w)) {
        D = (maxAB / (l * w)) * (l * w) + minWaste;
      } else {
        D = (maxAB / (l * w) + 1) * (l * w) + minWaste;
      }
      return (L * W - D) / (l * w);
    }
    private void initialize(int L, int W, int l, int w) {
      int L_n;
      int W_n;
      int i;
      int j;
      Set rasterX = new Set();
      Set rasterY = new Set();
      normalSetX = newSet(L + 2);
      constructConicCombinations(L, l, w, ref normalSetX);
      normalize = new int[L + 1];
      i = 0;
      for (j = 0; j <= L; j++) {
        for (; i < normalSetX.size && normalSetX.points[i] <= j; i++)
          ;
        normalize[j] = normalSetX.points[i - 1];
      }
      L_n = normalize[L];
      W_n = normalize[W];
      constructRasterPoints(L, W, ref rasterX, ref rasterY, normalSetX);
      normalSetX = newSet(L_n + 2);
      int k = 0;
      i = 0;
      j = 0;
      while (i < rasterX.size && rasterX.points[i] <= L_n && j < rasterY.size && rasterY.points[j] <= W_n) {
        if (rasterX.points[i] == rasterY.points[j]) {
          normalSetX.points[k++] = rasterX.points[i++];
          normalSetX.size++;
          j++;
        } else if (rasterX.points[i] < rasterY.points[j]) {
          normalSetX.points[k++] = rasterX.points[i++];
          normalSetX.size++;
        } else {
          normalSetX.points[k++] = rasterY.points[j++];
          normalSetX.size++;
        }
      }
      while (i < rasterX.size && rasterX.points[i] <= L_n) {
        if (rasterX.points[i] > normalSetX.points[k - 1]) {
          normalSetX.points[k++] = rasterX.points[i];
          normalSetX.size++;
        }
        i++;
      }
      if (k > 0 && normalSetX.points[k - 1] < L_n) {
        normalSetX.points[k++] = L_n;
        normalSetX.size++;
      }
      normalSetX.points[k] = L_n + 1;
      normalSetX.size++;
      indexX = new int[L_n + 2];
      indexY = new int[W_n + 2];
      for (i = 0; i < normalSetX.size; i++) {
        indexX[normalSetX.points[i]] = i;
      }
      int ySize = 0;
      for (i = 0; i < normalSetX.size; i++) {
        if (normalSetX.points[i] > W_n) {
          break;
        }
        ySize++;
        indexY[normalSetX.points[i]] = i;
      }
      solutionDepth = new int[normalSetX.size][];
      upperBound = new int[normalSetX.size][];
      lowerBound = new int[normalSetX.size][];
      reachedLimit = new int[normalSetX.size][];
      cutPoints = new CutPoint[normalSetX.size, ySize];
      for (i = 0; i < normalSetX.size; i++) {
        solutionDepth[i] = new int[ySize];
        upperBound[i] = new int[ySize];
        lowerBound[i] = new int[ySize];
        for (int h = 0; h < ySize; h++)
          cutPoints[i, h] = new CutPoint(0, 0, 0, 0, 0);
        reachedLimit[i] = new int[ySize];
      }
      for (i = 0; i < normalSetX.size; i++) {
        int x = normalSetX.points[i];
        for (j = 0; j < ySize; j++) {
          int y = normalSetX.points[j];
          solutionDepth[i][j] = N;
          reachedLimit[i][j] = 1;
          upperBound[i][j] = barnesBound(x, y, l, w);
          lowerBound[i][j] = LowerBound(x, y, l, w);
          cutPoints[i, j].homogeneous = 1;
        }
      }
    }
    private int LowerBound(int L, int W, int l, int w) {
      return Math.Max((L / l) * (W / w), (L / w) * (W / l));
    }
    private int solve_BD(int L, int W, int l, int w, int N_max) {
      int L_n;
      int W_n;
      N = N_max;
      if (N <= 0) {
        N = INFINITY_;
      }
      if (W > L) {
        swap(ref L, ref W);
      }
      initialize(L, W, l, w);
      L_n = normalize[L];
      W_n = normalize[W];
      int solution = BD(L_n, W_n, l, w, N);
      if (solution != upperBound[indexX[L_n]][indexY[W_n]] && N != 1) {
        solution = BD(L_n, W_n, l, w, 1);
      }
      lowerBound[indexX[L_n]][indexY[W_n]] = solution;
      reachedLimit = null;
      solutionDepth = null;
      return solution;
    }
    private void draw(int[] q) {
      draw(q[0], q[1], 0, 0);
    }
    private short boxOrientation(int x, int y) {
      int a = (x / l) * (y / w);
      int b = (x / w) * (y / l);
      return Convert.ToInt16((a > b) ? HORIZONTAL : VERTICAL);
    }
    private void drawHomogeneous(int x, int y, int dx, int dy) {
      int i;
      int j;
      short corte = boxOrientation(x, y);
      if (corte == HORIZONTAL) {
        for (i = 0; i + l <= x; i += l) {
          for (j = 0; j + w <= y; j += w) {
            this.Rectangles.Add(new Rectangle(i + dx,j + dy, l, w));
          }
        }
      } else {
        for (i = 0; i + w <= x; i += w) {
          for (j = 0; j + l <= y; j += l) {
            this.Rectangles.Add(new Rectangle(i + dx, j + dy, w, l));
          }
        }
      }
    }
    private void getSubproblems(CutPoint cutPoint, int[] L_, int[] W_, int L, int W) {
      int x1 = cutPoint.x1;
      int x2 = cutPoint.x2;
      int y1 = cutPoint.y1;
      int y2 = cutPoint.y2;
      L_[1] = x1;
      W_[1] = normalize[W - y1];
      L_[2] = normalize[L - x1];
      W_[2] = normalize[W - y2];
      L_[3] = normalize[x2 - x1];
      W_[3] = normalize[y2 - y1];
      L_[4] = x2;
      W_[4] = y1;
      L_[5] = normalize[L - x2];
      W_[5] = y2;
    }
    private void drawRotation(int L, int W, int dx, int dy) {
      int[] L_ = new int[6];
      int[] W_ = new int[6];
      int i;
      int iX;
      int iY;
      swap(ref L, ref W);
      iX = indexX[L];
      iY = indexY[W];
      if (cutPoints[iX, iY].homogeneous == 1) {
        swap(ref L, ref W);
        drawHomogeneous(L, W, dx, dy);
        return;
      }
      getSubproblems(cutPoints[iX, iY], L_, W_, L, W);
      for (i = 1; i <= 5; i++) {
        swap(ref L_[i], ref W_[i]);
        if (L_[i] != 0 && W_[i] != 0 && !((L_[i] == L && W_[i] == W) || (L_[i] == W && W_[i] == L))) {
          switch (i) {
            case 1:
              draw(L_[1], W_[1], dx + W_[4], dy + L_[2]);
              break;
            case 2:
              draw(L_[2], W_[2], dx + W_[5], dy);
              break;
            case 3:
              draw(L_[3], W_[3], dx + W_[4], dy + L_[5]);
              break;
            case 4:
              draw(L_[4], W_[4], dx, dy + L_[5]);
              break;
            case 5:
              draw(L_[5], W_[5], dx, dy);
              break;
          }
        }
        swap(ref L_[i], ref W_[i]);
      }
    }
    private void drawNormal(int L, int W, int dx, int dy) {
      int i;
      int[] L_ = new int[6];
      int[] W_ = new int[6];
      int iX = indexX[L];
      int iY = indexY[W];
      if (cutPoints[iX, iY].homogeneous == 1) {
        drawHomogeneous(L, W, dx, dy);
        return;
      }
      getSubproblems(cutPoints[iX, iY], L_, W_, L, W);
      for (i = 1; i <= 5; i++) {
        if (L_[i] != 0 && W_[i] != 0 && !((L_[i] == L && W_[i] == W) || (L_[i] == W && W_[i] == L))) {
          switch (i) {
            case 1:
              draw(L_[1], W_[1], dx, dy + W_[4]);
              break;
            case 2:
              draw(L_[2], W_[2], dx + L_[1], dy + W_[5]);
              break;
            case 3:
              draw(L_[3], W_[3], dx + L_[1], dy + W_[4]);
              break;
            case 4:
              draw(L_[4], W_[4], dx, dy);
              break;
            case 5:
              draw(L_[5], W_[5], dx + L_[4], dy);
              break;
          }
        }
      }
    }
    private void draw(int L, int W, int dx, int dy) {
      if (L >= W) {
        drawNormal(L, W, dx, dy);
      } else {
        drawRotation(L, W, dx, dy);
      }
    }
  }
}