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 遍历 facet 并结合前面的评论，但我仍然需要知道哪个排队/堆叠的 facet 受到每个约束删除的影响。
  4. 在遍历期间使用 aset而不是queue/ stack，这样我就可以从我需要访问涉及已删除约束的构面的句柄中删除（在删除之前），因为在删除之后它们可能会失效（如果发生翻转）。

那么，StackOverflow 对此有何看法？

4

0 回答 0