CGAL users discussion list

[<>]

hi

general problem description:
----------------------------------------
I experience a basic problem with the triangulation method of CGAL. Id need a
2D delaunay triangulation of a domain. (constrained/confirmed is not important
at this stage ). CGAL does not obey the constraints of the domain boundary.

a more detailed view of the problem:
--------------------------------------------------
consider the following point set: 
#: x y
1: 0 1
2: 0 2
3: 2 2
4: 2 0
5: 1 0
6: 1 1

and followed the wished connection list of the boundary of my PSLG:
1: 1 2
2: 2 3 
3: 3 4 
4: 4 5 
5: 5 6 
6: 6 1

The problem is that CGAL produces (by using the basic triangulation ) 5
triangles, where 4 of the 5 triangles are within the mentioned PSLG and the
fifth is outside, consisting of the following points:
wrong triangle: 1-6-5
or the points: 0 1 - 1 1 - 1 0

in other words: the meshing process generates a triangle outside my given
constraints. 

my approach:
-------------------
I am using a fairly simple meshing procedure, followed the important parts of
my code:

--------------------------------------------------------------------------------------------------------------------------
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>

struct K : public CGAL::Exact_predicates_inexact_constructions_kernel {};
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;

cdt.insert_constraint(Point( 0, 1 ), Point( 0, 2 ));
cdt.insert_constraint(Point( 0, 2 ), Point( 2, 2 ));
cdt.insert_constraint(Point( 2, 2 ), Point( 2, 0 ));
cdt.insert_constraint(Point( 2, 0 ), Point( 1, 0 ));
cdt.insert_constraint(Point( 1, 0 ), Point( 1, 1 ));
cdt.insert_constraint(Point( 1, 1 ), Point( 0, 1 ));

assert(cdt.is_valid());
--------------------------------------------------------------------------------------------------------------------------

A constrain verification by the CDT::Finite_edge_iterator yields the correct
number of constrained edges:
--------------------------------------------------------------------------------------------------------------------------
int count = 0;
for (CDT::Finite_edges_iterator eit = cdt.finite_edges_begin(); eit !=
cdt.finite_edges_end(); ++eit)
        if (cdt.is_constrained(*eit)) ++count;
std::cout << "constrained edges: " << count << std::endl;
--------------------------------------------------------------------------------------------------------------------------
--> 6 .. this output outlines, that the constraints are there, but not
recognized / obeyed as a boundary of the meshing domain. 

Apparently I miss something serious here, but after reading the parts of "2D
Triangulations" and "2D Conforming Triangulations and Meshes" of the manual a
few times, I am not able to answer this on my own. I hope anybody would be so
kind and help me out.

Id greatly appreciate your time spent on this problem!

thanks in advance,
regards, 
Josef Weinbub