我正在使用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/