CGAL Voronoi图:将输入站点链接到面

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();
}