randomly place N spheres in volume

[PhysicsIsFun]

Hello there.

This time, I need to put N spheres with given radius R randomly in a Volume [-0.5,0.5]^3, without any overlap of spheres.

If I choose values so that all the spheres will occupy ~57% of the total volume (the maximal theoretical possible value is ~64%), I find it difficult to get results.
The basic scheme to place the i-th particle after i-1 particles have been placed:
-choose random position
-check for overlap with any other sphere
-if(overlap): check new randomly chosen position
-repeat until i has been placed
-place next particle

However, the more particles have been placed, the less likely my random generator will find a position with enough space AND the more time the overlap check needs. For N=500, R=0.5/7.7, the algorithm is barely able to place 340 particles (overlap is called billions of times at this point).

  #include <vector>
#include <random>
#include <iostream>
#include "particle.h"
#include "hard_sphere_overlap_index.h"
#include "random_positions_hard_spheres.h"

using namespace std;

//this function places N hard spheres of radius R on random coordinates in a [-0.5,0.5]^3 box
vector <particle> random_positions_hard_spheres (int N, double R){

    vector <particle> positions;

    static seed_seq seed_sequence { 100, 78639, 193, 55555, 3, 2348089, 6474367, 264441578 };
    static mt19937 gen (seed_sequence);
    uniform_real_distribution<double> random_double(-0.5, 0.5);
    double x,y,z;
    double d=2*R;

    for(size_t i=0; i<N; ++i){

        x=random_double(gen);
        y=random_double(gen);
        z=random_double(gen);

        positions.push_back({x,y,z});

        //find position with no overlap
        int j=0;
        while(overlap_index(positions, i, d)){

            positions[i]={random_double(gen), random_double(gen), random_double(gen)};
            ++j;
        }
        cout <<"overlap was called "+to_string(j)+" times"<<endl;
        cout <<"particle "+to_string(i)+" was placed"<<endl;

    }

    return positions;
}

Does anyone have an idea on how to do this better?

Regards!

[Repeater]

How does your overlap checking function work? A k-d tree can be used to make an efficient overlap detector; https://en.wikipedia.org/wiki/K-d_tree

[helios]

A random placement will very probably produce a very inefficient distribution, such that placing a specific number of spheres will be increasingly difficult the closer that number is to the theoretical maximum number.

Forget about spheres for a moment and let's reduce the problem to one dimension.
We have a 1 m length and we need to place three 0.3 m strips at random without any overlap.
1. After a random roll, I place the first strip at [0.2-0.5]
2. After a random roll, I place the second strip at [0.7-1]
Whoops! It's now completely impossible to place the last strip anywhere, because the largest gap is only 0.2 m wide, even though in total we have 0.4 m available.

Your 64% density figure assumes a randomization method different than what you're using, where the spheres are poured into a volume and the volume is shaken so that the spheres settle into a more compact configuration. You simply spawn your spheres in your volume without even letting them drop until they hit something.

[PhysicsIsFun]

@Repeater
My overlap function still sucks. I will have to improve it, but I believe in this problem, my approach with the random generator will not work out (no matter how good the overlap function gets, it will have to be called billions over billions of times).
But thank you for the link, I will look into it (and mb open another thread if I have^^").

@helios
Thank you for that insight. I assumed there might be a fundamental flaw in that approach, even though it should be possible to create "random close packing" of up to 64%.
But certainly not like this...

It's ok then, I intended to use that configuration as an initial state to test the validity of my simulation, but it seems like this is not so trivial (in fact, I have come across research papers that deal with this problem^^).