CGAL users discussion list

[Mariette Yvinec <>]

Eivind LM wrote:

> Greetings,
> I'm completely new to CGAL, and am trying to model a 2D terrain surface in 3D 
> using Triangulation_2 and Triangulation_euclidean_traits_xy_3. My application 
> requires me to add points to an existing triangulation.
>
> During insertion of points, I get an assertion error which to me indicates 
> that the triangulation has become invalid at some point.
>
> But as far as I have understood the documentation I should be able to insert 
> vertices at any point in a triangulation, and CGAL should keep the 
> triangulation valid. Is this correct? Please find below example code to 
> reproduce my problem.
>
> Best regards,
> Eivind Lyche Melvaer
>
> Sample code to reproduce the assertion failure, using CGAL version 3.3.3:
> #include <CGAL/basic.h>
> #include <CGAL/Triangulation_euclidean_traits_xy_3.h>
> #include <CGAL/Triangulation_2.h>
> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
>
>
> typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
> typedef Kernel::Point_3                                     Point_3;
> typedef CGAL::Triangulation_euclidean_traits_xy_3<Kernel>   
> TriangulationTraits;
> typedef CGAL::Triangulation_2<TriangulationTraits>          Triangulation;
>
>
> int main(int argc, char** argv)
> {
>  Triangulation t;
>
>  //Add two triangles, to represent a coarse triangulation of the unit square
>  t.insert(Point_3(0, 0, 0));
>  t.insert(Point_3(1, 0, 0));
>  t.insert(Point_3(0, 1, 0));
>  t.insert(Point_3(1, 1, 0));
>
>  int numi = 10;
>  int numj = 10;
>
>  //Then a 10x10 grid of vertices within the unit square are inserted.
>  for(int i = 0; i < numi; i++) {
>    for( int j = 0; j < numj; j++) {
>      std::cout << i << " " << j << std::endl;
>      double x = i*1.0/(numi-1);
>      double y = j*1.0/(numj-1);
>      double z = 0;
>      t.insert(Point_3(x, y, z));
>    }
>  }
> }
>
> The assertion failure:
> CGAL error: precondition violation!
> Expr: oriented_side(f,p) == ON_POSITIVE_SIDE
> File: /mn/sarpanitu/ansatte-u21/eivindlm/env/include/CGAL/Triangulation_2.h
> Line: 920
> terminate called after throwing an instance of 'std::logic_error'
>  what():  basic_string::_S_construct NULL not valid
> Aborted
>  
I got the same error on my computer.
This failure comes from a numerical problem  since it disappears if you 
replace,
in both the include and typedef line :

Exact_predicates_inexact_constructions_kernel
by
Exact_predicates_exact_constructions_kernel

Obviously this Delaunay triangulation should not require
a kernel with exact constructions. The problem
is that, as it is coded now, the predicates are not exact
when the kernel are instantiated with 
Exact_predicates_inexact_constructions_kernel.
Thanks for reporting the bug.