Уместить картинки в прямоугольной области

#алгоритм

Имеется N картинок и прямоугольная область. Необходимо подобрать размер картинок
так, чтобы они заняли максимальную площадь прямоугольника, т.е. полностью вместились
в прямоугольник. Картинки должны быть одинакового размера, разница допустима, если
только она не бросается в глаза (лишние пару пикселей у некоторых картинок не страшны).
Также, картинки должны меняться в размере пропорционально, опять же разница в несколько
пикселей не страшна, если она визуально не заметна. Прикрепляю примеры, как должно быть. 
Нужен алгоритм.


UPD:
Скрин к ответу Peter Olson.

    

Ответы

Ответ 1

Начнём с самым простым алгоритмом (грубая сила): попробуем уместить картинки в одном
столбцом, потом в двух, трёх, и т.д. до N, чтобы найти количество столбцов, соответствующее
на максимальную плошадь.



function bestDimensions(N, aspect, width, height) {
  var maxArea = 0;
  var bestWidth, bestHeight;
  for (var cols = 1; cols <= N; cols++) {
    var rows = Math.ceil(N / cols);
    var w = width / cols;
    if ((w / aspect) * rows > height) {
      w = height * aspect / rows;
    }
    var h = w / aspect;
    var area = N * w * h;
    if (area > maxArea) {
      maxArea = area;
      bestWidth = w;
      bestHeight = h;
    }
  }
  return [bestWidth, bestHeight];
}

// Следующий код не алгоритм. Это просто код для демо.
byId("show").onclick = function() {
  var width = +byId("width").value,
    height = +byId("height").value,
    aspect = +byId("aspect").value,
    N = +byId("N").value;
  var dimensions = bestDimensions(N, aspect, width, height);
  var imageWidth = dimensions[0],
    imageHeight = dimensions[1];
  var canvas = byId("canvas");
  canvas.width = width;
  canvas.height = height;
  var ct = canvas.getContext("2d");
  var x = 0,
    y = 0;
  while (N--) {
    ct.beginPath();
    ct.rect(x, y, imageWidth, imageHeight);
    ct.fillStyle = 'yellow';
    ct.fill();
    ct.lineWidth = 1;
    ct.strokeStyle = 'black';
    ct.stroke();
    if (x + imageWidth > width - imageWidth) {
      x = 0;
      y += imageHeight;
    } else {
      x += imageWidth;
    }
  }
};

function byId(id) {
  return document.getElementById(id);
}
#canvas {
  border: 1px solid black;
}
N:

Cоотношение сторон:

Высота:

Ширина:








Это конечно не оптимальный алгоритм, хотя довольно простой, и по-моему достаточно
быйстрый: код для показа картинок будет намного медленее.

ПРАВКА: Использую canvas вместо HTML divов. Теперь не выходит за границу области.


Ответ 2

Улучшил алгоритм, теперь поиск занимает обычно около 5 итераций.



Исправил несколько ошибок.



Вот ещё один вариант, на WPF.

Переменные: PicMargin — маргин вокруг картинки, PicQuantity — количество картинок,
PicWidth/PicHeight — высота/ширина нерастянутой картинки, TargetSpace.ActualWidth/TargetSpace.ActualHeight
— размер области, где нужно разметить картинки. Как alpha обозначен коэффициент растяжения
картинки. Алгоритм находит максимальное возможное значение alpha.

// подсчёт alpha для данного к-ва строк и столбцов
double CalcAlpha(int m, int n)
{
    // m * (alpha * w + margin) + margin <= clientW <=> 
    //      alpha <= ((clientW - margin)/m - margin)/w
    // n * (alpha * h + margin) + margin <= clientH <=>
    //      alpha <= ((clientH - margin)/n - margin)/h
    var clientW = TargetSpace.ActualWidth - PicMargin;
    var clientH = TargetSpace.ActualHeight - PicMargin;

    return Math.Min(((clientW - PicMargin)/m - PicMargin)/PicWidth,
                    ((clientH - PicMargin)/n - PicMargin)/PicHeight);
}

// оценка нужного количества строк
double EstimateM()
{
    var clientW = TargetSpace.ActualWidth - PicMargin;
    var clientH = TargetSpace.ActualHeight - PicMargin;
    // m * picW : n * picH = clientW : clientH, m : n = (clientW * picH) : (clientH
* picW)
    var approxAspectRatio = (double)(clientW * PicHeight) / (clientH * PicWidth);
    // m * n = PicQuantity => m * m = approxAspectRatio * PicQuantity
    return Math.Sqrt(approxAspectRatio * PicQuantity);
}

