将一个矩形分成 N 个正方形单元的算法是什么？

Question

我正在画布上绘制图像。我需要一种有助于放置图像的算法。

我试图保持单元格的长宽比为 1:1。这并不总是可能的，所以我们的想法是，在划分单元格时，如果长度大于宽度，则将长度除以一半，如果宽度大于长度，则将单元格除以宽度。

像这样的东西：

这不是保持单元格纵横比 1:1 的示例：

我如何计算像元大小及其 x 和 y 偏移量？

number of cells = 6
rectangle height = 600
rectangle width = 400

for each cell
  calculate cell height, width, xOffset, yOffset ???

然后我可以循环遍历单元格并绘制它们：

for each cell
  draw(xOffset, yOffset, width, height)

Answer 1

这种方法似乎至少和你所有的例子一样有效：

1. 考虑不断增加尺寸的 MxN 网格，直到到达第一个具有至少足够单元格的网格。从 1x1 开始，然后根据生成的宽高比重复添加行或列。

2. 令 D 为您拥有的单元格数量与您想要的单元格数量之间的差值。将 D 行或 D 列中的单元格数量减少 1，均匀分配分区。

如果愿意，您可以重新平衡行宽或列高，以确保所有单元格具有相同的宽高比。

这是 JavaScript 中的一个实现。每次运行它都会生成不同的分区。

// compute how far an aspect ratio is from square
function aspectError(w,h) {
  return Math.abs(Math.log(w) - Math.log(h));
}

// Calculate a pleasing division between two grids
// returns [average aspect error, division point]
function balance(
  numShort, // number of short rows/cols
  numLong,  // number of long rows/cols
  shortLen, // cells in short ones (long ones are +1)
  T, // transverse dimension
  L // lengthwise dimension
  ){
    // short aspect = div/numshort x L/shortLen
    // long aspect = (T-div)/numLong x L/(shortLen+1)
    // setting equal and solving gives
    // div/(T-div) = (shortLen+1)*numShort/(shortLen*numLong)
    let ratio = (shortLen+1)*numShort / (shortLen * numLong);
    // this point gives both grids the same aspect ratio
    let even =  T * ratio / (ratio+1);
    // Experimentally, this one is more pleaseing
    let div = T*numShort / (numShort + numLong);
    div = (div+even)/2;
    // calculate the average aspect error, plus a penalty for differing area
   
    let err = (
        aspectError(div/numShort,L/shortLen) + 
      aspectError((T-div)/numLong, L/(shortLen+1)) +
      2*aspectError((div/numShort)*(L/shortLen), ((T-div)/numLong)*(L/(shortLen+1)))
      )/2;
    return [err,div];
}

// compute a squarish subdivision
// returns a list of rectangular grids:
// [{x,y,w,h,xdivs,ydivs}]
function squarish(W,H,N)
{
    let xdivs=1
  let ydivs=1
  while(xdivs*ydivs < N) {
    let err1 = aspectError(W/xdivs, H/(ydivs+1));
    let err2 = aspectError(W/(xdivs+1), H/ydivs);
    if (err1 < err2) {
        ydivs+=1;
    } else {
        xdivs+=1;
    }
  }
  // number of rows/cols we have to shorten
  const D = xdivs*ydivs - N;
  if (D<=0) {
    return [{x: 0, y: 0, w: W, h: H, xdivs, ydivs}];
  }
  // decide whether to shorten rows or columns.
  // try both
  let bestCase = null;
  let bestErr = Number.MAX_VALUE;
  if (ydivs == D && xdivs > 1) {
    let err = aspectError(W/(xdivs-1), H/ydivs);
    if (err < bestErr) {
        bestErr = err;
      bestCase = [{x: 0, y: 0, w: W, h: H, xdivs: xdivs-1, ydivs}];
    }
  } else if (ydivs > D && xdivs > 1) {
    // shorten D rows
    // calculate the division point between short and long rows
    // that gives all cells the same aspect
    let [err,div] = balance(D, ydivs-D, xdivs-1, H, W);
    if (err < bestErr) {
        bestErr = err;
      bestCase = [
        {x: 0, y: 0, w: W, h: div, xdivs: xdivs-1, ydivs: D},
        {x: 0, y: div, w: W, h: H-div, xdivs, ydivs: ydivs-D}
      ];
    }
    }
  if (xdivs == D && ydivs > 1) {
    let err = aspectError(W/xdivs, H/(ydivs-1));
    if (err < bestErr) {
        bestErr = err;
      bestCase = [{x: 0, y: 0, w: W, h: H, xdivs, ydivs: ydivs-1}];
    }
  } else if (xdivs > D && ydivs > 1) {
    // shorten D cols
    // calculate the division point between short and long cols
    // that gives all cells the same aspect
    let [err,div] = balance(D, xdivs-D, ydivs-1, W, H);
    if (err < bestErr) {
        bestErr = err;
      bestCase = [
        {x: 0, y: 0, w: div, h: H, xdivs: D, ydivs: ydivs-1},
        {x: div, y: 0, w: W-div, h: H, xdivs: xdivs-D, ydivs}
      ];
    }
    }
  return bestCase;
}


let context = document.getElementById('canvas').getContext("2d");
context.strokeStyle="#000";

let W=(Math.random()-0.5)*(Math.random()-0.5)*1.9 + 0.5;
let H = 1-W;
{
    let fac = 300/Math.max(W,H);
  W *= fac;
  H *= fac;
}
let N=Math.floor(Math.random()*17+2);
for (const grid of squarish(W,H,N)) {
    for (let y=0; y<grid.ydivs; ++y) {
    for (let x=0; x<grid.xdivs; ++x) {
        let minx = grid.x + grid.w * x/grid.xdivs;
        let maxx = grid.x + grid.w * (x+1)/grid.xdivs;
        let miny = grid.y + grid.h * y/grid.ydivs;
        let maxy = grid.y + grid.h * (y+1)/grid.ydivs;
      context.strokeRect(minx+1, miny+1, maxx-minx, maxy-miny);
    }
  }
}

<canvas id="canvas" width="302" height="302">
This text is displayed if your browser does not support HTML5 Canvas.
</canvas>