CGAL users discussion list

[Mael Rouxel-Labbé <>]

For the record, this issue is discussed on the github of CGAL:
https://github.com/CGAL/cgal/issues/2924


On 13/03/2018 12:12, Arnold Song wrote:
> Has anyone else encountered an issue with degenerate faces in a
> Constrained Delaunay Triangulation?  
>
> I'm trying to generate a Delaunay triangulation of a square domain
> that has non-axis aligned sides.  When I run two refinement steps, the
> mesh contains 4 triangles, with 1 degenerate triangle with area 0.  I
> expect to have 3 triangles.  It appears that the degenerate triangle
> is generated with the star_hole when the new point in the refinement
> is inserted.  I haven't seen a place where there is a check for area 0
> (or very small area) triangles and subsequent removal.  Any
> suggestions would be wonderful.  
>
> Best,
> Arnold 
>
> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
> #include <CGAL/Constrained_Delaunay_triangulation_2.h>
>
> #include <CGAL/Delaunay_mesher_2.h>
> #include <CGAL/Delaunay_mesh_face_base_2.h>
> #include <CGAL/Delaunay_mesh_vertex_base_2.h>
> #include <CGAL/Delaunay_mesh_size_criteria_2.h>
>
> #include <CGAL/Voronoi_diagram_2.h>
> #include <CGAL/Delaunay_triangulation_adaptation_traits_2.h>
> #include <CGAL/Delaunay_triangulation_adaptation_policies_2.h>
>
> #include <CGAL/Boolean_set_operations_2.h>
>
> #include <CGAL/Cartesian_converter.h>
>
> typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
> typedef CGAL::Triangulation_vertex_base_2<K> Vb;
> typedef CGAL::Delaunay_mesh_face_base_2<K> Fb;
> typedef CGAL::Triangulation_data_structure_2<Vb, Fb> Tds;
> typedef CGAL::Constrained_Delaunay_triangulation_2<K, Tds> CDT;
> typedef CGAL::Delaunay_mesh_size_criteria_2<CDT> Criteria;
> typedef CGAL::Delaunay_mesher_2<CDT, Criteria> Mesher;
>
> typedef CGAL::Delaunay_triangulation_adaptation_traits_2<CDT>         
>        AT;
> typedef
> CGAL::Delaunay_triangulation_caching_degeneracy_removal_policy_2<CDT> AP;
> typedef CGAL::Voronoi_diagram_2<CDT,AT,AP>                           
>         VD;
>
> typedef CGAL::Exact_predicates_exact_constructions_kernel exactK;
> typedef K::Point_2 Point;
> typedef CGAL::Polygon_2<exactK> Polygon;
> typedef CGAL::Vector_2<K> Vector_2;
> typedef CGAL::Polygon_with_holes_2<exactK> Polygon_with_holes_2;
> typedef CGAL::Cartesian_converter<exactK,K> EK_to_IK;
>
>
>   // The constrained Delaunay triangulation (dual of the Voronoi)
>   CDT cdt;
>
>   cdt.insert_constraint(boundaryPts.begin(), boundaryPts.end(), true);
>
>   Mesher mesher(cdt);
>   mesher.init(false);
>   mesher.set_criteria(Criteria(0.25, 1.0));
>   std::cout <<"\nNumber of faces: " << cdt.number_of_faces() << "\n"
> << std::endl;
>
>   std::cout << "\nFirst refinement step:" << std::endl;
>   mesher.try_one_step_refine_mesh();
>   std::cout <<"\nNumber of faces: " << cdt.number_of_faces() << "\n"
> << std::endl;
>
>   std::cout << "\nSecond refinement step:" << std::endl;
>   std::cout << "Is refinement done: " << mesher.is_refinement_done()
> << std::endl;
>   mesher.try_one_step_refine_mesh();
>   std::cout <<"\nNumber of faces: " << cdt.number_of_faces() << "\n"
> << std::endl;