點插入後在CGAL Delaunay三角剖分中安全使用Cell_handle

我打算編寫一個將使用CGAL Delaunay三角剖分數據結構的算法。基本上我需要插入一些點到三角測量中，保存對某些單元格的引用，然後進行其他插入。點插入後在CGAL Delaunay三角剖分中安全使用Cell_handle

我想知道如何在三角測量中插入新點後，如何存儲對未失效的單元格的引用？

在我看來，Cell_handle只是一個指向內部結構的指針，所以由於內部容器的重新分配而存儲它是危險的。另一方面，我在Triangulation_3接口中看不到存儲Cell_handle索引的方法。

typedef CGAL::Exact_predicates_inexact_constructions_kernel K; 
typedef CGAL::Triangulation_vertex_base_3<K>    Vb; 
typedef CGAL::Triangulation_hierarchy_vertex_base_3<Vb> Vbh; 
typedef CGAL::Triangulation_data_structure_3<Vbh>  Tds; 
typedef CGAL::Delaunay_triangulation_3<K,Tds>   Dt; 
typedef CGAL::Triangulation_hierarchy_3<Dt>    Dh; 
typedef Dh::Vertex_iterator Vertex_iterator; 
typedef Dh::Vertex_handle Vertex_handle; 
typedef Dh::Point   Point; 

int main(){ 

    Dh T; 
    for(int i = 0; i < 100; ++i) 
     T.insert(Point(rand()%1000,rand()%1000,rand()%1000)); 

    assert(T.is_valid()); 
    assert(T.number_of_vertices() == 100); 
    assert(T.dimension() == 3); 

    typedef Dh::Cell_iterator CellIterator; 

    std::vector<Dh::Cell_handle> hnd; 
    CellIterator itEnd = T.finite_cells_end(); 
    for(CellIterator it = T.finite_cells_begin(); it!=itEnd; ++it){ 
     const int dist = std::distance(T.cells_begin(),it); 
     hnd.push_back(it); 
    } 

    const int newP(1000); 
    for(int i = 0; i < newP; ++i) 
     T.insert(Point(rand()%1000,rand()%1000,rand()%1000)); 

    int finiteC(0),infiniteC(0); 
    for(int i = 0; i < hnd.size(); ++i){ 
     const int dist = std::distance(T.cells_begin(),hnd[i]); 
     if(T.is_infinite(hnd[i])) 
    ++infiniteC; 
    else 
    ++finiteC; 
    } 
    assert(T.is_valid()); 
    return 0; 
}

此代碼系統崩潰，但是，這真是奇怪，我，如果我改變NEWP 10000，該代碼可以神奇地運行。

有人可以解釋我如何處理這個問題？

來源

2013-05-04 Nicola Pezzotti

崩潰發生在這行i == 79。「const int dist = std :: distance（T.cells_begin（），hnd [i]）;」我正在使用VS2012 - Debug x64 - MDd – 2013-05-04 22:02:45

由於在插入新點時單元格可能會消失，因此保存的句柄不保證指向您的期望。

由於您使用內部創建和刪除內部容器中的單元格的三角測量層次結構，因此發生崩潰。如果您使用CGAL :: Delaunay_triangulation_3，則不會發生崩潰。

對於你的問題，你應該存儲一個Vertex_handleS的四元組，並使用is_cell函數（記錄here）。

來源

2013-05-06 05:14:02 sloriot

事實上，插入時細胞可能會消失。您還可以使用find_conflicts（）函數來查找將要通過插入刪除的單元格，以便您可以更新與其相關的任何內容。

來源

2013-05-07 05:53:02

點插入後在CGAL Delaunay三角剖分中安全使用Cell_handle

回答

相關問題