Finding random k points at least d apart in 3D confined space

Question

For my simulation purposes, I want to generate a randomly distributed k number of spheres (having the same radii) in a confined 3D space (inside a rectangle) where k is in order of 1000. Those spheres should not impinge on one another.

So, I want to generate random k points in a 3D space at least d distance away from one another; considering the number of points and the frequency at which I need those points for simulation, I don't want to apply brute force; I'm looking for some efficient algorithms achieving this.

Can you please give more context and tell you about what is E3? — Deepak Tatyaji Ahire, Apr 29 '21 at 03:39
Does this answer your question? [generate 3-d random points with minimum distance between each of them?](https://stackoverflow.com/questions/14780328/generate-3-d-random-points-with-minimum-distance-between-each-of-them) — Peter O., Apr 29 '21 at 03:59
@mnulb while writing I realised that I didn't have a good feeling for what you were after, adding details to the question would help giving a more appropriate answer — Sam Mason, Apr 29 '21 at 10:52

score 0 · Answer 1 · answered Apr 29 '21 at 10:50

How about just starting with some regular tessellation of the space (i.e. some primitive 3d lattice) and putting a single point somewhere in each tile? You'd then only need to check a small number of neighboring tiles for proximity.

To get a more statistically uniform, i.e. less regular, set of points, you could:

perturb points in space
generate an overly dense lattice and reject some points
"warp" the space so that the lattice was more dense in certain areas

You could perturb the points sequentially, giving you a monte-carlo chain over their coordinates, and potentially saving work elsewhere. Presumably you could tailor this so that the equilibrium distribution was what you wanted.

Finding random k points at least d apart in 3D confined space

1 Answers1