CGAL users discussion list

[Andreas Fabri <>]

Hi Thomas,

I am not sure to understand Sylvain, so either he replies to a
question you didn't ask, or what he says has to do with what you
do, or he got it wrong.

The Facet_iterator iterates over all cells, and if the adress
of the cell is smaller than the adress of the neighbor cell,
this cell makes it into a Facet.  As adressses of cells are
different in each run you see the facet once from this side
and once from the other side.

In order to make it deterministic you have to write your
own iterator, or to patch ours, so that you decide which
of the two cells you want to favor. It could be an integer
id which you store in a Cell_base_with_info, or it could
be a geometric criterium , say, a finite cell wins over an
infinite one, and if both are finite you take the cell with
the lexicographical smaller opposite vertex.

andreas


Sylvain Pion wrote:
> 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;