Optimization of points generating inside a sphere

Hello,

A few days ago I asked a questions about code optimization and recieved a good answer ( https://www.mathworks.com/matlabcentral/answers/1769225-generating-a-matrix-of-coordinates-without-certain-values ).

I want to generate points inside a sphere where they have minimal distance between them, the answer in the previous forum did a much better job than what I had.

However, once you set the minimal distance between points to be 40 units and as I want 80k points inside my sphere, the algorithm becomes very slow. As I believe the "rand" function has trouble generating coordinates that haven't been occupied by other points.

I need a way to get a high amount of points inside a sphere (about 80k points) quicker. any ideas are welcome

I though about creating a range of coordinates using "meshgrid" function for x,y,z for all possible point coordinates, and once I pick a point I can delete all other points that are within a forbidden range, yet have some problem implemanting that and would appreciate some help.

[Torsten]

How many "units" is the radius of the sphere if the points shall be at least 40 units apart ?

Are you sure there is enough room for 80000 points, even with closest packing ?

If you use "meshgrid" to create the points, they are no longer random. Does that matter ?

[Nicola Seraphim]

Volume wise 80000 "spheres" of radius 20 do fit in a sphere of radius 1000 (should have mentioned the large radius...) so it should be possible.

concerning the "meshgrid", I want to make a large grid of points where I can choose using "Randperm" the index to a center point, this is random enough for my case atleast. I though about randperm so it won't choose the same index twice

[Torsten]

I think a packing density of 64 % that you postulate is too high in value. Random packing in three dimensions without the restriction that the centers are inside a sphere only has a packing density of 63.5 %:

https://en.wikipedia.org/wiki/Sphere_packing

[Torsten]

Maybe of interest:

https://www.sciencedirect.com/science/article/pii/S2352711022000437

Perhaps you can use a dirac delta distribution with complete mass at r = 20 in the code to generate the spheres.

Answer 1

[John D'Errico]

The common scheme that is advised is to generate points randomly, then if a point is too close to a neighbor, then you reject it. That works great for a few dozen points, or even a hundred or so, depending on the density you are looking to find. Think of it like this:

Suppose I have a unit cube, so a cube that is one unit per side. Now, I wish to stuff points inside there, so that no point is within a distance of 0.1 units from any other point? Essentially, that mean NO other point can occupy a sphere of radius 0.1 around the point you have chosen. What is the volume of a unit cube? That one is easy, the volume is 1. What is the volume of a sphere, of radius 0.1? Lets see if I remember...

Rsphere = 0.1;
Vsphere = 4/3*pi*Rsphere^3

Vsphere = 0.0042

So how many spheres can I pack (roughly) into a unit cube?

1/Vsphere

ans = 238.7324

Admittedly, that makes no assumptions about hexagonal close packing. But it does give me a rough estimate of the MAXIMUM number of points I could pack into a unit cube. The problem is, as we get near that limit, it becomes less and less likely that any given randomly generated point will happen to fall into a hole where no sphere is already placed. And worse, the previous points were not generated according to any kind of close packing either, so the number of spheres we can pack into that cube will surely be less than the number I predicted above.

My point in all of this is, those rejection schemes are just atrociously slow, when you need to generate anything like a dense packing. If you try it, and find them getting slow, then you are out of luck. There is no magic when you follow that path. Things will just get abysmal.

Is there a better way? Well, yes, possibly so. There probably is some room for improvement. What you might do is to start with a randomly generated sample. Now for every point, imagine a repulsive force on each point that is proportional to the square of the distance to all of its neighbors. That force goes to zero for any point, IF the distance is greater then 0.1 unit. Now perturb every point, in the direction of the aggregate force on that point. Iterate in this process until all points lie sufficiently far apart, when you can now stop.

[Torsten]

@John D'Errico

Just an idea or do you have code for this ?