Anzahl der Permutationen verringern?

Lennox

Nabend. Ich versuche, eine Bilderkollage zu erstellen. Eine Kollage ist eine Sammlung von Bildern, die nebeneinander dargestellt werden... Die Bilder sind unterschiedlich groß. Ich möchte die Bilder in einem Quadrat anordnen, wobei das Quadrat möglichst klein sein soll. Der vorhandene Platz soll also optimal genutzt werden...

Bis ca. n=20 gelingt mir das auch ganz gut, aber danach entstehen Freiräume, bzw. der Platz wird nicht mehr optimal genutzt. Weiß vielleicht jemand, wie man geschickt die Anzahl der Permutationen verringern kann? So dass nicht jede Permutation geprüft werden muss?

Hier ist ein Beispiel mit vier Bildern: https://postimg.cc/D47m3kkQ

Lennox

Das Kuriose ist auch, dass die freien Stellen für einen Menschen ganz leicht zu erkennen sind - aber für den Backtracking-Algo eben nicht...

Also, welche Approximationen (oder Schätzungen) gibt es für dieses Problem?

Ich hatte diese Frage zunächst auch in einem anderen Forum gestellt (Computerbase), dort aber ein lebenslanges Hausverbot bekommen, weil dort überwiegend in Berlin angesiedelt Journalisten sind, die nur links-grüne Meinungen zulassen. Andere Positionen sind dort nicht erwünscht... Ich weiß gar nicht, ob ein grundloser Bann rechtens ist, aber andererseits ist das auch eigentlich ein Hardwareforum - und Fragen zur Programmierung sind dort eher nur eine Nischen-Erscheinung. Vermutlich wird sich auch erst dann mal daran etwas ändern, sobald die AfD regiert... denn dann werden sehr viele auch mal um ihre sicher geglaubte Position fürchten müssen.

Jedenfalls wüsste ich sonst nicht, wo ich diese Frage noch stellen könnte (von der KI oder Stack Overflow mal abgesehen).

Lennox

Schon gelöst...

Man muss gar nicht über alle Permutationen gehen... Es genügt, einmal nach der Weite zu sortieren, und dann zeilenweise durchzugehen, und jeweils das letzte Element in die nächste Zeile zu verschieben, insofern sich ein kleineres Quadrat ergibt.

