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找到網格中的內部點

回答

相關問題