Sign in to follow this  
Pet123

distrbute 100 points inside a sphere with min distance

Recommended Posts

Pet123    122
hi there at the moment the only way i can think of to distribute 100 points inside a sphere (the distance between any two points must be greater than some value) is this (brutle force and slow)
for (int i = 0; i < 100; ++i)
{
    do
	{
	    const float3 pos = random_pos_inside_the_sphere()
	    const bool ok = check_distance_with_existing_positions(pos, min_distance)

	} while (!ok);	
}

would anyone here please share your thoughts to complete this task with better solution? the one i came up with here is obviously slow, thanks a lot~~.

Share this post


Link to post
Share on other sites
Trapper Zoid    1370
One kernel of an idea that sprung to my mind would be to model the points as like little electrons with a repelling force between them (in your case with a cutoff of the force if the points are beyond a certain point) and then run a simple simulation until the points are acceptable.

Share this post


Link to post
Share on other sites
Drigovas    509
Well, your question isn't asking for 'random' points... so i'm going to assume that mostly ordered points are sufficient, with potential for slight random variability.

There are an awful lot of possible configurations that could very well lead to an impossible solution with this sort of random placement [or even a very organized placement, with sphere sizes and min distances that could not ever yield a valid solution]. So how about this instead: Come up with a uniform and consistent arrangement of points that are packed together as tightly as possible. This way, you'll know upfront whether or not your sphere can even contain the points with the specified min distance, since you know how much space those points will consume. If the sphere is bigger, and you're looking for some randomness, expand this arrangement and it'll leave you some room to wiggle each individual point around. I don't have the time at the moment to hack the math out to prove optimality, but I'd imagine a good primitive shape to start with would be a figure consisting of 4 points arranged so that if these points outlined a solid, this solid would be a figure composed of 4 equilateral triangles [if only because a 'grid' of these triangles is pretty trivially provable as being optimal point density on a 2d plane].

But really, choose-and-check is a bad way to go. Start with one point, and place another point that is 'min_distance' point away, and then a third point that is 'min_distance' from both, then a 4th..... [this pattern would result in a grid of equilateral triangular solids]. This should be a very orderly procedure.

Share this post


Link to post
Share on other sites
DvDmanDT    1941
Think of all points as spheres with a radius of min_distance/2, then add one at a time, as close as possible to the center of the big sphere. If you want to, you can increase the size of the points even more, then, when all points are placed, shrink them to the min_distance/2 and move them around some to create some randomness. Should work, but I'm not sure how to find the closest possible point to the center. I'm guessing there's a fairly simple way to do this though, possibly using alot of trig though.

Edit: This is probably pretty much what Drigovas is talking about as well.

Share this post


Link to post
Share on other sites
MJP    19753
Just generate random spherical coordinates, with rho >= min distance and =< max distance. The only trick to that is that you will get an uneven distribution (points will "clump" at the poles) if you generate phi coordinates that are between 0 and 2 * pi. I forget exactly how to fix this, but I'm about 90% sure that you get a nice distribution if you generate cos(phi) directly.

I have code that does this at home, I'll check later and post it.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this