How can I place n circles randomly inside a rectangle without overlapping?

Question

Suppose I have n circles of radius r. I want to place them randomly inside a rectangle of size AxA.

It is guaranteed that they fit. One can suppose that the sum of the area of all circles is about 60% of the area of the rectangle.

I can try it by doing a backtracking, trying to place, going back, etc., but there should be a better way to do it.

Answer 1

One possibility is to generate random points inside the rectangle without further constraints, and then move the points/centres iteratively (by little steps) such that avoiding overlapping. If two points are too near one from each other, each point can bring pressure to the other, to make it going away a little bit. The higher the pressure, the higher the move.

This process was implemented in C++. In the following simple code, to facilitate implementation, points and vectors are represented par std::complex type.

Note that I used srandand rand for test purpose. You may used better random algorithms, depending on your constraints.

According to the tests that I have performed, convergence seems guaranteed for a density of 60%. I also made some tests with a density of 70%: sometimes convergence, sometimes not.

Complexity is O(n^2 n_iter), where nis the number of circles and n_iterthe number of iterations. n_iteris generally between 100 and 300, for a density of 60%. It could be decreased with relaxing the convergence criteria.

It could be seems high complexity, compared to other proposals in comments. In practice, for n = 15, the work is performed in less than 30ms on my PC. Huge time or fast enough, depending on the context. I have included a figure to illustrate the algorithm.

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>
#include <complex>
#include <cmath>
#include <tuple>
#include <ios>
#include <iomanip>

using dcomplex = std::complex<double>;

void print (const std::vector<dcomplex>& centers) {
    std::cout << std::setprecision (9);
    std::cout << "\ncenters:\n";
    for (auto& z: centers) {
        std::cout << real(z) << ", " << imag(z) << "\n";
    }
}

std::tuple<bool, int, double> process (double A, double R, std::vector<dcomplex>& centers, int n_iter_max = 100) {
    bool check = true;
    int n = centers.size();
    std::vector<dcomplex> moves (n, 0.0);
    double acceleration = 1.0001;        // to accelerate the convergence, if density not too large
                                        // could be made dependent of the iteration index
    double dmin;
    
    auto limit = [&] (dcomplex& z) {
        double zx = real(z);
        double zi = imag(z);
        if (zx < R) zx = R;
        if (zx > A-R) zx = A-R;
        if (zi < R) zi = R;
        if (zi > A-R) zi = A-R;
        return dcomplex(zx, zi);
    };
    int iter;
    for (iter = 0; iter < n_iter_max; ++iter) {
        for (int i = 0; i < n; ++i) moves[i] = 0.0;
        dmin = A;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                auto vect = centers[i] - centers[j];
                double dist = std::abs(vect);
                if (dist < dmin) dmin = dist;
                double x = std::max (0.0, 2*R*acceleration - dist) / 2.0;
                double coef = x / (dist + R/10000);
                moves[i] += coef * vect;
                moves[j] -= coef * vect;
            }
        }
        std::cout << "iteration " << iter << "  dmin = " << dmin << "\n";
        if (dmin/R >= 2.0 - 1.0e-6) break;
        for (int i = 0; i < n; ++i) {
            centers[i] += moves[i];
            centers[i] = limit (centers[i]);
        }
    } 

    dmin = A;
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            auto vect = centers[i] - centers[j];
            double dist = std::abs(vect);
            if (dist < dmin) dmin = dist;
        }
    }
    std::cout << "Final: dmin/R = " << dmin/R << "\n";
        
    check = dmin/R >= 2.0 - 1.0e-6;
    return {check, iter, dmin};
}

int main() {
    int n = 15;              // number of circles
    double R = 1.0;         // ray of each circle
    double density = 0.6;   // area of all circles over total area A*A
    double A;               // side of the square
    int n_iter = 1000;
    
    A = sqrt (n*M_PI*R*R/density);
    std::cout << "number of circles = " << n << "\n";
    std::cout << "density = " << density << "\n";
    std::cout << "A = " << A << std::endl;
    
    std::vector<dcomplex> centers (n);
    
    std::srand(std::time(0));
    
    for (int i = 0; i < n; ++i) {
        double x = R + (A - 2*R) * (double) std::rand()/RAND_MAX;
        double y = R + (A - 2*R) * (double) std::rand()/RAND_MAX;
        centers[i] = {x, y};
    }
        
    auto [check, n_iter_eff, dmin] = process (A, R, centers, n_iter);
    std::cout << "check = " << check << "\n";
    std::cout << "Relative min distance = " << std::setprecision (9) << dmin/R << "\n";
    std::cout << "nb iterations = " << n_iter_eff << "\n";
    print (centers);
    return 0;
}