1

ファセットが何らかの「ラベル」(何らかの抽象プロパティ) に関連付けられている、制約付きの Delaunay 三角形分割があるとします。同じラベルを共有するファセットに付随するエッジを制約から削除したいと考えています。それを行うための効率的なアプローチは何ですか?また、制約が削除された後に取得されたファセットがそのラベルを保持していることを確認する方法は?

これは、私の目的を説明するために CGAL の例から追加されたコードの一部です。

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_face_base_with_info_2.h>
#include <CGAL/Polygon_2.h>
#include <iostream>

struct FaceInfo2
{
  FaceInfo2(){}
  int label;
};

typedef CGAL::Exact_predicates_inexact_constructions_kernel       K;
typedef CGAL::Triangulation_vertex_base_2<K>                      Vb;
typedef CGAL::Triangulation_face_base_with_info_2<FaceInfo2,K>    Fbb;
typedef CGAL::Constrained_triangulation_face_base_2<K,Fbb>        Fb;
typedef CGAL::Triangulation_data_structure_2<Vb,Fb>               TDS;
typedef CGAL::Exact_predicates_tag                                Itag;
typedef CGAL::Constrained_Delaunay_triangulation_2<K, TDS, Itag>  CDT;
typedef CDT::Point                                                Point;
typedef CGAL::Polygon_2<K>                                        Polygon_2;


void insert_polygon(CDT& cdt,const Polygon_2& polygon)
{
  if ( polygon.is_empty() ) return;
  CDT::Vertex_handle v_prev=cdt.insert(*CGAL::cpp11::prev(polygon.vertices_end()));
  for (Polygon_2::Vertex_iterator vit=polygon.vertices_begin();
       vit!=polygon.vertices_end();++vit)
  {
    CDT::Vertex_handle vh=cdt.insert(*vit);
    cdt.insert_constraint(vh,v_prev);
    v_prev=vh;
  }  
}

void compute_labels(CDT& cdt)
{
  // Do stuff and set the 'label' of each facet according to some property
}

int main( )
{
  // Insert some polyons into a constrained triangulation
  CDT cdt;
  insert_polygon(cdt,polygon1);
  insert_polygon(cdt,polygon2); // ...

  // Mark facets according to an arbitrary property
  compute_labels(cdt);

  int count=0;
  for (CDT::Finite_edges_iterator eit=cdt.finite_edges_begin();
                                  eit!=cdt.finite_edges_end();++eit)
  {
    // This will not do, because the iterator may get invalidated
    if ( eit->first->info().label == eit->first->neighbor(eit->second)->info().label )
      cdt.remove_constrained_edge(eit->first, eit->second);
  }

  return 0;
}

そこからいくつかの可能性が見えます：

  1. 元の三角形分割で異なるラベルを持つ面のみを結合する制約を挿入して、新しい CDT を構築します。
  2. バリアントcdt.remove_constrained_edge(fh, i, out)を使用して、制約の削除によって影響を受ける可能性のあるファセットを回復し、それに応じて処理します (ただし、イテレータが無効になるという問題は残ります)。
  3. 前の発言と組み合わせてファセットの BFS/DFS トラバーサルを使用しますが、各制約の削除によってどのキュー/スタック ファセットが影響を受けたかを知る必要があります。
  4. トラバーサル中に/のset代わりに使用して、ファセットから削除できるようにします (削除前に) 削除された制約に関連するファセットへのハンドルを参照する必要があります。queuestack

では、StackOverflow はこれについてどう考えているのでしょうか?

4

0 に答える 0