Hi there,
I'm doing some experiment with CGAL Constrained Delaunay Triangulation and boost graph Minimum Spanning Tree. The constrained edges of CDT correspond to path that already exist, the non constrained edges of CDT are transient edges for the MST algorithm. To make sure that MST will use the constrained edges, i'm setting their associated 'weight' (length) to zero, and for the non-constrained edges i'm setting their 'weight' to their squared length. I'm currently doing all of these manually, including 'transforming' the data structures between the steps of my 'pipeline'. I know it is not optimal, but at least i am able to get the whole pipeline working. I went through the chapter 'CGAL and the Boost Graph Library' (BTW big thumb up for the documentation!) and saw that CGAL provides all the bolts and nuts to bind CGAL with boost graph. For example, CGAL provide the edge weight map needed by MST, filters that allow to filter out infinite edges, ... I am now wondering if I could use a filter to hide/proxy the weight of the constrained edges or if i should use a different approach. Maybe I should redefine T2_edge_weight_map (CGAL/boost/graph/graph_traits_Triangulation_2.h) so that it takes a CDT as a ctor argument... Actually it looks like i cannot use graph_traits_Triangulation_2.h or graph_traits_Delaunay_Triangulation_2.h, i would need to write my own version for CDT, do I? Any clarification or point out are very welcome, Chris -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss |
On 21 March 2017 at 15:34, Ch'Gans <[hidden email]> wrote:
> Hi there, > [...] > > Actually it looks like i cannot use graph_traits_Triangulation_2.h or > graph_traits_Delaunay_Triangulation_2.h, i would need to write my own > version for CDT, do I? Indeed, I had to copy and adapt graph_traits_Delaunay_Triangulation_2.h, first to add support for the Constrained_Delaunay_Triangulation, and as well for the intersection tag. On top of that I've modified the weight_map to return 0 for constrained weight. Surprisingly, it was quite easy. I just wondered why there's no generic graph_traits that could be used for the whole (or part of) the triangulation family. As well, I have the feeling that the weight map is sub-optimal in term of CPU usage, it doesn't cache the weight value, tho I haven't verified if the operator[] get called more than once for a given edge... One might argue that caching is user choice, a decision that should be based on trade off b/w time and space requirement. Chris > > Any clarification or point out are very welcome, > Chris -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss |
On 03/21/2017 02:16 PM, Ch'Gans wrote:
> On 21 March 2017 at 15:34, Ch'Gans <[hidden email]> wrote: >> Hi there, >> > [...] >> >> Actually it looks like i cannot use graph_traits_Triangulation_2.h or >> graph_traits_Delaunay_Triangulation_2.h, i would need to write my own >> version for CDT, do I? > > Indeed, I had to copy and adapt > graph_traits_Delaunay_Triangulation_2.h, first to add support for the > Constrained_Delaunay_Triangulation, and as well for the intersection > tag. On top of that I've modified the weight_map to return 0 for > constrained weight. Surprisingly, it was quite easy. > I just wondered why there's no generic graph_traits that could be used > for the whole (or part of) the triangulation family. > As well, I have the feeling that the weight map is sub-optimal in term > of CPU usage, it doesn't cache the weight value, tho I haven't > verified if the operator[] get called more than once for a given > edge... One might argue that caching is user choice, a decision that > should be based on trade off b/w time and space requirement. > I guess you only have to make the specialization of graph_traits inherit from the one from Delaunay and leave it empty, right? Sebastien. > Chris > >> >> Any clarification or point out are very welcome, >> Chris > -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss |
In reply to this post by chgans
Hello, In the pull request https://github.com/CGAL/cgal/pull/1991 I added the graph_traits and free functions so that now all triangulation classes can be used with the BGL. Concerning the edge weights, you might store them in a boost::unordered_map<edge_descriptor,double>, fill it as you like, wrap it in a boost associative property map, and then pass it to the MST algorithm, instead of redefining T2_edge_weight_map. The weight map is a parameter of the MST algorithm. best, andreas On 21/03/2017 03:34, Ch'Gans wrote: > Hi there, > > I'm doing some experiment with CGAL Constrained Delaunay Triangulation > and boost graph Minimum Spanning Tree. > > The constrained edges of CDT correspond to path that already exist, > the non constrained edges of CDT are transient edges for the MST > algorithm. > To make sure that MST will use the constrained edges, i'm setting > their associated 'weight' (length) to zero, and for the > non-constrained edges i'm setting their 'weight' to their squared > length. > > I'm currently doing all of these manually, including 'transforming' > the data structures between the steps of my 'pipeline'. I know it is > not optimal, but at least i am able to get the whole pipeline working. > > I went through the chapter 'CGAL and the Boost Graph Library' (BTW big > thumb up for the documentation!) and saw that CGAL provides all the > bolts and nuts to bind CGAL with boost graph. For example, CGAL > provide the edge weight map needed by MST, filters that allow to > filter out infinite edges, ... > > I am now wondering if I could use a filter to hide/proxy the weight of > the constrained edges or if i should use a different approach. > Maybe I should redefine T2_edge_weight_map > (CGAL/boost/graph/graph_traits_Triangulation_2.h) so that it takes a > CDT as a ctor argument... > > Actually it looks like i cannot use graph_traits_Triangulation_2.h or > graph_traits_Delaunay_Triangulation_2.h, i would need to write my own > version for CDT, do I? > > Any clarification or point out are very welcome, > Chris > -- Andreas Fabri, PhD Chief Officer, GeometryFactory Editor, The CGAL Project phone: +33.492.954.912 skype: andreas.fabri -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss |
On 24 March 2017 at 03:31, Andreas Fabri
<[hidden email]> wrote: > > Hello, > > In the pull request https://github.com/CGAL/cgal/pull/1991 > I added the graph_traits and free functions so that now > all triangulation classes can be used with the BGL. Cool, thanks a lot! I'll give it a try. > > Concerning the edge weights, you might store them in > a boost::unordered_map<edge_descriptor,double>, > fill it as you like, wrap it in a boost associative > property map, and then pass it to the MST algorithm, > instead of redefining T2_edge_weight_map. The weight map > is a parameter of the MST algorithm. Thanks for the tip, will try that. Chris > > best, > > andreas > > > On 21/03/2017 03:34, Ch'Gans wrote: >> >> Hi there, >> >> I'm doing some experiment with CGAL Constrained Delaunay Triangulation >> and boost graph Minimum Spanning Tree. >> >> The constrained edges of CDT correspond to path that already exist, >> the non constrained edges of CDT are transient edges for the MST >> algorithm. >> To make sure that MST will use the constrained edges, i'm setting >> their associated 'weight' (length) to zero, and for the >> non-constrained edges i'm setting their 'weight' to their squared >> length. >> >> I'm currently doing all of these manually, including 'transforming' >> the data structures between the steps of my 'pipeline'. I know it is >> not optimal, but at least i am able to get the whole pipeline working. >> >> I went through the chapter 'CGAL and the Boost Graph Library' (BTW big >> thumb up for the documentation!) and saw that CGAL provides all the >> bolts and nuts to bind CGAL with boost graph. For example, CGAL >> provide the edge weight map needed by MST, filters that allow to >> filter out infinite edges, ... >> >> I am now wondering if I could use a filter to hide/proxy the weight of >> the constrained edges or if i should use a different approach. >> Maybe I should redefine T2_edge_weight_map >> (CGAL/boost/graph/graph_traits_Triangulation_2.h) so that it takes a >> CDT as a ctor argument... >> >> Actually it looks like i cannot use graph_traits_Triangulation_2.h or >> graph_traits_Delaunay_Triangulation_2.h, i would need to write my own >> version for CDT, do I? >> >> Any clarification or point out are very welcome, >> Chris >> > > -- > Andreas Fabri, PhD > Chief Officer, GeometryFactory > Editor, The CGAL Project > > phone: +33.492.954.912 skype: andreas.fabri > > > -- > You are currently subscribed to cgal-discuss. > To unsubscribe or access the archives, go to > https://sympa.inria.fr/sympa/info/cgal-discuss > > -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss |
In reply to this post by andreas.fabri
On 24 March 2017 at 03:31, Andreas Fabri
<[hidden email]> wrote: > > Hello, > > In the pull request https://github.com/CGAL/cgal/pull/1991 > I added the graph_traits and free functions so that now > all triangulation classes can be used with the BGL. BTW, what is the rational behind all these 'copy/paste' in these graph_traits, isn't it possible to parametrise the templates with a triangulation instead of the triangulation own params? eg: template<class Triangulation> struct graph_traits< Triangulation > { typedef typename Triangulation::Vertex_handle vertex_descriptor; } Chris > > Concerning the edge weights, you might store them in > a boost::unordered_map<edge_descriptor,double>, > fill it as you like, wrap it in a boost associative > property map, and then pass it to the MST algorithm, > instead of redefining T2_edge_weight_map. The weight map > is a parameter of the MST algorithm. > > best, > > andreas > > > On 21/03/2017 03:34, Ch'Gans wrote: >> >> Hi there, >> >> I'm doing some experiment with CGAL Constrained Delaunay Triangulation >> and boost graph Minimum Spanning Tree. >> >> The constrained edges of CDT correspond to path that already exist, >> the non constrained edges of CDT are transient edges for the MST >> algorithm. >> To make sure that MST will use the constrained edges, i'm setting >> their associated 'weight' (length) to zero, and for the >> non-constrained edges i'm setting their 'weight' to their squared >> length. >> >> I'm currently doing all of these manually, including 'transforming' >> the data structures between the steps of my 'pipeline'. I know it is >> not optimal, but at least i am able to get the whole pipeline working. >> >> I went through the chapter 'CGAL and the Boost Graph Library' (BTW big >> thumb up for the documentation!) and saw that CGAL provides all the >> bolts and nuts to bind CGAL with boost graph. For example, CGAL >> provide the edge weight map needed by MST, filters that allow to >> filter out infinite edges, ... >> >> I am now wondering if I could use a filter to hide/proxy the weight of >> the constrained edges or if i should use a different approach. >> Maybe I should redefine T2_edge_weight_map >> (CGAL/boost/graph/graph_traits_Triangulation_2.h) so that it takes a >> CDT as a ctor argument... >> >> Actually it looks like i cannot use graph_traits_Triangulation_2.h or >> graph_traits_Delaunay_Triangulation_2.h, i would need to write my own >> version for CDT, do I? >> >> Any clarification or point out are very welcome, >> Chris >> > > -- > Andreas Fabri, PhD > Chief Officer, GeometryFactory > Editor, The CGAL Project > > phone: +33.492.954.912 skype: andreas.fabri > > > -- > You are currently subscribed to cgal-discuss. > To unsubscribe or access the archives, go to > https://sympa.inria.fr/sympa/info/cgal-discuss > > -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss |
On 24/03/2017 06:41, Ch'Gans wrote: > On 24 March 2017 at 03:31, Andreas Fabri > <[hidden email]> wrote: >> >> Hello, >> >> In the pull request https://github.com/CGAL/cgal/pull/1991 >> I added the graph_traits and free functions so that now >> all triangulation classes can be used with the BGL. > > BTW, what is the rational behind all these 'copy/paste' in these > graph_traits, isn't it possible to parametrise the templates with a > triangulation instead of the triangulation own params? > eg: > template<class Triangulation> > struct graph_traits< Triangulation > { > typedef typename Triangulation::Vertex_handle vertex_descriptor; > > } Note that your template parameter `Triangulation` has no semantics for the compiler. We have to provide these partial specializations. Alternatively, we could put these typedefs inside the triangulation classes, so that the generic definition boost::graph_traits<T> would work, as it has typedefs such as typedef typename T::vertex_descriptor vertex_descriptor; We then would not need the partial specializations. Andreas > > > Chris > > >> >> Concerning the edge weights, you might store them in >> a boost::unordered_map<edge_descriptor,double>, >> fill it as you like, wrap it in a boost associative >> property map, and then pass it to the MST algorithm, >> instead of redefining T2_edge_weight_map. The weight map >> is a parameter of the MST algorithm. >> >> best, >> >> andreas >> >> >> On 21/03/2017 03:34, Ch'Gans wrote: >>> >>> Hi there, >>> >>> I'm doing some experiment with CGAL Constrained Delaunay Triangulation >>> and boost graph Minimum Spanning Tree. >>> >>> The constrained edges of CDT correspond to path that already exist, >>> the non constrained edges of CDT are transient edges for the MST >>> algorithm. >>> To make sure that MST will use the constrained edges, i'm setting >>> their associated 'weight' (length) to zero, and for the >>> non-constrained edges i'm setting their 'weight' to their squared >>> length. >>> >>> I'm currently doing all of these manually, including 'transforming' >>> the data structures between the steps of my 'pipeline'. I know it is >>> not optimal, but at least i am able to get the whole pipeline working. >>> >>> I went through the chapter 'CGAL and the Boost Graph Library' (BTW big >>> thumb up for the documentation!) and saw that CGAL provides all the >>> bolts and nuts to bind CGAL with boost graph. For example, CGAL >>> provide the edge weight map needed by MST, filters that allow to >>> filter out infinite edges, ... >>> >>> I am now wondering if I could use a filter to hide/proxy the weight of >>> the constrained edges or if i should use a different approach. >>> Maybe I should redefine T2_edge_weight_map >>> (CGAL/boost/graph/graph_traits_Triangulation_2.h) so that it takes a >>> CDT as a ctor argument... >>> >>> Actually it looks like i cannot use graph_traits_Triangulation_2.h or >>> graph_traits_Delaunay_Triangulation_2.h, i would need to write my own >>> version for CDT, do I? >>> >>> Any clarification or point out are very welcome, >>> Chris >>> >> >> -- >> Andreas Fabri, PhD >> Chief Officer, GeometryFactory >> Editor, The CGAL Project >> >> phone: +33.492.954.912 skype: andreas.fabri >> >> >> -- >> You are currently subscribed to cgal-discuss. >> To unsubscribe or access the archives, go to >> https://sympa.inria.fr/sympa/info/cgal-discuss >> >> > -- Andreas Fabri, PhD Chief Officer, GeometryFactory Editor, The CGAL Project phone: +33.492.954.912 skype: andreas.fabri -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss |
Free forum by Nabble | Edit this page |