Packing known number of uniform-sized squares into a known rect

[momesana]

Hi,
A known number of uniform-sized squares must be packed into a container rectangle (that can but may not be a square) while making optimal use of the available area. The items are not rotated or otherwise distorted. They neither overlap each other nor do they go beyond the bounds of the container rectangle. Hence, it's the uniform size of the squares, that I am looking for. The equation (or rather inequality) that came right into my mind was this:

floor(w / s) * floor(h / s) >= n.

floor(w / s) * floor(h / s) >= n.

To copy to clipboard, switch view to plain text mode 

w,h and n are known! w is the width and h the height of the container rect and n the number of inner square items. Due to the occurrence of floor it seems like it is not possible to transform the inequality into a form that isolates s which is the length of a side of the inner squares.


Known parameters:

• The size (width and height) of the container rectangle.
• The number of inner square items.

Characteristics:

• items are squares
• all items share the same size
• items are not rotated or otherwise distorted
• items don't overlap
• items don't go beyond the bounds of the container rectangle

Wanted:

• The uniform size (or rather lenght of a side) of a square

.

I wrote a bruteforce function that uses a binary search to find an approximation of the value I am looking for. It uses about 10-15 iterations to get a result but I am looking for a more elegant solution, maybe in the form of a mathematical formula. Can someone point me towards the right direction?

Thanks in advance

p.s.: Save the provided attachment (or save the following code into a file main.cpp) and run qmake -project && qmake && make to compile it.

#include <QtGui>
#include <cmath>
#include <limits>
using namespace std;
 
class Widget : public QWidget
{
  Q_OBJECT
public:
  Widget(QWidget* parent = 0)
      : QWidget(parent)
      , m_piecesCount(0) {
    for (int i = 0; i < 100; ++i)
      m_colors << QColor(qrand() % 256, qrand() % 256, qrand() % 256);
  }
 
protected:
  void paintEvent(QPaintEvent* e) {
 
    Q_UNUSED(e);
 
    QStyleOption opt;
    opt.init(this);
    QPainter p(this);
    p.setRenderHints(QPainter::Antialiasing);
    p.translate(0.5, 0.5);
    style()->drawPrimitive(QStyle::PE_Widget, &opt, &p, this);
 
    QRectF container = contentsRect();
    container.adjust(container.width()  *  0.25,
                     container.height() *  0.25,
                     container.width()  * -0.25,
                     container.height() * -0.25);
 
    p.setPen(Qt::black);
    p.drawRect(container);
 
    const qreal spacing = 3;
    container.adjust(spacing, spacing, -spacing, -spacing);
    p.setPen(QPen(Qt::black, 1,  Qt::DashLine));
 
    if (container.width() < 1 || container.height() < 1)
      return;
 
    qreal side = squareSide(container, m_piecesCount);
    int rows = container.height() / side;
    int cols = container.width() / side;
    emit infoChanged(QString("Rows: %1\tCols: %2").arg(rows).arg(cols));
 
    for (int i = 0; i < m_piecesCount; ++i) {
      int r = i / cols;
      int c = i % cols;
 
      QRectF square(container.left() + c * side, container.top() + r * side, side, side);
      if (i < m_colors.size())
        p.setBrush(m_colors.at(i)); // just to make sure ;)
      p.drawRect(square);
 
      if (side > 14) // don't draw text if square is too small
	p.drawText(square, Qt::AlignCenter, QString::number(i));
    }
  }
 
public slots:
  void setPiecesCount(int count) {
    m_piecesCount = count;
    update();
  }
 
signals:
  void infoChanged(const QString&);
 
private:
  int m_piecesCount;
  QList<QColor> m_colors;
 
  // The function that needs to be improved!!!
  qreal squareSide(const QRectF& r, int piecesCount) {
  const qreal w = r.width();
  const qreal h = r.height();
  qreal top = qMin(w, h);
  qreal bottom = 1;
 
  while (top - bottom > 0.01) {
    qreal mid = bottom + (top - bottom) / 2;
    if (floor(w / mid) * floor(h / mid) < piecesCount)
      top = mid;
    else
      bottom = mid;
  }
 
  return bottom;
  }
};
 
class MainWindow : public QMainWindow
{
  Q_OBJECT
public:
  MainWindow(QWidget* parent = 0) : QMainWindow(parent) {
 
    m_widget = new Widget;
    connect(m_widget, SIGNAL(infoChanged(const QString&)), this, SLOT(updateStatusBar(const QString&)));
 
    m_spinBox = new QSpinBox;
    connect(m_spinBox, SIGNAL(valueChanged(int)), m_widget, SLOT(setPiecesCount(int)));
    m_spinBox->setRange(1, 100);
    m_spinBox->setValue(5);
 
    QWidget* cw = new QWidget;
    QVBoxLayout* lo = new QVBoxLayout;
    cw->setLayout(lo);
    lo->addWidget(m_widget);
    lo->addWidget(m_spinBox);
    setCentralWidget(cw);
 
    m_infoLabel = new QLabel;
    statusBar()->addPermanentWidget(m_infoLabel);
  }
 
public slots:
  void updateStatusBar(const QString& info) {
    m_infoLabel->setText(info);
  }
 
private:
  QLabel* m_infoLabel;
  QSpinBox* m_spinBox;
  Widget* m_widget;
};
 
int main(int argc, char** argv)
{
  QApplication app(argc, argv);
 
  MainWindow mw;
  qsrand(QTime::currentTime().msec());
  mw.show();
  return app.exec();
}
 
#include "main.moc"

#include <QtGui>
#include <cmath>
#include <limits>
using namespace std;

class Widget : public QWidget
{
  Q_OBJECT
public:
  Widget(QWidget* parent = 0)
      : QWidget(parent)
      , m_piecesCount(0) {
    for (int i = 0; i < 100; ++i)
      m_colors << QColor(qrand() % 256, qrand() % 256, qrand() % 256);
  }

protected:
  void paintEvent(QPaintEvent* e) {
    
    Q_UNUSED(e);

    QStyleOption opt;
    opt.init(this);
    QPainter p(this);
    p.setRenderHints(QPainter::Antialiasing);
    p.translate(0.5, 0.5);
    style()->drawPrimitive(QStyle::PE_Widget, &opt, &p, this);

    QRectF container = contentsRect();
    container.adjust(container.width()  *  0.25,
                     container.height() *  0.25,
                     container.width()  * -0.25,
                     container.height() * -0.25);

    p.setPen(Qt::black);
    p.drawRect(container);
    
    const qreal spacing = 3;
    container.adjust(spacing, spacing, -spacing, -spacing);
    p.setPen(QPen(Qt::black, 1,  Qt::DashLine));

    if (container.width() < 1 || container.height() < 1)
      return;

    qreal side = squareSide(container, m_piecesCount);
    int rows = container.height() / side;
    int cols = container.width() / side;
    emit infoChanged(QString("Rows: %1\tCols: %2").arg(rows).arg(cols));

    for (int i = 0; i < m_piecesCount; ++i) {
      int r = i / cols;
      int c = i % cols;

      QRectF square(container.left() + c * side, container.top() + r * side, side, side);
      if (i < m_colors.size())
        p.setBrush(m_colors.at(i)); // just to make sure ;)
      p.drawRect(square);
      
      if (side > 14) // don't draw text if square is too small
	p.drawText(square, Qt::AlignCenter, QString::number(i));
    }
  }

public slots:
  void setPiecesCount(int count) {
    m_piecesCount = count;
    update();
  }

signals:
  void infoChanged(const QString&);

private:
  int m_piecesCount;
  QList<QColor> m_colors;

  // The function that needs to be improved!!!
  qreal squareSide(const QRectF& r, int piecesCount) {
  const qreal w = r.width();
  const qreal h = r.height();
  qreal top = qMin(w, h);
  qreal bottom = 1;

  while (top - bottom > 0.01) {
    qreal mid = bottom + (top - bottom) / 2;
    if (floor(w / mid) * floor(h / mid) < piecesCount)
      top = mid;
    else
      bottom = mid;
  }

  return bottom;
  }
};

class MainWindow : public QMainWindow
{
  Q_OBJECT
public:
  MainWindow(QWidget* parent = 0) : QMainWindow(parent) {

    m_widget = new Widget;
    connect(m_widget, SIGNAL(infoChanged(const QString&)), this, SLOT(updateStatusBar(const QString&)));
    
    m_spinBox = new QSpinBox;
    connect(m_spinBox, SIGNAL(valueChanged(int)), m_widget, SLOT(setPiecesCount(int)));
    m_spinBox->setRange(1, 100);
    m_spinBox->setValue(5);

    QWidget* cw = new QWidget;
    QVBoxLayout* lo = new QVBoxLayout;
    cw->setLayout(lo);
    lo->addWidget(m_widget);
    lo->addWidget(m_spinBox);
    setCentralWidget(cw);

    m_infoLabel = new QLabel;
    statusBar()->addPermanentWidget(m_infoLabel);
  }

public slots:
  void updateStatusBar(const QString& info) {
    m_infoLabel->setText(info);
  }

private:
  QLabel* m_infoLabel;
  QSpinBox* m_spinBox;
  Widget* m_widget;
};

int main(int argc, char** argv)
{
  QApplication app(argc, argv);

  MainWindow mw;
  qsrand(QTime::currentTime().msec());
  mw.show();
  return app.exec();
}

#include "main.moc"

To copy to clipboard, switch view to plain text mode 

[pitonyak]

If you state that s must be an integer, then I guess that I missed it, so i will assume that it is not an integer.

You know that the total area is given by wh and that there are n squares. Divide wh by n and you have the maximum size for each square. So, you can set an upper bound on s as (s^2 <= w * h / n).

We are not using an integer for s, so we know that there will be an exact fit on either the width or the height. So, take the square root of (w * h / n) and set this to s.

Let a = w / s - floor(w/s)
Let b = h / s - floor(h/s)

No time to finish my thoughts, and I have not worked this out, but, I am thinking about reducing s such that either w / s or h / s is an integer (which should be a simple calculation). Uggg!

[pitonyak]

The entire floor thing is not correct I think. I believe the following to be true (assuming s is known):

w/s * floor(h/s) <= n <= w / s * ceiling(h/s) <= w / s * h / s = w*h / s^2

I think that I would explore an initial guess of s as D = sqrt(w * h / n), then do something silly like

We know that s <= D.

E = min(h / ceiling(h/D), w / ceiling(w/D))

E is designed such that either h/E or W/E is an integer. The point to note is that this provides a value for s such that it completely fills one of the dimensions. My guess is that (if there is no rounding) that this will provide you with the optimal solution.