So könnte eine Implementierung sein:

  private static int getRowWidth(ArrayList<Image> row) {
    int rowWidth = SPACE_D;
    for (Image img : row) {
      rowWidth += img.getWidth(null) + SPACE_D;
    }
    return rowWidth;
  }

  private static int getRowHeight(ArrayList<Image> row) {
    int rowHeight = 0;
    for (Image img : row) {
      rowHeight = Math.max(rowHeight, img.getHeight(null) + SPACE_D);
    }
    return rowHeight;
  }

  private static int calculateArea(ArrayList<ArrayList<Image>> imgTable) {
    int wmax = 0;
    int hmax = SPACE_D;
    for (ArrayList<Image> row : imgTable) {
      if (row.isEmpty()) {
        continue;
      }
      int row_w = getRowWidth(row);
      int row_h = getRowHeight(row);
      wmax = Math.max(wmax, row_w);
      hmax += row_h;
    }
    return Math.max(wmax, hmax);
  }

  private static void sortAndSaveImages(ArrayList<Image> images) throws IOException {
    ArrayList<Image> sortedImages = new ArrayList<>(images);
    // Not sure if sorting by width is the best strategy, but it's a start
    sortedImages.sort(
        (img1, img2) -> {
          int w1 = img1.getWidth(null);
          int w2 = img2.getWidth(null);
          return Integer.compare(w1, w2);
        });

    ArrayList<ArrayList<Image>> imgTable = new ArrayList<>();
    final int row_len = images.size();
    for (int i = 0; i < row_len; i++) {
      imgTable.add(new ArrayList<>());
    }
    for (Image sortedImage : sortedImages) {
      imgTable.get(0).add(sortedImage);
    }

    ArrayList<ArrayList<Image>> bestTable = backtrack(imgTable, 0);
    // Sort each row to have a consistent output
    for (ArrayList<Image> row : bestTable) {
      row.sort(
          (img1, img2) -> {
            int i1 = images.indexOf(img1);
            int i2 = images.indexOf(img2);
            return Integer.compare(i1, i2);
          });
    }

    Integer[] bestPositions = new Integer[row_len * row_len];
    for (int i = 0; i < bestTable.size(); i++) {
      ArrayList<Image> row = bestTable.get(i);
      for (int j = 0; j < row.size(); j++) {
        Image img = row.get(j);
        int index = images.indexOf(img);
        bestPositions[i * row_len + j] = index;
      }
    }
    int bestArea = calculateArea(bestTable);

    saveImages(images, bestPositions, bestArea, row_len);
  }

  private static ArrayList<ArrayList<Image>> shallowCopy(ArrayList<ArrayList<Image>> imgTable) {
    ArrayList<ArrayList<Image>> newTable = new ArrayList<>();
    for (ArrayList<Image> row : imgTable) {
      newTable.add(new ArrayList<>(row));
    }
    return newTable;
  }

  private static ArrayList<ArrayList<Image>> backtrack(
      ArrayList<ArrayList<Image>> imgTable, int index) {
    if (index + 1 >= imgTable.size()) {
      return imgTable;
    }
    if (imgTable.get(index).isEmpty()) {
      return imgTable;
    }

    // Calculate current area
    int bestArea = calculateArea(imgTable);
    ArrayList<ArrayList<Image>> bestTable = imgTable;

    // Try moving last image from row index to row index + 1 (e.g., balancing rows)
    ArrayList<ArrayList<Image>> copy = shallowCopy(imgTable);
    ArrayList<Image> r1 = copy.get(index);
    ArrayList<Image> r2 = copy.get(index + 1);
    r2.add(0, r1.remove(r1.size() - 1));

    ArrayList<ArrayList<Image>> bt = backtrack(copy, index + 1);
    int area = calculateArea(bt);
    if (area >= bestArea) {
      // No improvement, return best found so far
      return bestTable;
    }
    bestArea = area;
    bestTable = shallowCopy(bt);

    // Can we do better by moving more images from row index to row index + 1?
    bt = backtrack(copy, index);
    area = calculateArea(bt);
    if (area < bestArea) {
      // Found a better arrangement
      bestTable = shallowCopy(bt);
    }

    return bestTable;
  }

Das "Saven" ist dann straightforward:

    BufferedImage b_image = new BufferedImage(bestArea, bestArea, BufferedImage.TYPE_INT_RGB);
    Graphics2D g2d = b_image.createGraphics();
    g2d.setColor(Color.LIGHT_GRAY);
    g2d.fillRect(0, 0, b_image.getWidth(), b_image.getHeight());

    g2d.setColor(Color.BLACK);
    int hmax = SPACE_D;
    for (int i = 0; i < row_len; i++) {
      int row_w = SPACE_D;
      int row_h = 0;
      for (int j = 0; j < row_len; j++) {
        Integer p = positions[i * row_len + j];
        if (p != null) {
          Image image = images.get(p);
          g2d.drawImage(image, row_w, hmax, null);
          g2d.drawString("Img " + p, row_w + 5, hmax + image.getHeight(null) + 15);
          int w = image.getWidth(null) + SPACE_D;
          int h = image.getHeight(null) + SPACE_D;
          row_w += w;
          row_h = Math.max(row_h, h);
        }
      }
      hmax += row_h;
    }

    g2d.dispose();

    // ImageIO.write(b_image, ...

Lennox

Oh, man sollte nach Höhe aufsteigend sortieren... Der Rest bleibt unverändert.

Finnegan

