c++ - CGAL Voronoi 图 : Link input sites to faces

Question

我正在使用 CGAL 构建 Voronoi 图，如下所示:

//consider some points
std::vector<Point_2> points = read_input();

//throw points (i.e. Sites) into Voronoi diagram
VD vd;
for (std::vector<Point_2>::iterator it = points.begin(); it != points.end(); ++it) {
    vd.insert(*it);
}

现在，我想知道是否有办法检索原始站点所属的面孔:

for (VD::Site_iterator it = vd.sites_begin(); it != vd.sites_end(); ++it) {
    it->?!
}

从上面迭代器的签名来看，与 voronoi 图的底层半边数据结构没有明显的联系。我知道 locate 方法，但是，据我所知，locate 在 O(log(n)) 时间内运行。由于我想查询所有站点，因此生成的运行时间将为 O(n*log(n))，这似乎有点浪费。有什么我想念的吗？

Answer 1

您可以通过遍历面孔并调用 dual 来反过来做方法。

for (VD::Face_iterator fit=vd.faces_begin(),
                       fit_end=vd.faces_end();
                       fit!=fit_end;++fit)
{
  fit->dual()->point();
}