CGAL 在网格中找到内部点

Question

我正在尝试将 CGAL to find the points that are in the interior of a triangle mesh. (i.e. the set of points that are not on its boundary. There is a similar example here 用于使用函数 CGAL::Side_of_triangle_mesh<> 的 3D 网格。任何人都可以帮助/建议如何 mod 二维三角剖分吗？

我的测试代码只是创建两个正方形，一个在另一个正方形中，然后在原点放置一个种子（打一个洞），然后执行 2D Delaunay 三角剖分。当我调用 side_of_triangle_mesh<> class 时：

Point_2 p = points2D[i];
CGAL::Bounded_side res = inside2D(p);

我收到错误：

/usr/local/include/CGAL/Side_of_triangle_mesh.h:164:16: Candidate function not viable: no known conversion from 'Point_2' (aka 'Point_2<CGAL::Epick>') to 'const Point' (aka 'const Point_3<CGAL::Epick>') for 1st argument

这是否意味着 side_of_triangle_mesh 仅适用于 3D Polyhedron_3 网格？如果是这样，谁能建议一种方法来为 2D 网格执行此操作？

我的测试代码如下：谢谢

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Delaunay_mesh_vertex_base_2.h>
#include <CGAL/Delaunay_mesh_face_base_2.h>
#include <CGAL/Delaunay_mesh_size_criteria_2.h>
#include <CGAL/Side_of_triangle_mesh.h>
#include <vector>
#include <CGAL/Delaunay_mesher_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel     K;
typedef K::Point_2 Point_2;
typedef CGAL::Triangle_2<K> triangle;
typedef CGAL::Delaunay_mesh_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;
typedef CDT::Vertex_handle                                      Vertex_handle;
typedef CGAL::Delaunay_mesh_size_criteria_2<CDT>                Criteria;

int main(int argc, char* argv[])
{
    // Create a vector of the points
    //
    std::vector<Point_2> points2D ;
    points2D.push_back(Point_2(-5.0, -5.0));    // ----------
    points2D.push_back(Point_2( 5.0, -5.0));    // |   OUTER
    points2D.push_back(Point_2( 5.0,  5.0));    // |   SQUARE
    points2D.push_back(Point_2(-5.0,  5.0));    // ----------
    points2D.push_back(Point_2(-2.5, -2.5));    // ----------
    points2D.push_back(Point_2( 2.5, -2.5));    // |   INNER
    points2D.push_back(Point_2( 2.5,  2.5));    // |   SQUARE
    points2D.push_back(Point_2(-2.5,  2.5));    // ----------
    size_t numTestPoints = points2D.size();

    // Create a constrained delaunay triangulation and add the points
    //
    CDT cdt;
    std::vector<Vertex_handle> vhs;
    for (unsigned int i=0; i<numTestPoints; ++i){
        vhs.push_back(cdt.insert(points2D[i]));
    }

    // Creare constraints of the sides of the mesh
    //
    cdt.insert_constraint(vhs[0],vhs[1]);
    cdt.insert_constraint(vhs[1],vhs[2]);
    cdt.insert_constraint(vhs[2],vhs[3]);
    cdt.insert_constraint(vhs[3],vhs[0]);

    cdt.insert_constraint(vhs[4],vhs[5]);
    cdt.insert_constraint(vhs[5],vhs[6]);
    cdt.insert_constraint(vhs[6],vhs[7]);
    cdt.insert_constraint(vhs[7],vhs[4]);

    // Create a seed to make sure the inner square is a hole
    //
    std::list<Point_2> list_of_seeds;
    list_of_seeds.push_back(Point_2(0, 0));

    // Refine the mesh into triangles of max side length '1' and ensuring seeds are 'holes'
    //
    CGAL::refine_Delaunay_mesh_2(cdt, list_of_seeds.begin(), list_of_seeds.end(),
                                 Criteria(0.125, 1),false);


    // Call side_of_triangle_mesh
    //
    CGAL::Side_of_triangle_mesh<CDT, K> inside2D(cdt) ;

    int n_inside = 0;
    int n_boundary = 0;
    for(unsigned int i=0; i<numTestPoints; ++i)
    {
        Point_2 p = points2D[i];
        CGAL::Bounded_side res = inside2D(p);
        // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        // NO MATCHING FUNCTION Call

        if (res == CGAL::ON_BOUNDED_SIDE) { ++n_inside; }
        if (res == CGAL::ON_BOUNDARY) { ++n_boundary; }
    }
    std::cerr << "2D results for query size: " << cdt.number_of_vertices() << std::endl;
    std::cerr << "  " << n_inside << " points inside " << std::endl;
    std::cerr << "  " << n_boundary << " points on boundary " << std::endl;

    return 0 ;
}

Answer 1

您必须使用 locate 功能。它将 return 包含您的查询点的面部句柄。然后你需要使用is_in_domain()成员函数检查人脸是否在域中。

请注意，如果您有多个查询要做，您应该先将所有查询点放在一个容器中，然后使用 hilbert_sort 对它们进行排序并将前一个点的位置用作定位函数的第二个参数。

以下是如何在边界情况下获取事件面的示例代码：

CDT_2 mesh;

CGAL::Locate_type loc;
int li;

Point_2 query;

Face_handle f =  mesh.locate(query, loc, li);

switch(loc)
{
  case FACE:
    f->is_in_domain();
  break;
  case EDGE:
  {
    bool face_1_in_domain = f->is_in_domain(); // first incident face status
    bool face_2_in_domain = f->neighbor(li)->is_in_domain(); // second incident face status
    break;
  }
  case VERTEX:
  {
    // turn around f->vertex(li)
    Face_handle start = f;
    do{
      bool current_face_in_domain = f->is_in_domain();
      Vertex_handle v = f->vertex(mesh.cw(li));
      f = f->neighbor(mesh.ccw(li));
      li = f->index(v);
    }
    while(f!=current);
    break;
  }
  default:
    // outside of the domain.

}

Answer 2

多亏了@sloriot，我才弄清了真相。最重要的是，您不能将 CGAL::Side_of_triangle_mesh<> 用于 2D Delaunay 网格。相反，您需要做的是遍历网格中的所有顶点，并通过查看顶点周围的所有相邻面来测试每个顶点。如果任何面在域之外，则顶点或点位于网格的边缘。

这是更正后的代码：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Delaunay_mesh_vertex_base_2.h>
#include <CGAL/Delaunay_mesh_face_base_2.h>
#include <CGAL/Delaunay_mesh_size_criteria_2.h>
#include <vector>
#include <CGAL/Delaunay_mesher_2.h>


typedef CGAL::Exact_predicates_inexact_constructions_kernel     K;
typedef K::Point_2                                              Point_2;
typedef CGAL::Delaunay_mesh_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;
typedef CDT::Vertex_handle                                      Vertex_handle;
typedef CGAL::Delaunay_mesh_size_criteria_2<CDT>                Criteria;
typedef CDT::Vertex_iterator                                    Vertex_iterator;
typedef CDT::Vertex                                             Vertex;
typedef CDT::Face                                               Face ;
typedef Face::Face_handle                                       Face_handle ;
typedef CDT::Face_circulator                                    Face_circulator ;


int main(int argc, char* argv[])
{

    // Create a vector of the points
    //
    std::vector<Point_2> points2D ;
    points2D.push_back(Point_2(-5.0, -5.0));    // ----------
    points2D.push_back(Point_2( 5.0, -5.0));    // |   OUTER
    points2D.push_back(Point_2( 5.0,  5.0));    // |   SQUARE
    points2D.push_back(Point_2(-5.0,  5.0));    // ----------
    points2D.push_back(Point_2(-2.5, -2.5));    // ----------
    points2D.push_back(Point_2( 2.5, -2.5));    // |   INNER
    points2D.push_back(Point_2( 2.5,  2.5));    // |   SQUARE
    points2D.push_back(Point_2(-2.5,  2.5));    // ----------
    size_t numTestPoints = points2D.size();

    // Create a constrained delaunay triangulation and add the points
    //
    CDT cdt;
    std::vector<Vertex_handle> vhs;
    for (unsigned int i=0; i<numTestPoints; ++i){
        vhs.push_back(cdt.insert(points2D[i]));
    }

    // Creare constraints of the sides of the mesh
    //
    cdt.insert_constraint(vhs[0],vhs[1]);
    cdt.insert_constraint(vhs[1],vhs[2]);
    cdt.insert_constraint(vhs[2],vhs[3]);
    cdt.insert_constraint(vhs[3],vhs[0]);

    cdt.insert_constraint(vhs[4],vhs[5]);
    cdt.insert_constraint(vhs[5],vhs[6]);
    cdt.insert_constraint(vhs[6],vhs[7]);
    cdt.insert_constraint(vhs[7],vhs[4]);

    // Create a seed to make sure the inner square is a hole
    //
    std::list<Point_2> list_of_seeds;
    list_of_seeds.push_back(Point_2(0, 0));

    // Refine the mesh into triangles of max side length '1' and ensuring seeds are 'holes'
    //
    CGAL::refine_Delaunay_mesh_2(cdt, list_of_seeds.begin(), list_of_seeds.end(),
                                 Criteria(0.125, 1.5),false);

    // The mesh is now created. The next bit swings around each vertex point checking that
    // all faces around it are in the domain. If any are not then the vertex is on the
    // edge of the mesh.
    // thanks to @sloriot for this
    //

    Vertex v ;
    std::vector<Point_2> interior_points ;
    std::vector<Point_2> boundary_points ;
    CDT::Locate_type loc = CDT::Locate_type::VERTEX ;
    int li;

    Vertex_iterator vit = cdt.vertices_begin(), beyond = cdt.vertices_end() ;
    while (vit != beyond) {
        v = *vit ;
        Point_2 query = vit->point();
        Face_handle f =  cdt.locate(query, loc, li);

        bool current_face_in_domain ;
        Face_handle start = f ;
        do {
            current_face_in_domain = f->is_in_domain() ;
            Vertex_handle vh = f->vertex(li);
            f = f->neighbor(cdt.ccw(li));
            li = f->index(vh) ;
        }
        while(current_face_in_domain && f != start) ;

        if (f == start) {
            interior_points.push_back(query) ;
        }else{
            boundary_points.push_back(query) ;
        }
        ++vit ;
    }

    printf("Boundary points:\n");
    for(auto p = boundary_points.begin(); p != boundary_points.end(); ++p){
        printf("%f,%f\n",p->x(), p->y()) ;
    }

    printf("interior points:\n");
    for(auto p = interior_points.begin(); p != interior_points.end(); ++p){
        printf("%f,%f\n",p->x(), p->y()) ;
    }

    return 0 ;
}

当你运行它时你应该得到类似的东西： This

CGAL 在网格中找到内部点

CGAL find interior points in a mesh

c++

mesh

cgal

triangulation

delaunay