CGAL users discussion list

[Sebastien Loriot <>]

A triangulation of a point set is a triangulation of the convex hull of 
the points. If some constrain edges are added, you then have the 
guarantee that those edges will be present in the triangulation of the
convex hull of your points.

If your constraints define a closed shape then you need a flooding like
algorithm to only pick the triangles that are inside the shape, like in
this example:

https://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2polygon_triangulation_8cpp-example.html

Best,

Sebastien.

On 3/13/22 02:46, Bob Bill ( via cgal-discuss Mailing 
List) wrote:
> I am given the vertices of a polygon, and I need to mesh it. I am 
> following one of the first examples in the CDT package documentation.
>
> The code is the following:
>
> #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_size_criteria_2.h>
> #include <CGAL/IO/write_VTU.h>
>
> #include <iostream>
> 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 CDT::Vertex_handle Vertex_handle;
> typedef CDT::Point Point;
>
> int main()
> {
>    CDT cdt;
>    Vertex_handle va = cdt.insert(Point(-1,-1));
>    Vertex_handle vb = cdt.insert(Point(-1,-0.25714));
>    Vertex_handle vc = cdt.insert(Point(-1.5,-1.4));
>    Vertex_handle vd = cdt.insert(Point(1.3,-1.2));
>    Vertex_handle ve = cdt.insert(Point(1.3,0.5));
>    Vertex_handle vf = cdt.insert(Point(1, 0.45714));
>    Vertex_handle vg = cdt.insert(Point(1, -1));
>
>    cdt.insert_constraint(va, vb);
>    cdt.insert_constraint(vb, vc);
>    cdt.insert_constraint(vc, vd);
>    cdt.insert_constraint(vd, ve);
>    cdt.insert_constraint(ve,vf);
>    cdt.insert_constraint(vf,vg);
>    cdt.insert_constraint(vg,va);
>    std::cout << "Number of vertices: " << cdt.number_of_vertices() << 
> std::endl;
>    std::cout << "Meshing the triangulation..." << std::endl;
>    // CGAL::refine_Delaunay_mesh_2(cdt, Criteria(0.125, 0.5));
>    std::cout << "Number of vertices: " << cdt.number_of_vertices() << 
> std::endl;
>
>    std::ofstream output("intersected_mesh.vtu");
>    CGAL::write_vtu(output, cdt);
>
> //Show the vertices of the triangulation
>      for(auto it = 
> cdt.finite_faces_begin();it!=cdt.finite_faces_end();++it){
>      std::cout << cdt.triangle(it) <<'\n';
>    }
> }
>
> If I look at the .vtu file, it seems to have the correct shape (see 
> attached image). However, after I printed the vertices for each 
> triangle, it appears that one element of the triangulation is also the 
> one with vertices
> (-1, -0.25714)
> (1, -1)
> (1, 0.45714)
>
> which should not be there since is not inside that polygon. Isn't this a 
> bug? If not, how can I create a mesh for which this is avoided? I mean, 
> I'd like to have all the triangles inside the domain.
>
> Best regards,
> Bob
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss