How to get the source and target points from Edge_iterator in CGAL
-
26-10-2019 - |
Question
I have a Delaunay triangulation over some points and want to iterate over all of the edges in it in length-ascending order in order to build a minimum spanning thread.
I've tried with the following approach but cannot get it to compile:
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_triangulation_2<K> T;
typedef K::Point_2 P;
typedef T::Vertex_handle Vh;
typedef T::Vertex_iterator Vi;
typedef T::Edge_iterator Ei;
bool sortFunction (Ei a, Ei b) {
K::FT la, lb;
la = CGAL::squared_distance(a.source().point(), a.target().point());
lb = CGAL::squared_distance(b.source().point(), b.target().point());
return la < lb;
}
...
T g;
...
std::vector<Ei> edges;
for (Ei ei = g.edges_begin(); ei != g.edges_end(); ei++) {
edges.push_back(ei);
}
std::sort(edges.begin(), edges.end(), sortFunction);
...
The compilation fails in the sortFunction
, saying that source
is no member of Edge_iterator
. However, the documentation confuses me here.
CGAL documentation says that the value type of the edge iterator is a halfedge.
There it is said that I can use source()
and target()
to access the points.
However, this does not seem to be the case. What am I messing up here?
Solution
The edge_iterator
is a std::pair
of a face and a vertex index. The edge's source and target vertices can be accessed over this face reference. The vertex index in the edge_iterator conforms to the opposite vertex. So, the other two have id's (i+2)%3
and (i+1)%3
.
Some other solution is getting to the segment via triangulation.segment(edge_iterator)
and then using the source()
and target()
functions to get to the points directly. However, you cannot get access to the vertex handles that way.
OTHER TIPS
Triangulation::Edge e;
//TODO: get e
Triangulation::Vertex_handle v1 = e.first->vertex((e.second + 1) % 3);
Triangulation::Vertex_handle v2 = e.first->vertex((e.second + 2) % 3);
K::FT squared_distance = CGAL::squared_distance(v1->point(), v2->point());
you can access to vertex_handle of the endpoints by
T::Vertex_handle sVertex = a->first->vertex(T::cw(a->second));
T::Vertex_handle fVertex = a->first->vertex(T::ccw(a->second));
an so on.. From each Vertex_handle you can recover point's coordinates by using the point method..
Hope it can help
Iterators should act a bit like pointers to the actual elements, so you need to dereference it before accessing any members. Try changing it to a->source().point()
Edit: I guess handles are also pointerlike. See if it likes this.
la = CGAL::squared_distance(a->source()->point(), a->target()->point());
lb = CGAL::squared_distance(b->source()->point(), b->target()->point());