如何在矩形內隨機放置n個圓圈而不重疊？

假設我有n個半徑為r的圓。我想將它們隨機放置在大小為A x A的矩形內。

保證它們適合。可以假設所有圓的面積之和約為矩形面積的 60%。

我可以通過回溯、嘗試放置、回傳等來嘗試，但應該有更好的方法來做到這一點。

uj5u.com熱心網友回復：

一種可能性是在沒有進一步約束的情況下在矩形內生成隨機點，然后迭代地（通過小步驟）移動點/中心以避免重疊。如果兩點距離太近，每一點都會給對方帶來壓力，讓它稍微遠離一點。壓力越高，移動就越高。

這個程序是用 C 實作的。在下面的簡單代碼中，為了方便實作，點和向量都用parstd::complex型別表示。

請注意，我使用srandandrand用于測驗目的。您可能會使用更好的隨機演算法，具體取決于您的約束。

根據我進行的測驗，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;
}

標籤：

上一篇：將公式從Java移植到PHP的問題

下一篇：如何將一個角度移近另一個角度？