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

Question

假设我有 n 个半径为 r 的圆。我想将它们随机放置在大小为 AxA.

的矩形内

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

我可以通过回溯、尝试放置、返回等方法来尝试，但应该有更好的方法来做。

Answer 1

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

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

请注意，我使用 srand 和 rand 进行测试。您可能会使用更好的随机算法，具体取决于您的约束条件。

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

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

与评论中的其他提案相比，它似乎非常复杂。实际上，对于 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;
}

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

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

algorithm

math

geometry