Efficiently Filtering Triangles within an Alpha Shape in CGAL

Question

I am currently working on a project that involves processing a large number of points using CGAL's Constrained Delaunay Triangulation and Alpha Shape functionalities. However, I am facing performance issues when filtering triangles that lie within an Alpha Shape using the classify method provided by the CGAL::Alpha_shape_2 class. As the number of points increases, the classification process becomes prohibitively slow.

Here's a snippet of the code I am using:

// Constrained Delaunay Triangulation
ConstrainedDelaunayTriangulation constrainedDelaunayTriangulation;
// Insert points into constrainedDelaunayTriangulation

// Compute the Alpha Shape
const AlphaShape2d alphaShape2d = calc2dAlphaShapeForPointCloud(points);

// Filter triangles within the Alpha Shape
for (ConstrainedDelaunayFacesIterator fit = constrainedDelaunayTriangulation.finite_faces_begin(), end = constrainedDelaunayTriangulation.finite_faces_end(); fit != end; ++fit) {
    const Point2d p1 = fit->vertex(0)->point();
    const Point2d p2 = fit->vertex(1)->point();
    const Point2d p3 = fit->vertex(2)->point();

    // Check if all three vertices of the triangle are inside the Alpha Shape
    const bool areAllVerticesInAlphaShape =
        (alphaShape2d.classify(p1) != AlphaShape2d::EXTERIOR) &&
        (alphaShape2d.classify(p2) != AlphaShape2d::EXTERIOR) &&
        (alphaShape2d.classify(p3) != AlphaShape2d::EXTERIOR);

    if (areAllVerticesInAlphaShape) {
        // Triangle is within the Alpha Shape
        // Further processing...
    }
}

I suspect that the classify method is the bottleneck, especially for a large number of points. I'm looking for more efficient ways to check if a triangle lies within the Alpha Shape.

Answer 1

I think if you try to classify points instead of vertices, it will first simulate an insert in the triangulation. You better directly use the vertex. Note that except if you are using the REGULARIZED mode, vertices are never exterior.