> could you tell me the idea of the algo?


Sure. =)

Basically, I follow these steps, where n is the number of spheres needing
placement:
1. place n spheres randomly, ignoring collisions. Store their radii
separately.
2. sort the placement array by the X coordinate. I used mergesort.
3. for each element A in the array:
 - for each element B in the array that's after A:
 -- if A and B are too close to each other, abort the inner loop. A must be
replaced.
 -- if B's X coordinate is so far away from A that they can't possibly be
too close, abort the inner loop and continue to the next A.
 - (end inner loop)
 - if A needs to be replaced, keep trying random positions, until you find
one that doesn't conflict with any position already in the array. You can
make use of the sortedness of the array when testing these points for
collisions.

As more points are replaced, the algorithm slows down, since their new
positions have to be stored in a separate array, which isn't sorted. (They
can't remain in the original array, because keeping them in that would make
that array not sorted anymore.)

That's the gist of it.

- Slime
[ http://www.slimeland.com/ ]
[ http://www.slimeland.com/images/ ]

Post a reply to this message