我正在使用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)),这似乎有点浪费。有什么我想念的吗?

最佳答案

您可以通过遍历面孔并调用 dual 方法来进行另一种处理。

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

关于c++ - CGAL Voronoi图:将输入站点链接到面部,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/26364212/

10-12 00:31