CGAL users discussion list

[Sylvain Pion <>]

Matthijs Sypkens Smit wrote:
> I came across the following: when I create a instance of a 
> Random_points_in_sphere_3 generator with a fixed random seed, then the 
> points are the same every time, except when I instantiate a Delaunay 
> triangulation before the creation of the points. Here is some code (I have 
> attached the complete code):
> int main( )
> {
>     Triangulation dt;
>
>     for (int i = 0; i < 5; i++) {
>         std::cout << *pgen << std::endl;
>         pgen++;
>     }
>
>     return 0;
> }
>
> This program produces points with different coordinates each time it is 
> run. When I uncomment the line 'Triangulation dt;', then the output is 
> always the same.
>
> I suspect that one is supposed to be able to build a Delaunay triangulation 
> of random, but reproducible, numbers. Therefore I assume this might be a 
> bug. Can anyone confirm that the expected behaviour is that the randomly 
> generated points are identical on each run? Can the problem be reproduced?
>
> I have not bothered to investigate the problem beyond isolating it. I 
> presume, assuming that this is a bug, that the Delaunay triangulation 
> makes some use of random numbers at initialisation, but this probably 
> should not affect anything outside the Triangulation object itself.

You guessed right that CGAL::Random is also used by
Delaunay_triangulation internally (for randomized algorithms purposes,
since the output is deterministic).  CGAL::Random simply calls the
standard rand() function, which unfortunately uses a global state.
I guess the best long term fix would be to switch to the random number
generators defined in TR1 (part of the next C++ standard).

There is a second issue here, which is that the random number generator
inside Delaunay_triangulation is default constructed, which calls
time() to get a non-deterministic (well, non-constant) seed...
And there is no control over that.

Depending on what you need, the easiest thing to do is to pass a
CGAL::Random object to the constructor of
Delaunay_triangulation_3 (and down to its Triangulation_3 base class).
Note that if you use Triangulation_hierarchy_3, there is the same
problem there...

If you really need separate random states, then it's harder, since
rand() must be replaced by something that supports a state
(drand48_r() does it, but is probably not portable).

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project
CGAL, http://cgal.org/