What is an algorithm to divide a rectangle into N number of square(ish) cells?-CodePudding

The

This would NOT be an example of keeping cell aspect ratios 1:1:

How would I work out the cell sizes and their x and y offset?

number of cells = 6 rectangle height = 600 rectangle width = 400 for each cell calculate cell height, width, xOffset, yOffset ???

Then I can loop through the cells and draw them:

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

CodePudding user response：

This method seems to work out at least as well as all your examples:

Consider MxN grids of increasing size until you get to the first one with at least enough cells. Start with 1x1, and repeatedly add a row or column depending on the resulting aspect ratio.

Let D be the difference between the number of cells you have and the number of cells you want. Reduce the number of cells by 1 in D rows or D columns, distributing the divisions evenly.

If you like, you can then rebalance the row widths or column heights to make sure that all cells have the same aspect ratio.

Here's an implementation in JavaScript. It will generate a different division every time you run it.

// 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>