How to fill a fixed rectangle with square pieces entirely?

Question

Is this knapsack algorithm or bin packing? I couldn't find an exact solution but basically I have a fixed rectangle area that I want to fill with perfect squares that represents my items where each have a different weight which will influence their size relative to others.

They will be sorted from large to smaller from top left to bottom right.

Also even though I need perfect squares, in the end some non-uniform scaling is allowed to fill the entire space as long as they still retain their relative area, and the non-uniform scaling is done with the least possible amount.

What algorithm I can use to achieve this?

user_2144669 · Answer

There's a fast approximation algorithm due to Hiroshi Nagamochi and Yuusuke Abe. I implemented it in C++, taking care to obtain a worst-case O(n log n)-time implementation with worst-case recursive depth O(log n). If n ≤ 100, these precautions are probably unnecessary.

#include 
#include 
#include 
#include 

namespace {

struct Rectangle {
  double x;
  double y;
  double width;
  double height;
};

Rectangle Slice(Rectangle &r, const double beta) {
  const double alpha = 1 - beta;
  if (r.width > r.height) {
    const double alpha_width = alpha * r.width;
    const double beta_width = beta * r.width;
    r.width = alpha_width;
    return {r.x + alpha_width, r.y, beta_width, r.height};
  }
  const double alpha_height = alpha * r.height;
  const double beta_height = beta * r.height;
  r.height = alpha_height;
  return {r.x, r.y + alpha_height, r.width, beta_height};
}

void LayoutRecursive(const std::vector &reals, const std::size_t begin,
                     std::size_t end, double sum, Rectangle rectangle,
                     std::vector &dissection) {
  while (end - begin > 1) {
    double suffix_sum = reals[end - 1];
    std::size_t mid = end - 1;
    while (mid > begin + 1 && suffix_sum + reals[mid - 1] <= 2 * sum / 3) {
      suffix_sum += reals[mid - 1];
      mid -= 1;
    }
    LayoutRecursive(reals, mid, end, suffix_sum,
                    Slice(rectangle, suffix_sum / sum), dissection);
    end = mid;
    sum -= suffix_sum;
  }
  dissection.push_back(rectangle);
}

std::vector Layout(std::vector reals,
                              const Rectangle rectangle) {
  std::sort(reals.begin(), reals.end());
  std::vector dissection;
  dissection.reserve(reals.size());
  LayoutRecursive(reals, 0, reals.size(),
                  std::accumulate(reals.begin(), reals.end(), double{0}),
                  rectangle, dissection);
  return dissection;
}

std::vector RandomReals(const std::size_t n) {
  std::vector reals(n);
  std::exponential_distribution<> dist;
  std::default_random_engine gen;
  for (double &real : reals) {
    real = dist(gen);
  }
  return reals;
}

} // namespace

int main() {
  const std::vector dissection =
      Layout(RandomReals(100), {72, 72, 6.5 * 72, 9 * 72});
  std::cout << "%!PS
";
  for (const Rectangle &r : dissection) {
    std::cout << r.x << " " << r.y << " " << r.width << " " << r.height
              << " rectstroke
";
  }
  std::cout << "showpage
";
}

user_2521214 · Answer

Ok so lets assume integer positions and sizes (no float operations). To evenly divide rectangle into regular square grid (as big squares as possible) the size of the cells will be greatest common divisor GCD of the rectangle sizes.

However you want to have much less squares than that so I would try something like this:

try all square sizes a from 1 to smaller size of rectangle
for each a compute the naive square grid size of the rest of rectangle once a*a square is cut of it

so its simply GCD again on the 2 rectangles that will be created once a*a square is cut of. If the min of all 3 sizes a and GCD for the 2 rectangles is bigger than 1 (ignoring zero area rectangles) then consider a as valid solution so remember it.
after the for loop use last found valida

so simply add a*a square to your output and recursively do this whole again for the 2 rectangles that will remain from your original rectangle after a*a square was cut off.

Here simple C++/VCL/OpenGL example for this:

//---------------------------------------------------------------------------
#include 
#pragma hdrstop
#include "Unit1.h"
#include "gl_simple.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
class square                // simple square
    {
public:
    int x,y,a;              // corner 2D position and size
    square(){ x=y=a=0.0; }
    square(int _x,int _y,int _a){ x=_x; y=_y; a=_a; }
    ~square(){}
    void draw()
        {
        glBegin(GL_LINE_LOOP);
        glVertex2i(x  ,y);
        glVertex2i(x+a,y);
        glVertex2i(x+a,y+a);
        glVertex2i(x  ,y+a);
        glEnd();
        }
    };
int rec[4]={20,20,760,560}; // x,y,a,b
const int N=1024;           // max square number
int n=0;                    // number of squares
square s[N];                // squares
//---------------------------------------------------------------------------
int gcd(int a,int b)        // slow euclid GCD
    {
    if(!b) return a;
    return gcd(b, a % b);
    }
//---------------------------------------------------------------------------
void compute(int x0,int y0,int xs,int ys)
    {
    if ((xs==0)||(ys==0)) return;
    const int x1=x0+xs;
    const int y1=y0+ys;
    int a,b,i,x,y;
    square t;
    // try to find biggest square first
    for (a=1,b=0;(a<=xs)&&(a<=ys);a++)
        {
        // sizes for the rest of the rectangle once a*a square is cut of
        if (xs==a) x=0; else x=gcd(a,xs-a);
        if (ys==a) y=0; else y=gcd(a,ys-a);
        // min of all sizes
                          i=a;
        if ((x>0)&&(i>x)) i=x;
        if ((y>0)&&(i>y)) i=y;
        // if divisible better than by 1 remember it as better solution
        if (i>1) b=a;
        } a=b;
    // bigger square not found so use naive square grid division
    if (a<=1)
        {
        t.a=gcd(xs,ys);
        for (t.y=y0;t.y


And preview for the actually hardcoded rectangle:

The number 8 in Caption of the window is the number of squares produced.
Beware this is just very simple startup example for this problem. I Have not tested it extensively so there is possibility once prime sizes or just unlucky aspect ratios are involved then this might result in really high number of squares... for example if GCD of the rectangle size is 1 (primes) ... In such case you should tweak the initial rectangle size (+/-1 or whatever)
The important thing in the code is just the compute() function and the global variables holding the output squares s[n]... beware the compute() does not clear the list (in order to allow recursion) so you need to set n=0 before its non recursive call.
To keep this simple I avoided to use any libs or dynamic allocations or containers for the compute itself...

How to fill a fixed rectangle with square pieces entirely?

2 Answers