Алгоритм нарезки прямоугольника на равные меньшие прямоугольники

#алгоритм #геометрия

Дан исходный прямоугольник N×M.
Задача: определить сколько раз можно полностью "уложить" (ориентация любая) меньший
прямоугольник n×m в исходный.
Возможно, для будущих ходоков будет интересно КАК.
Спасибо.    

Ответы

Ответ 1

Чистая эвристика: сделал модель с простым перебором на JS. В очередную точку пробует
поставить блок гор. или верт. Есть вариант с приоритетом вертикального положения, есть
с приоритетом горизонтального. 

Добавил случайность: каждый раз с вероятностью 50% выбирается приоритет гор. или
вертикального расположения очередного блока. С откатом на оставшийся вариант, если
«приоритетный» не влезает.

Забавно: наблюдаю, что с «хаосом» иногда получаются результаты лучшие, чем когда
выбран определённый вариант приоритета. Т.е. оптимум лежит в более сложном алгоритме.

Для размера «гаража» 320x278 и «машины» 12x56 я пока поймал максимум в 125:


P.s. потыкав и понаблюдав расстановки, интуитивно понял, что надо начинать из углов,
двигаясь к центру. Если кому не лень форкнуть и разобраться, дайте знать. Может, конкурс
устроить? Битву алгоритмов : )   Все пишут свои варианты. В назначенный день объявляем
конкурсный размер гаража и машины, и смотрим, кто найдёт максимум за меньшее время.


Ответ 2

Задачка решается просто.
Если нужен ответ на вопрос КАК
// Возвращает массив расположения блоков [ { x, y, w, h } ]
function calc(W, H, w, h) {

    var hor = pack([], W, H, w, h, 0, 0);
    var ver = pack([], W, H, h, w, 0, 0);

    // сортировка блоков в порядке сверху-вниз, слева-направо
    // если не планируется нумеровать блоки - можно удалить
    return (hor.length >= ver.length ? hor : ver).sort(function(a, b) {
        return (a.y - b.y) || (a.x - b.x);
    });

    function pack(pieces, W, H, w, h, x0, y0) {
        var x, y;
        var nx = W / w | 0;  // число блоков, умещающееся по ширине
        var ny = H / h | 0;  // по высоте
        var n = nx * ny;     // всего
        for (y = 0; y < ny; y++) for (x = 0; x < nx; x++) {
            pieces.push({ x: x0 + x*w, y: y0 + y*h, w: w, h: h });
        }
        if (W % w >= h && H >= w) {  // осталось полезное место справа
            pack(pieces, W % w, H, h, w, x0 + nx*w, 0);
        } else if (H % h >= w && W >= h) {  // осталось полезное место снизу
            pack(pieces, W, H % h, h, w, 0, y0 + ny*h);
        }
        return pieces;
    }

}

Если нужен ответ на вопрос СКОЛЬКО
// Возвращает число блоков
function calc(W, H, w, h) {

    return Math.max(pack(W, H, w, h), pack(W, H, h, w));

    function pack(W, H, w, h) {
        var n = (W / w | 0) * (H / h | 0);
        if (W % w >= h && H >= w) {
            n += pack(W % w, H, h, w);
        } else if (H % h >= w && W >= h) {
            n += pack(W, H % h, h, w);
        }
        return n;
    }

}

Демо: http://jsfiddle.net/RHq23/