@Lennox Habe deine Problematik nur quergelesen, aber vielleicht bietet dieses Paper hier ja ein paar zusätzliche Inspirationen:

A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing, Jukka Jylänki, 2010

Edit: gerade erst diesen politischen Kommentar gesehen. Völlig unnötig, das hier zu erwähnen, weil es überhaupt nichts zur Sache tut. Eventuell wollte man dich in einem "Hardware-Forum" auch nicht mehr haben, weil sowas am Thema vorbei geht und Diskussionen entgleisen lässt? Nur so als Denkanstoß, bitte nicht weiter vertiefen ("Diskussionen entgleisen" und so).

Lennox

Ich glaube eher, die mögen mich nicht, weil ich sage, was ich denke... Eine Eigenschaft, mit der nicht jeder umgehen kann... Bitte nicht weiter vertiefen.

@Finnegan sagte in Anzahl der Permutationen verringern?:

Habe deine Problematik nur quergelesen, aber vielleicht bietet dieses Paper hier ja ein paar zusätzliche Inspirationen:

Danke für die Anregung, aber an für sich bin ich mit meinem Approach schon zufrieden. Ab ca. 15 Items wird es langsam, aber man könnte die Rekursionstiefe auch noch begrenzen.

Das Problem ist ja nicht neu und vielleicht vergleichbar dem TSP, also auch NP-schwer. Deshalb geht es eigentlich nur noch darum, bestimmte Annäherungen/Approximationen zu finden.

Belli

@Lennox sagte in Anzahl der Permutationen verringern?:

Ich glaube eher, die mögen mich nicht, weil ich sage, was ich denke... Eine Eigenschaft, mit der nicht jeder umgehen kann... Bitte nicht weiter vertiefen.

Ich glaube, es ist umgekehrt: Man mag Dich nicht, weil Du denkst, was Du sagst.
Bitte nicht weiter vertiefen.

DocShoe

@Lennox sagte in Anzahl der Permutationen verringern?:

Das Kuriose ist auch, dass die freien Stellen für einen Menschen ganz leicht zu erkennen sind - aber für den Backtracking-Algo eben nicht...

Also, welche Approximationen (oder Schätzungen) gibt es für dieses Problem?

Ich hatte diese Frage zunächst auch in einem anderen Forum gestellt (Computerbase), dort aber ein lebenslanges Hausverbot bekommen, weil dort überwiegend in Berlin angesiedelt Journalisten sind, die nur links-grüne Meinungen zulassen. Andere Positionen sind dort nicht erwünscht... Ich weiß gar nicht, ob ein grundloser Bann rechtens ist, aber andererseits ist das auch eigentlich ein Hardwareforum - und Fragen zur Programmierung sind dort eher nur eine Nischen-Erscheinung. Vermutlich wird sich auch erst dann mal daran etwas ändern, sobald die AfD regiert... denn dann werden sehr viele auch mal um ihre sicher geglaubte Position fürchten müssen.

Jedenfalls wüsste ich sonst nicht, wo ich diese Frage noch stellen könnte (von der KI oder Stack Overflow mal abgesehen).

Wird mal wieder Zeit für ne Accountsperre.

Lennox

@Belli sagte in Anzahl der Permutationen verringern?:

Ich glaube, es ist umgekehrt: Man mag Dich nicht, weil Du denkst, was Du sagst.

Das ergibt keinen Sinn. Aber Logik war noch nie eure Stärke.

SeppJ

@Lennox sagte in Anzahl der Permutationen verringern?:

@Belli sagte in Anzahl der Permutationen verringern?:

Ich glaube, es ist umgekehrt: Man mag Dich nicht, weil Du denkst, was Du sagst.

Das ergibt keinen Sinn. Aber Logik war noch nie eure Stärke.

Na dann eben doch. War ja nur eine Frage der Zeit. Hat dieses Mal erstaunlich lange gehalten. Bis zum nächsten Account.