Имеется N картинок и прямоугольная область. Необходимо подобрать размер картинок так, чтобы они заняли максимальную площадь прямоугольника, т.е. полностью вместились в прямоугольник. Картинки должны быть одинакового размера, разница допустима, если только она не бросается в глаза (лишние пару пикселей у некоторых картинок не страшны). Также, картинки должны меняться в размере пропорционально, опять же разница в несколько пикселей не страшна, если она визуально не заметна. Прикрепляю примеры, как должно быть.
Нужен алгоритм.
UPD:
Скрин к ответу Peter Olson.
Ответ
Начнём с самым простым алгоритмом (грубая сила): попробуем уместить картинки в одном столбцом, потом в двух, трёх, и т.д. до 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ов. Теперь не выходит за границу области.
Комментариев нет:
Отправить комментарий