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 に答える