CGAL users discussion list

[Sylvain Pion <>]

Hi Thomas,

Thomas Zangl - Home a écrit :
> I am building a regular triangulation_3 out of a set of points/radi
> contained in a file. 
>
> Some code:
>   dbl radius;
>   int vIdx = 0;
>   while ( iFile >> p ) {
>     iFile >> radius;
>     Rt_Weighted_point newPoint(p, radius*radius);
>
>     Rt_Vertex_handle vh = t.insert(newPoint);
>     vh->info() = vIdx;
>     cout << "Sphere: " << p << " r=" << radius << " index: " << vh->info() << 
> endl;
>     vIdx++;
>   }
>   iFile.close();
>
>   // check the triangulation
>   t.is_valid(true);
>
> Quite simple :)
>
> Now I iterate over the triangulation using the begin_facets() iterator:
>
>   Rt_Facet_iterator fIt = t.facets_begin();
>   Rt_Facet_iterator fEnd = t.facets_end();
>   if ( fIt == fEnd ) {
>     std::cout << "RegularTriangulation: no faces found" << std::endl;
>     assert(false);
>   }
>   else {
>     while(fIt != fEnd) {
>     ....
>     }
>
> The order how the facets are visited is different between the runs.
> For debugging, I need the same order for the same set of input points at
> different runs. Maybe the iterator starts at a random facet? How to
> avoid this behavior? 

This looks like a problem I already encountered this a few times.
I agree that it can be annoying for debugging.  The problem is that
there is a randomized algorithm which is involved, namely the point
location "stochastic walk".
This point location returns a cell/facet/edge/vertex, but for a facet
or edge, several representations are possible (a cell_handle plus 1
or 2 indices).  Depending on the randomization (the random generator
involved underneath), the representation which is returned can be
different.
The cell_handle is later used as starting point of the "find_conflict"
function which updates the triangulation for inserting the new point.
Since its starting cell is not the same, the memory layout later used
in the cell container can vary, and thus the iterators orders can
differ.

One way to fix that would be to use a pseudo random generator which
can be made deterministic.  But for debugging, it might be enough
to just derandomize the point location, by using the "i=0" instead of
the random number generator in the following code block from
<CGAL/Triangulaiton_3.h> :

        // For the remembering stochastic walk,
        // we need to start trying with a random index :
        int i = rng.template get_bits<2>();
        // For the remembering visibility walk (Delaunay only), we don't :
        // int i = 0;

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

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature