Layout algorithm

I have an array of N pictures, each with dimensions WxH. I want to display them in a rectangular matrix that is as close to a square as possible. The last row may be incomplete. How do I calculate the number of rows an开发者_如何学Cd columns?

---

So, suppose you have p across and q down; then your whole image is pW by qH. You want to include all the images, so pq >= N; only the last row is allowed to be incomplete, so p(q-1) < N. And, subject to those conditions, you want pW and qH to be as nearly equal as possible. (Perhaps you would also prefer pq-N to be as small as possible?)

The conditions N < p(q-1) <= N are equivalent to q = ceiling(N/p). So you want to choose p so that the ratio p:ceiling(N/p) is as close as possible to H:W (in some sense; perhaps you want to minimize the absolute difference of the logarithms, or something).

So, very crudely, p/(N/p) ~= H/W, so p ~= sqrt(NH/W).

As p increases, N/p decreases, hence ceiling(N/p) at least doesn't increase. So p/ceiling(N/p) is an increasing function of p. So, whatever criterion for closeness-of-ratio you prefer, there is exactly one value of p that does the job, and the ratio gets worse in one direction as you move away from it one way, and worse in the other direction as you move away in the other.

So, super-naive but probably adequate pseudocode is as follows (note that it ignores stuff like conversion between integer and floating-point values):

target_ratio = H/W;
p = round(sqrt(N*H/W)); // initial guess
current_ratio = p / ceiling(N/p);
merit = merit_function(current_ratio, target_ratio);
best_p = p; best_merit = merit; prev_merit = merit;
// [define merit_function however you like; e.g., -abs(log(x/y)-1)
// or -max(x/y-1,y/x-1) or whatever.]
if (current_ratio > target_ratio) {
  // p might be too big
  while (true) {
    --p; if (p<=0) break;
    current_ratio = p / ceiling(N/p);
    merit = merit_function(current_ratio, target_ratio);
    if (merit > best_merit) { best_p=p; best_merit=merit; }
    else if (merit < prev_merit) break;
    prev_merit = merit;
  }
}
else if (current_ratio < target_ratio) {
  // p might be too small
  // similar loop, but in the other direction
}

I suspect that for reasonable choices of merit_function you only ever have to do one iteration, but I don't feel like trying to prove that right now.

If an adequate solution, rather than an optimal one, is good enough then you could just use p=round(sqrt(N*H/W)) and be done with it. Or, for a slightly better approximation, you could say that ceiling(N/p) is probably about N/p+0.5 on average, kinda, which I think ends up meaning that you want something like p = round(sqrt(N*H/W+0.25*H*H/(W*W)) - 0.25*H/W. (You should probably check my algebra before relying on it. I'm just simplifying p/(N/p-1/2) = H/W and solving the resulting quadratic equation.)

---

You can try all possible layouts if N is small enough.

Score(N, W, H, columnCount):
    rowCount = ceiling(N / columnCount)
    xPixels = W * columnCount
    yPixels = H * rowCount
    return min(xPixels, yPixels) / max(xPixels, yPixels)

bestColumnCount = columnCount with max Score(N, W, H, columnCount) in [1,N]
bestRowCount = ceiling(N / bestColumnCount) 

---

(1st try was totally wrong..

(so was 2nd try)

3nd try:

columns = floor( sqroot( N * H / W ) + 0.5 )
rows = ceiling( N / columns )