// подсчёт лучшего alpha
void Update()
{
    int iterations = 0;
    double bestAlpha = double.NegativeInfinity;
    int bestM = 0, bestN = 0;
    var mApprox = Math.Min(Math.Max((int)Math.Round(EstimateM()), 1), PicQuantity);

    // ищем наилучший вариант вверх и вниз от оценочного значения
    // поскольку качество решения зависит от к-ва строк горкой,
    // можно выходить из цикла как только началось ухудшение
    for (int m = mApprox; m <= PicQuantity; m++)
    {
        iterations++;
        // берём необходимое количество столбцов
        int n = (int)Math.Ceiling((double)PicQuantity / m);
        // и вычисляем alpha для этого случая
        var currAlpha = CalcAlpha(m, n);
        if (currAlpha < bestAlpha)
            break;
        // запоминаем текущий лучший результат
        bestAlpha = currAlpha;
        bestM = m;
        bestN = n;
    }
    // то же вниз
    for (int m = mApprox - 1; m >= 1; m--)
    {
        iterations++;
        int n = (int)Math.Ceiling((double)PicQuantity / m);
        var currAlpha = CalcAlpha(m, n);
        if (currAlpha < bestAlpha)
            break;
        bestAlpha = currAlpha;
        bestM = m;
        bestN = n;
    }
    Debug.WriteLine("Iterations: " + iterations);

    TargetSpace.Children.Clear();
    if (bestAlpha > 0)
        PlacePictures(bestM, bestN, bestAlpha);
    else
        TargetSpace.Children.Add(
            new TextBlock() { Text = "Impossible", Foreground = Brushes.Red });
}

// вывод
void PlacePictures(int m, int n, double alpha)
{
    double xstep = PicMargin + PicWidth * alpha,
           ystep = PicMargin + PicHeight * alpha;
    // центрируем по горизонтали
    double x0 = PicMargin + (TargetSpace.ActualWidth - PicMargin - m * xstep) / 2,
           y0 = PicMargin;
    for (int j = 0; j < n - 1; j++)
        for (int i = 0; i < m; i++)
            PlacePictureAt(x0 + i * xstep, y0 + j * ystep, alpha);
    // отдельно центрируем последнюю строку
    var remainingPictures = PicQuantity - (n - 1) * m;
    x0 = PicMargin + (TargetSpace.ActualWidth - PicMargin - remainingPictures * xstep) / 2;
    for (int i = 0; i < remainingPictures; i++)
        PlacePictureAt(x0 + i * xstep, y0 + (n - 1) * ystep, alpha);
}


Полный код:

MainWindow.xaml.cs:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace PicturePlacement
{
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
            TargetSpace.SizeChanged += (o, args) => Update();
            Update();
        }

        double CalcAlpha(int m, int n)
        {
            // m * (alpha * w + margin) + margin <= clientW  <=>  alpha <= ((clientW
- margin)/m - margin)/w
            // n * (alpha * h + margin) + margin <= clientH  <=>  alpha <= ((clientH
