如何将n个圆随机放置在一个矩形内而不重叠？

Question

假设我有n 个半径为r的圆。我想将它们随机放置在大小为A x A的矩形内。

保证它们适合。可以假设所有圆的面积之和约为矩形面积的 60%。

我可以通过回溯、尝试放置、返回等方式进行尝试，但应该有更好的方法来做到这一点。

Answer 1

一种可能性是在没有进一步约束的情况下在矩形内生成随机点，然后迭代地移动点/中心（小步），以避免重叠。如果两点距离太近，每一点都会给另一点带来压力，使其稍微远离。压力越大，动作就越高。

这个过程是用C++实现的。在下面的简单代码中，为了方便实现，点和向量都用parstd::complex类型表示。

请注意，我使用srand和rand进行测试。您可以使用更好的随机算法，具体取决于您的限制。

根据我进行的测试，60% 的密度似乎可以保证收敛。我还做了一些密度为70%的测试：有时收敛，有时不收敛。

复杂度为O(n^2 n_iter)，其中n是圈数和n_iter迭代次数。 n_iter对于60%的密度，一般在100到300之间。它可以通过放宽收敛标准来降低。

与评论中的其他提案相比，它可能看起来很复杂。实际上，对于n = 15，该工作在我的 PC 上执行时间不到 30 毫秒。时间长还是足够快，取决于具体情况。我提供了一张图来说明该算法。

#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;
}