0

我打算编写一个使用 CGAL Delaunay 三角剖分数据结构的算法。基本上我需要在三角剖分中插入一些点，保存对一些单元格的引用，然后进行一些其他插入。

我想知道如何存储对在三角剖分中插入新点后未失效的单元格的引用？

在我看来， 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，这段代码就会神奇地工作。

有人可以解释我如何处理这个问题吗？

4

2 回答 2

2

由于在插入新点期间单元格可能会消失，因此您保存的句柄并不能保证指向您所期望的。

您遇到了崩溃，因为您使用了在内部容器中创建和删除单元格的三角剖分层次结构。如果您使用 CGAL::Delaunay_triangulation_3，则不会发生崩溃。

对于您的问题，您应该存储四个 Vertex_handleS 并使用 is_cell 函数（在此处记录）。

于 2013-05-06T05:14:02.257 回答
1

事实上，细胞可以在插入时消失。您还可以使用 find_conflicts() 函数来查找将被插入删除的单元格，以便您可以更新与它们相关的任何内容。

于 2013-05-07T05:53:02.350 回答