在CGAL中高效地筛选Alpha形状内的三角形

huangapple go评论77阅读模式
英文:

Efficiently Filtering Triangles within an Alpha Shape in CGAL

问题

我目前正在处理一个项目,涉及使用CGAL的Constrained Delaunay Triangulation和Alpha Shape功能来处理大量的点。然而,当使用CGAL::Alpha_shape_2类提供的classify方法来筛选位于Alpha Shape内的三角形时,我遇到了性能问题。随着点的数量增加,分类过程变得非常缓慢。

以下是我正在使用的代码片段:

// Constrained Delaunay Triangulation
ConstrainedDelaunayTriangulation constrainedDelaunayTriangulation;
// 将点插入constrainedDelaunayTriangulation

// 计算Alpha Shape
const AlphaShape2d alphaShape2d = calc2dAlphaShapeForPointCloud(points);

// 筛选位于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();

    // 检查三角形的三个顶点是否都位于Alpha Shape内
    const bool areAllVerticesInAlphaShape =
        (alphaShape2d.classify(p1) != AlphaShape2d::EXTERIOR) &&
        (alphaShape2d.classify(p2) != AlphaShape2d::EXTERIOR) &&
        (alphaShape2d.classify(p3) != AlphaShape2d::EXTERIOR);

    if (areAllVerticesInAlphaShape) {
        // 三角形位于Alpha Shape内
        // 进一步处理...
    }
}

我怀疑classify方法可能是性能瓶颈,特别是对于大量点。我正在寻找更有效的方法来检查三角形是否位于Alpha Shape内。

英文:

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.

答案1

得分: 1

我认为,如果你尝试对点进行分类而不是顶点,它将首先模拟在三角剖分中插入一个点。最好直接使用顶点。请注意,除非你正在使用REGULARIZED模式,否则顶点永远不会位于外部。

英文:

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.

huangapple
  • 本文由 发表于 2023年7月18日 14:40:50
  • 转载请务必保留本文链接:https://go.coder-hub.com/76710115.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定