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.

score 1 · Accepted Answer · answered Jul 18 '23 at 07:11

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.

answered Jul 18 '23 at 07:11

sloriot

6,070
18
27

I understand that classifying based on Vertex_handle will be faster than using the point, but the issue I'm facing is that fit->vertex(0) is not compatible with the parameter required for alphaShape2d.classify. Do you have any ideas for workarounds? – Dawid Jul 18 '23 at 13:19
I just looked at the code and there is `Classification_type classify(const Vertex_handle& v) const` so maybe I'm missing your point here. – sloriot Jul 19 '23 at 05:49
1

In case the problem persists please put a self-contained code on gist.github.com so that we can have a look. – Andreas Fabri Jul 19 '23 at 11:43

Efficiently Filtering Triangles within an Alpha Shape in CGAL

1 Answers1