Pet123 122 Report post Posted August 11, 2008 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~~. 0 Share this post Link to post Share on other sites
Hodgman 51433 Report post Posted August 11, 2008 It's not quite the same problem, but this article describes a few different approaches to distributing random points inside a box with min distance. 0 Share this post Link to post Share on other sites
Trapper Zoid 1370 Report post Posted August 11, 2008 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. 0 Share this post Link to post Share on other sites
Drigovas 509 Report post Posted August 11, 2008 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. 0 Share this post Link to post Share on other sites
DvDmanDT 1941 Report post Posted August 11, 2008 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. 0 Share this post Link to post Share on other sites
MJP 19811 Report post Posted August 11, 2008 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. 0 Share this post Link to post Share on other sites