CGAL找到网格中的内部点

我试图使用CGAL来查找三角形网格内部的点。（即不在其边界上的一组点），对于使用函数CGAL :: Side_of_triangle_mesh <>的3D网格，有一个similar example here。任何人都可以帮助/建议如何对此进行二维三角测量？CGAL找到网格中的内部点

我的测试代码只是创建两个正方形，一个在另一个内，然后使种子在原点（使一个孔），然后进行2D Delaunay三角当我调用side_of_triangle_mesh <>类：

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 ; 
}

来源

2017-05-26 CobaltGray

感谢@sloriot我得到的这条底线。底线是你不能使用2D Delaunay网格的CGAL :: Side_of_triangle_mesh <>。相反，你要做的是循环遍历网格中的所有顶点，并通过查看顶点周围的所有相邻面来测试每个顶点。如果任何面在域外，则顶点或点位于网格的边缘。

以下是更正代码：

#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

来源

2017-05-26 16:42:27 CobaltGray

必须使用locate功能。它将返回一个包含你的查询点的脸部句柄。然后您需要使用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. 

}

来源

2017-05-26 08:31:01 sloriot

感谢@sloriot。什么定义了一个“域”，并将船体边缘上的一个点放在域内还是域外？（我认为从手册中“不”是我想要的，我想把网格边界上的点与内部网格的边界隔离开来）。你确实给了我一个想法。我可以得到与顶点相关的面部手柄，并从中获得其他两个顶点。然后找到每个顶点的邻居面，如果有的话是'无限'，那么测试点必须在边界上？必须有一个更简单的方法？在hilbert_sort上提示。 – CobaltGray

实际上，对于'locate'函数，我的意思是另一个重载，它也包含位置类型（面，顶点或边）。我已经更新了我的答案。该域由包含至少一个种子点的连接组件定义。 – sloriot

感谢您的尝试，但仍然没有回答我的问题 - 我需要区分网格边界上的顶点和其内部的顶点。我按照你的建议实现了is_in_domain（）函数，它包含了网格边缘的顶点。不幸的是，我自己的contrib不起作用，因为网格边缘上的顶点仍然可能有三个非无限邻居。 – CobaltGray

CGAL找到网格中的内部点

回答

相关问题