CODEWITHSUNDEEP
c++cgal
Matthias
Matthias

Reputation: 516

CGAL Voronoi Diagram: Link input sites to faces

I'm constructing a Voronoi Diagram using CGAL, like so:

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

Now, I would like to know if there is a way to retrieve the faces the original sites belong to:

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

From the signature of the iterator above there is no apparent link to the underlying half-edge data structure of the voronoi diagram. I know about the locate method, however, as far as I know, locate runs in O(log(n)) time. Since I want to query all sites the resulting runtime would be O(n*log(n)), which seems kinda wasteful. Is there something I'm missing?

Upvotes: 1

Views: 331

Answers (1)

sloriot
sloriot

Reputation: 6263

You can do it the other way round by iterating over the faces and calling the dual method.

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

Upvotes: 2

Related Questions