How to layout a given number of thumbnails N of picW x picH into m columns and n rows in a given page (pageW x pageH) so that the “to be applied” scale is maximal? All thumbnails yield the same dimensions, reordering is not allowed, rotation neither. If the chosen scale is maximized, then the result will have the biggest possible thumbnails. I need this for the contactSheet-script, because currently it uses fixed column-sizes and I don’t want to figure this out manually each time the wanted page- or thumbnail-size or the amount of thumbnails changes.
I am aware, that this is some kind of well known bin-packing problem, but just after implementing the very first naive approach I figured out that there is maybe(?) no closed equation possible: just iterating over all possible cases. Maybe I missed something, but the current approach would look like the following. I will move this from C++/Qt to sh soon, because this will become part of contactSheet-script which I apply to every set of scanned film 😉
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
int const pageW(ui->pageW_LE->text().toInt()); //maybe validate later! int const pageH(ui->pageH_LE->text().toInt()); //maybe validate later! int const picW(ui->picW_LE->text().toInt()); //maybe validate later! int const picH(ui->picH_LE->text().toInt()); //maybe validate later! int const N(ui->N_LE->text().toInt()); //maybe validate later! int result[2]; double maxScale(0.0); double maxA(0.0); for(int m(1); m <= N; m++) { int const n = N / m + ((N % m != 0) ? 1 : 0); qDebug() << "############################################\nm * n: " << QString::number(m) << " * " << QString::number(n); double const scaleW = (double)pageW / (double)(m * picW); double const scaleH = (double)pageH / (double)(n * picH); qDebug() << "scales: " << QString::number(scaleW) << " * " << QString::number(scaleH); double const minScale(scaleW < scaleH ? scaleW : scaleH); double const resultW = m * minScale * picW; double const resultH = n * minScale * picH; double const A = resultW * resultH; qDebug() << "A = " << QString::number(A) << " with scale " << QString::number(minScale); //use the first found biggest result if(minScale > maxScale) { maxScale = minScale; //save for later usage maxA = A; //just for checking result[0] = m; result[1] = n; } } qDebug() << "\n\nlayout with:" << QString::number(result[0]) << "*" << QString::number(result[1]) << " with A = " << QString::number(maxA) << " and scale " << QString::number(maxScale); |
By the way: the sketch has been done with draw.io, because I stopped using Dia …
Leave a Reply
You must be logged in to post a comment.