- margin)/n - margin)/h
            var clientW = TargetSpace.ActualWidth - PicMargin;
            var clientH = TargetSpace.ActualHeight - PicMargin;

            return Math.Min(((clientW - PicMargin)/m - PicMargin)/PicWidth,
                            ((clientH - PicMargin)/n - PicMargin)/PicHeight);
        }

        double EstimateM()
        {
            var clientW = TargetSpace.ActualWidth - PicMargin;
            var clientH = TargetSpace.ActualHeight - PicMargin;
            // m * picW : n * picH = clientW : clientH, m : n = (clientW * picH)
: (clientH * picW)
            var approxAspectRatio = (double)(clientW * PicHeight) / (clientH * PicWidth);
            // m * n = PicQuantity => m * m = approxAspectRatio * PicQuantity
            return Math.Sqrt(approxAspectRatio * PicQuantity);
        }

        void Update()
        {
            int iterations = 0;
            double bestAlpha = double.NegativeInfinity;
            int bestM = 0, bestN = 0;
            var mApprox = Math.Min(Math.Max((int)Math.Round(EstimateM()), 1), PicQuantity);
            for (int m = mApprox; m <= PicQuantity; m++)
            {
                iterations++;
                int n = (int)Math.Ceiling((double)PicQuantity / m);
                var currAlpha = CalcAlpha(m, n);
                if (currAlpha < bestAlpha)
                    break;
                bestAlpha = currAlpha;
                bestM = m;
                bestN = n;
            }
            for (int m = mApprox - 1; m >= 1; m--)
            {
                iterations++;
                int n = (int)Math.Ceiling((double)PicQuantity / m);
                var currAlpha = CalcAlpha(m, n);
                if (currAlpha < bestAlpha)
                    break;
                bestAlpha = currAlpha;
                bestM = m;
                bestN = n;
            }
            Debug.WriteLine("Iterations: " + iterations);

            TargetSpace.Children.Clear();
            if (bestAlpha > 0)
                PlacePictures(bestM, bestN, bestAlpha);
            else
                TargetSpace.Children.Add(new TextBlock() { Text = "Impossible", Foreground
= Brushes.Red });
        }

        void PlacePictures(int m, int n, double alpha)
        {
            double xstep = PicMargin + PicWidth * alpha, ystep = PicMargin + PicHeight
* alpha;
            double x0 = PicMargin + (TargetSpace.ActualWidth - PicMargin - m * xstep)
/ 2, y0 = PicMargin;
            for (int j = 0; j < n - 1; j++)
                for (int i = 0; i < m; i++)
                    PlacePictureAt(x0 + i * xstep, y0 + j * ystep, alpha);
            var remainingPictures = PicQuantity - (n - 1) * m;
            x0 = PicMargin + (TargetSpace.ActualWidth - PicMargin - remainingPictures
* xstep) / 2;
            for (int i = 0; i < remainingPictures; i++)
                PlacePictureAt(x0 + i * xstep, y0 + (n - 1) * ystep, alpha);
        }

        void PlacePictureAt(double x, double y, double alpha)
        {
            Rectangle r = new Rectangle() { Height = PicHeight * alpha, Width = PicWidth
* alpha, Fill = Brushes.Green };
            Canvas.SetLeft(r, x);
            Canvas.SetTop(r, y);
            TargetSpace.Children.Add(r);
        }

        #region propdp int PicHeight
        public int PicHeight
        {
            get { return (int)GetValue(PicHeightProperty); }
            set { SetValue(PicHeightProperty, value); }
        }

        public static readonly DependencyProperty PicHeightProperty = 
            DependencyProperty.Register("PicHeight", typeof(int), typeof(MainWindow),
                                        new PropertyMetadata(1, (o, args) => ((MainWindow)o).Update()));
        #endregion

        #region propdp int PicWidth
        public int PicWidth
        {
            get { return (int)GetValue(PicWidthProperty); }
            set { SetValue(PicWidthProperty, value); }
        }

        public static readonly DependencyProperty PicWidthProperty = 
            DependencyProperty.Register("PicWidth", typeof(int), typeof(MainWindow),
                                        new PropertyMetadata(1, (o, args) => ((MainWindow)o).Update()));
        #endregion

        #region propdp int PicQuantity
        public int PicQuantity
        {
            get { return (int)GetValue(PicQuantityProperty); }
            set { SetValue(PicQuantityProperty, value); }
        }

        public static readonly DependencyProperty PicQuantityProperty = 
            DependencyProperty.Register("PicQuantity", typeof(int), typeof(MainWindow),
                                        new PropertyMetadata(1, (o, args) => ((MainWindow)o).Update()));
        #endregion

        #region propdp int PicMargin
        public int PicMargin
        {
            get { return (int)GetValue(PicMarginProperty); }
            set { SetValue(PicMarginProperty, value); }
        }

        public static readonly DependencyProperty PicMarginProperty = 
            DependencyProperty.Register("PicMargin", typeof(int), typeof(MainWindow),
                                        new PropertyMetadata(10, (o, args) => ((MainWindow)o).Update()));
        #endregion
    }
}


MainWindow.xaml:


    
        
            
            
        
        
            Client
W:
            
            
            Client
H:
            
            
            Width:
            
            
            Height:
            
            
            Quantity:
            
            
            Margin:
            
        
        
    



Ответ 3

Первое, что пришло в голову, помимо перебора

function bestDimensions(images, width, height)
{
    var area = Math.sqrt(width * height / images);
    var square_w = Math.ceil(width / area);
    var square_h = Math.ceil(height / area);
    var sw = width / square_w;
    var sh = height / square_h;
    var sz = Math.floor(Math.max(sw, sh));

    var h = Math.floor(width / sz);
    var v = Math.floor(height / sz);

    if (h * v < images)
    {
        sz = Math.floor(Math.min(sw, sh));
        h = Math.floor(width / sz);
        v = Math.floor(height / sz);
    }

    return sz;
}


На входе:
width - ширина области в пикселях
height - высота области в пикселях
images - количество изображений

На выходе:
sz - размер изображения в пикселях (изображение квадратное);
h - максимальное количество изображений по горизонтали;
v - максимальное количество изображений по вертикали;

upd: изменил код на JavaScript