Constrained delaunay triangulation and boost's graph minimum spanning tree

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Constrained delaunay triangulation and boost's graph minimum spanning tree

chgans
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


Reply | Threaded
Open this post in threaded view
|

Re: Constrained delaunay triangulation and boost's graph minimum spanning tree

chgans
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


Reply | Threaded
Open this post in threaded view
|

Re: Constrained delaunay triangulation and boost's graph minimum spanning tree

Sebastien Loriot (GeometryFactory)
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


Reply | Threaded
Open this post in threaded view
|

Re: Constrained delaunay triangulation and boost's graph minimum spanning tree

andreas.fabri
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


Reply | Threaded
Open this post in threaded view
|

Re: Constrained delaunay triangulation and boost's graph minimum spanning tree

chgans
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


Reply | Threaded
Open this post in threaded view
|

Re: Constrained delaunay triangulation and boost's graph minimum spanning tree

chgans
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


Reply | Threaded
Open this post in threaded view
|

Re: Constrained delaunay triangulation and boost's graph minimum spanning tree

andreas.fabri


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