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

Question

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

algorithmmathgeometry

4

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

保证它们可以放下。我们可以假设所有圆的面积总和约为矩形面积的60%。

我可以通过回溯法尝试放置，不断尝试，但应该有更好的方法来解决这个问题。

- Daniel

1

另一种表述问题的方式可能是“如何选择一个随机点，使其距离现有集合中的任何点至少为r？”（我不知道比你建议的更好的技术） - Jeremy Friesner

1

我会说，在朴素的方法中，执行检测相交的数量是_O(n^2)_，因此基本上你正在寻找更快的方法来完成它，对吗？ - Alessandro Jacopson

4

把n个相同半径的圆密集地排列在矩形中，然后随机地放置半径为r的圆。 - user1196549

2

@YvesDaoust 这是一种非常高效的方法，而且实现起来相当容易。优点/缺点（？）是分布会相当均匀，例如很少有圆形互相接触。OP可能需要详细说明他们所谓的“随机”。 - Damien

2

无论如何，这个问题都很难，因为你可能会得到一个输入，其中n个圆几乎根本不适合，或者只有一种适合的方式。换句话说，这个问题可以归结为圆装箱问题。因此，在最坏的情况下，我不认为已知有效的算法。例如，如果我给你 n = 15, r = 1 and A = 4 + sqrt(2) + sqrt(6)，你必须能够生成这个：https://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/15_circles_in_a_square.svg/512px-15_circles_in_a_square.svg.png - orlp

显示剩余10条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Damien · Accepted Answer

一种可能的方法是在矩形内随机生成点而不加限制，然后通过小步迭代移动点/中心以避免重叠。如果两个点彼此太近，则每个点可以对另一个点施加压力，使其稍微远离一点。压力越大，移动距离就越大。这个过程是用C++实现的。在以下简单的代码中，为了方便实现，点和向量采用std::complex类型表示。请注意，我使用了srand和rand进行测试目的。根据您的约束条件，您可以使用更好的随机算法。根据我进行的测试，对于密度为60％，收敛似乎是有保证的。我还进行了一些密度为70％的测试：有时收敛，有时不收敛。复杂度为O(n^2 n_iter)，其中n是圆的数量，n_iter是迭代次数。对于密度为60％，n_iter通常在100到300之间。通过放宽收敛标准，可以将其减少。

与评论中的其他提案相比，它可能看起来非常复杂。实际上，对于 n = 15，在我的电脑上可以在不到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;
}