Как подобрать размер прямоугольника заполняемого N одинаковыми прямоугольниками?

Question

Как подобрать размер прямоугольника заполняемого N одинаковыми прямоугольниками?

Рейтинг: 0Ответов: 1Опубликовано: 01.03.2023

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

Стороны результирующего прямоугольника должна быть степенью двойки. Желательно добиться того, чтоб результирующий прямоугольник был приближён к квадрату.

Все прямоугольники должны быть ориентированы по осям.

Меня хватило только на то, чтоб начать заполнять пространство и просто увеличивать размер при переполнении. Но при некоторых значениях на выходе получается уж слишком растянутый прямоугольник.

const nextPow2 = num => num > 0 && (num & num - 1) === 0 ? num : 1 << 32 - Math.clz32(num);

const textureSize = (w, h, count) => {
    let xw = nextPow2(w);
    let xh = nextPow2(h);
    let x = 0;
    let y = 1;

    for (let i = 0; i < count; i++) {
        x++;
        if (x * w <= xw) {
            continue;
        }
        if (x < y) {
            xw *= 2;
            continue;
        }
        y++;
        if (y * h > xh) {
            x = 0;
            xh *= 2;
        }
    }
    const col = Math.floor(xw / w);
    const row = Math.ceil(count / col);

    return [nextPow2(col * w), nextPow2(row * h), col, row];
};

console.log(textureSize(128, 10, 12));

javascript алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

Предложу вот такой вариант.

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

function getSquare(width, height, count) {
  const proportion = width / height;
  const pole = [[]];
  const [min, max] = proportion >= 1 ? [height, width] : [width, height];
  let curRow = 0;
  let cnt = count;
  while (cnt) {
    pole[curRow].push(1);
    if (pole[curRow].length * min + min > pole.length * max + max) {
      if (pole.length - 1 === curRow) {
        curRow++;
        pole.push([])
      }
    }
    if (curRow && pole[curRow].length === pole[0].length && !pole[curRow + 1]) {
      curRow = 0
    }
    if (pole[curRow + 1] && pole[curRow].length > pole[curRow + 1].length) {
      curRow++
    }
    cnt--;
  }
  console.log(`Размеры поля для ${count} прямоугольников ${width}x${height}
  Ширина: ${getBorderLen(proportion >= 1 ? pole[0].length * min : pole.length * max)} 
  Высота: ${getBorderLen(proportion >= 1 ? pole.length * max : pole[0].length * min)}
  `)
}

function getBorderLen(m, i = 1) {
  const x = 2 ** i;
  if (x < m) return getBorderLen(m, i + 1);
  return x;
}

getSquare(1, 10, 5)
getSquare(1, 10, 17)
getSquare(10, 1, 5)
getSquare(10, 1, 25)
getSquare(5, 10, 10)
getSquare(15, 13, 50)
getSquare(10, 2, 50)
getSquare(4, 5, 50)

Как подобрать размер прямоугольника заполняемого N одинаковыми прямоугольниками?

Ответы