CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

Mattia Penati wrote:
> On 28 March 2011 15:11, Sebastien Loriot (GeometryFactory)
> <>
>  wrote:
> > Hello Mattia,
> >
> > Conceptually I have a problem defining a graph on a data structure which
> > is documented as a point set on which you can do queries. I mean that
> > there is no notion of graph on the structure, whereas there is an
> > obvious one on triangulation.
>
>
> I completely agree with you about the fact that a point set doesn't
> define a graph, but there are some applications where this definition
> is implicit. Currently I'm working on a problem in which I need to do
> geometric queries and to construct the Euclidean minimum spanning tree
> (EMSP) of a 2D point set. To define the EMST obviously you need a
> graph, but it's the complete graph given by points, so it's quite
> useless to describe each edge. And the algorithm to construct the EMST
> use the fact that EMST is a subgraph of Delaunay triangulation.
My answer was related to the fact that I was not enthusiast to add
the graph_traits specialization and document it, because as you said you
are using the underlying Delaunay triangulation. Hopefully your code
works with the Delaunay specialization (up to documentation problem).

Thanks for your feedback.

> > Can you try using the following specialization of graph_traits
> > boost::graph_traits<Point_set<Gt,Tds>::Base> instead of
> > boost::graph_traits<Point_set<Gt,Tds> > in your code and tell us whether
> > it is working?
>
> Yes.