CGAL users discussion list

Andreas Fabri wrote:
> Hi Thomas,
>
> I am not sure to understand Sylvain, 

I could not understand either when I read his explanation. The trick is 
that, in degenerate cases when a new point is located on an edge or 
facet, this edge or facet is returned by locate, and this result is 
deterministic of course, but its representation is not unique and 
depends on which cell we look at this edge or facet from, and this 
depends on the "stochastic walk".
Then find_conflicts, which returns a deterministic output too, does not 
return the cells in the same order, depending on the cell that is 
considered for the starting edge or facet.
So, the insertion of the new point does not delete and create cells in 
the same order. So, cells are not stored the same order in the container.

> Sylvain Pion wrote:

> > > > 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.