CGAL users discussion list

[Camille Wormser <>]

Dear Angelina,


 wrote:
> I'm using the kernel
> CGAL::Exact_predicates_inexact_constructions_kernel
> Checking the FAQ section I think that should be the problem, 

This kernel should not be the problem: in order to build the terrain 
triangulation, no new coordinates are ever constructed. The algorithm 
relies only on predicates evaluation at existing coordinates. You need 
an exact_constructions_kernel only if you need to evaluate the 
predicates on constructed data.

> though there are only two digits after the decimal... Is there an option, 
> which takes care of singular inputs? A more exact kernel would not solve my 
> problem I think if I can not guarantee that there are e.g. no squares.
>   

This kernel is exact, in the sense that it evaluates the sign of the 
predicates reliably. And this is all the algorithm needs. In particular, 
it is able to handle degenerated cases (singular inputs).

> CGAL error: precondition violation!
> Expr: !is_infinite(f) && !is_infinite(f->neighbor(i))
> File: triangulation_2.h
> Line: 860
>   

In fact, this is a bug in the precondition statements rather than in the 
algorithm itself!

The algorithms sometimes need to flip infinite faces, and this was 
forgotten when the preconditions were written. I'll submit a patch for 
this. In the meantime, you should simply comment out the last two 
precondtions in the flip(Face_handle f, int i) function:

 CGAL_triangulation_precondition( !is_infinite(f) &&  // REMOVE FROM 
HERE ------------
                  !is_infinite(f->neighbor(i)) );
 CGAL_triangulation_precondition(
                 orientation(f->vertex(i)->point(),
                 f->vertex(cw(i))->point(),
                 mirror_vertex(f,i)->point()) == RIGHT_TURN &&
                 orientation(f->vertex(i)->point(),
                 f->vertex(ccw(i))->point(),
                 mirror_vertex(f,i)->point()) ==  LEFT_TURN); // UNTIL 
HERE ----------

This bug will occur in the specific case where a point is inserted 
outside the convex hull AND removes at least one point from the convex hull.

> The problem occures only with specific input. The strange thing is that
> if I have a point cloud, which is OK to insert and shift it, then it's
> suddenly not OK any more, but the triangulation should be the same in
> both cases!
>   

This is typical of degenerated cases: in such cases, where you have aligned
vertices on the convex hull (at some point in your insertion procedure), 
shifting the vertices will introduce some imprecision so that the 
triangulation will change, because the points will now be seen as being 
in convex or concave position. So, you should NOT expect the algorithm 
to compute the same triangulation in both cases (but you should expect 
the algorithm not to crash, of course...).
--
Camille