CGAL：在周期性三角剖分中使用边迭代器访问每个顶点的邻居时出现问题

Question

我在我的代码中使用 CGAL 中的周期性 Delaunay 三角剖分，并为每个顶点生成所有相邻顶点。为此，我使用 Edge 迭代器，因为在我的例子中，它比 Vertex 迭代器快得多。这是代码片段，

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Periodic_2_triangulation_traits_2<Kernel> Gt;
typedef CGAL::Triangulation_vertex_base_with_info_2<unsigned int, Gt> Vb;
typedef CGAL::Periodic_2_triangulation_face_base_2<Gt> Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb> Tds;
typedef CGAL::Periodic_2_Delaunay_triangulation_2<Gt, Tds> Triangulation;
typedef Triangulation::Iso_rectangle Iso_rectangle;
typedef Triangulation::Edge_iterator Edge_iterator;
typedef Triangulation::Vertex_handle Vertex_handle;
typedef Triangulation::Point Point;
typedef vector<pair<Point, unsigned> > Vector_Paired;
Vector_Paired points;
Iso_rectangle domain(0,0,L,L);

for(int iat = 0; iat < N; iat++)
    {
 points.push_back(make_pair(Point(r_tot[iat][0],r_tot[iat][1]),iat));
    }
Triangulation T(points.begin(), points.end(), domain);

for(Edge_iterator ei=T.finite_edges_begin(); ei!=T.finite_edges_end(); ei++)
    {

      Triangulation::Face& f = *(ei->first);
      int ii = ei->second;
      Vertex_handle vi = f.vertex(f.cw(ii));     
      Vertex_handle vj = f.vertex(f.ccw(ii));    
      int iat = vi->info();
      int jat = vj->info();

      VecInd[iat].push_back(jat);
      VecInd[jat].push_back(iat);

    }

但是，有时我得到的不是每个顶点的一个特殊邻居，而是 8 个或 9 个或...相同邻居的副本。例如在 VecInd 中，它是一个包含相邻索引的二维向量，我得到这样的东西： VecInd[0]=[2,2,2,2,4,4,4,...]

我在 CGAL 网站上找不到使用边缘迭代器的示例，在 Whosebug 中也没有相关内容。我想知道这个实现是否正确？我应该在我的代码中添加什么以便每个邻居获得一份副本，我可以使用 STL::sets，但我想知道问题的根源。

Answer 1

这里是 Mael was posted on the CGAL-discuss mailing-list 的回答：

如果您的点集在几何上分布不均，则这些点的三角剖分可能不会在平面环面上形成单纯复形（换句话说，三角剖分中存在短环）。在这种情况下，该算法使用 8 个三角剖分副本来人为地创建单纯复形。您可以使用函数 is_triangulation_in_1_sheet() and read more about these mechanisms in the User Manual.

检查是否属于这种情况

使用副本时，遍历边缘确实会为您提供底层数据结构的确切信息：每条边缘 9 个实体。要获得独特的，您可以通过查看边缘顶点的偏移量来简单地从 9 个中筛选出 8 个。这就是 returns 唯一周期段的迭代器中所做的。不幸的是，您需要边，而此迭代器直接转换为边的几何形状（线段）。不过，您可以简单地使用该迭代器的主要过滤函数，即：is_canonical()。此函数将查看边的两个顶点的偏移量，并仅保留在域的第一个副本中至少有一个顶点的那些，这足以使其唯一。

CGAL：在周期性三角剖分中使用边迭代器访问每个顶点的邻居时出现问题

CGAL: problem accessing the neighbors of every vertex using edge iterator in periodic triangulation

cgal

delaunay