"Slime" <noo### [at] hotmailcom> wrote in message
news:3cbe1713$1@news.povray.org...
> > So I wonder, if there are other, more advanced algorithms out there,
which
> are
> > faster ...
>
> Here's an idea I just came up with.
>
> Do it just like you are. Except, as you place the spheres, keep the array
> that holds their positions *sorted*. So, when you add a new value to the
> array, use some sort of binary search to find the part of the array where
> the new position should be kept. (To sort the array, do something like
> sorting first in the X direction, and then in the Z direction.) Then
insert
> the new value there, pushing the rest of the values ahead.
>
> Then, when you have a new position, you still have to check the array to
> make sure it doesn't conflict with any of the positions already there.
> However, you no longer have to check the whole array - you only have to
> check the part of the array that's within twice the maximum possible
radius
> from the new position you're testing.
>
> It might be difficult to implement, but it might really speed it up. The
key
> thing here is to search the array with a binary search or something else
> that takes advantage of its sortedness.

this page http://www.ulib.org/webRoot/Books/Numerical_Recipes/bookcpdf.html
has some very, very useful algorithms.
It's basically an on-line version on a book I have used many times. There's
a few sorting algorithms in section 8, but there's much more here as well.
Quite possibly, there are many people who've used this book, but the online
resource is nice.
I've posted the C version but it's also available in Fortran (the on I use).

jim

Post a reply to this message