Constrained triangulation issue

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Constrained triangulation issue

Arnold Song
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;
Reply | Threaded
Open this post in threaded view
|

Re: Constrained triangulation issue

MaelRL
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;


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss