CGAL users discussion list

[Panagiotis Cheilaris <>]

On Mon, May 06, 2013 at 12:37:56PM -0700, Pablo Miranda Carranza wrote:
> I tried CORE::Expr in the data I had, I summarise here my findings and what
> has worked for me:
> 
> Even if this worked in the sample program above, it did not work with the
> whole data.
> 
> typedef CORE::Expr                                  ENT;
> typedef CGAL::Simple_cartesian<double>    CK;
> typedef CGAL::Simple_cartesian<ENT>        EK;
> typedef CGAL::Segment_Delaunay_graph_filtered_traits_2<
> CK,
> CGAL::Field_with_sqrt_tag,EK,
> CGAL::Field_tag
> >  Gt;
> typedef Extended_Segment_Delaunay_graph<Gt>   SDG_2;
> 
> Following your tip, I tried this, which worked (though it is quite slow):
> 
> typedef CORE::Expr                               ENT;
> typedef CGAL::Lazy_exact_nt<ENT>        LENT;
> typedef CGAL::Simple_cartesian<LENT>   CK;
> typedef CGAL::Segment_Delaunay_graph_traits_without_intersections_2<
> CK,
> CGAL::Integral_domain_without_division_tag
> >  Gt;
> typedef Extended_Segment_Delaunay_graph<Gt>  SDG_2;
> 
> 
> Here is a screenshot of the data:
> 
> <http://cgal-discuss.949826.n4.nabble.com/file/n4657381/Screen_Shot_2013-05-06_at_6.08.28_PM.png>
>  
> 
> I am using the medial axis for doing some shape analysis on architectural
> plans. Plans of buildings are usually difficult because they are full of
> degenerate cases. The segment delaunay algorithms work fine in all the
> number types I thought reasonable to use, but I have found problems with the
> calculation of the circumcenters.
> 
> I found out that if I cast the input data to floats first,
> Segment_Delaunay_graph_filtered_traits_2 works fine with all reasonable
> types (it has no problems calculating the circumcenters). This is a
> workaround that is reasonable in this case, since any meaningful dimensions
> of a building will fit within a float (from thousands of meters to
> millimeters). Otherwise the use of Core::Expr suggested by you works, but,
> on the plan in the image above, it will only work when I use
> Segment_Delaunay_graph_traits_without_intersections_2 (no filtered traits)
> and CORE::Expr as the exact number type (Lazy_exact_nt<Core::Expr> works
> fine).

I am wondering if you should use the following instead for
filtered traits (since the CORE::Expr EK seems to support square
roots exactly):

typedef CGAL::Segment_Delaunay_graph_filtered_traits_2<
       CK,CGAL::Field_with_sqrt_tag,EK,CGAL::Field_with_sqrt_tag>  Gt;

Also, shouldn't you always use "without_intersections" traits
(filtered or non-filtered)? I think your input does not have
intersections in the interiors of segments, right?

A general comment:

The circumcenter computation is considered a construction and in
your use of filtered traits, the CK (CGAL::Simple_cartesian<double>)
kernel is used for constructions. Therefore, the constructions are
not exact. My guess is that for the specific double inputs that
you have, some circumcenter computation is far from the correct
value. When you truncate the doubles to float precision, this
problem does not arise.

When you use the non-filtered traits with CORE::Expr, then even
the constructions are computed exactly, so you do not have the
above problem.


Best,
Panos