Search code examples
c++cgal

CGAL is not computing a complete delaunay triangulation


I currently run into an error using the Delaunay triangulation of the CGAL library. I compute the triangulation as follows

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point;
typedef CGAL::Delaunay_triangulation_2<Kernel> DelaunayTriangulation;

auto triangulation = DelaunayTriangulation();
triangulation.insert(points.begin(),points.end());

Where points is a given vector of Points. I run the code over several instances and most of the time the triangulation is computed correctly. However sometimes (I cannot reproduce it for a certain instance) the triangulation only gives me a fraction of the expected faces. I implemented the following helper functions

auto face_count = [](DelaunayTriangulation &triangulation)
{
    std::size_t face_count = 0;
    for (auto it = triangulation.finite_faces_begin(); it < triangulation.finite_faces_end(); it++) {
        face_count ++;
    }

    return face_count;
};

auto is_correct = [&convex_hull_size, &face_count, &points](DelaunayTriangulation &triangulation)
{
    return face_count(triangulation) != 2*points.size() - convex_hull_size - 2;
};

to count the number of faces of the computed triangulation. In some cases, it is possible to recompute the triangulation on the same points which produce the correct amount of triangles. In other cases, however, I keep getting zero triangles which are really annoying.

My question is if someone has experienced similar errors when using CGAL and has an idea how I can debug it. Providing a minimal working example is hard due to the instance reading process.

EDIT:

For clarity: The following code

do
{
    triangulation = DelaunayTriangulation();
    triangulation.insert(points.begin(),points.end());
    std::cout << "Calculated triangulation with " << face_count(triangulation) << " faces the correct amount is " << 2*points.size() - convex_hull_size - 2 << std::endl;
} while(is_correct(triangulation));

produces the following output:

Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 11 faces the correct amount is 60
Calculated triangulation with 11 faces the correct amount is 60
Calculated triangulation with 11 faces the correct amount is 60
Calculated triangulation with 11 faces the correct amount is 60
Calculated triangulation with 11 faces the correct amount is 60
Calculated triangulation with 11 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 0 faces the correct amount is 60
Calculated triangulation with 60 faces the correct amount is 60

for some instances (but not always). For other instances, I repeatedly get 0 faces and the while loop does not terminate.


Solution

  • for (auto it = triangulation.finite_faces_begin(); it < triangulation.finite_faces_end(); it++)

    should be replaced by

    for (auto it = triangulation.finite_faces_begin(); it !=triangulation.finite_faces_end(); it++)