Construct_hyperbolic_segment_2 does not terminate

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

Construct_hyperbolic_segment_2 does not terminate

Stefan Witzel
Hello,

Here is an obscure issue: I have two points p and q for which
Construct_hyperbolic_segment_2 does not terminate. The points are
approximately Hyperbolic_point_2(0.9666536103464638,-0.0141826279439945)
and Hyperbolic_point_2(0.9666536103464638,0.0141826279439945) but I
don't know how I can dump them exactly. They arise as vertices of a
hyperbolic Voronoi diagram. Any suggestions?

Best,
Stefan

Some relevant code:

typedef CGAL::Hyperbolic_Delaunay_triangulation_traits_2<>  Gt;
typedef typename Gt::Hyperbolic_point_2                     Hyperbolic_point_2;
typedef Gt::Construct_hyperbolic_segment_2
Construct_hyperbolic_segment_2;

Hyperbolic_point_2 p = ...;
Hyperbolic_point_2 q = ...;
std::cerr << "Lets try...";
Construct_hyperbolic_segment_2(p,q);
std::cerr << "...done"; // This point won't be reached

--
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: Construct_hyperbolic_segment_2 does not terminate

Stefan Witzel
Hi,

Am Do., 20. Juni 2019 um 14:46 Uhr schrieb Stefan Witzel <[hidden email]>:
> Here is an obscure issue: I have two points p and q for which
> Construct_hyperbolic_segment_2 does not terminate. The points are
> approximately Hyperbolic_point_2(0.9666536103464638,-0.0141826279439945)
> and Hyperbolic_point_2(0.9666536103464638,0.0141826279439945) but I
> don't know how I can dump them exactly. They arise as vertices of a
> hyperbolic Voronoi diagram. Any suggestions?

Actually it did terminate after minutes. So this must have to do with
the exact calculations, climbing up some tower of quadratic
extensions?
I will use the occasion to ask a bit more about exact/inexact calculations:
1. My points do actually come from a quadratic extension of Q (but
from a different program); is there a good way to feed them exactly
into cgal?
2. What would be a good alternative to the time-consuming exact
calculations? If I use

  typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
  typedef CGAL::Hyperbolic_Delaunay_triangulation_traits_2<K> Gt;

the program is very fast but also the outcome is very unsatisfactory.
Am I right to assume that I should use

  typedef CGAL::Hyperbolic_Delaunay_triangulation_CK_traits_2<> Gt;

? In that case, can someone indicate how to cast a
Hyperbolic_segment_2 to a segment or a circular arc? In principle I
appreciate this abstraction between interface and implementation but
in practice I find that the interface doesn't provide what I need (see
a previous discussion) so I need to access the actual implementation
and then digging into a template with three nested template parameters
is beyond me.

Best,
Stefan

--
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: Construct_hyperbolic_segment_2 does not terminate

teillaud
Administrator
Hi,

I am travelling these days and cannot spend a lot of time on emails, so my answer right now will not be very detailed.  

It seems to me that you would need a general purpose hyperbolic geometry kernel, similar to what CGAL has for Euclidean geometry. I agree that it would be nice if we could have that in CGAL, but it would require some manpower...
What CGAL currently has for hyperbolic geometry is only Traits classes, specifically targeted at being used by the hyperbolic Delaunay triangulations package (rather than by users), that's why you don't find everything you need.

In fact, directly using the 2D circular geometry kernel could be better for you
see https://doc.cgal.org/latest/Manual/packages.html#PkgCircularKernel2
Its interface is about circles and circular arcs in Euclidean plane, not about hyperbolic geometry. Still, as a mathematician, you know how hyperbolic segments are constructed in the Poincaré disk and you can probably easily translate between the two geometries.

Note that the circular kernel is using some number types for quadratic extensions of Q (see "Roots of Polynomials" in the Reference Manual), in which you might feed your point coordinates.

Hope this helps.
Best,
--
Monique Teillaud
https://members.loria.fr/Monique.Teillaud/
INRIA Nancy - Grand Est, LORIA
Institut National de Recherche en Informatique et Automatique

----- Le 20 Juin 19, à 9:31, Stefan Witzel [hidden email] a écrit :

> Hi,
>
> Am Do., 20. Juni 2019 um 14:46 Uhr schrieb Stefan Witzel <[hidden email]>:
>> Here is an obscure issue: I have two points p and q for which
>> Construct_hyperbolic_segment_2 does not terminate. The points are
>> approximately Hyperbolic_point_2(0.9666536103464638,-0.0141826279439945)
>> and Hyperbolic_point_2(0.9666536103464638,0.0141826279439945) but I
>> don't know how I can dump them exactly. They arise as vertices of a
>> hyperbolic Voronoi diagram. Any suggestions?
>
> Actually it did terminate after minutes. So this must have to do with
> the exact calculations, climbing up some tower of quadratic
> extensions?
> I will use the occasion to ask a bit more about exact/inexact calculations:
> 1. My points do actually come from a quadratic extension of Q (but
> from a different program); is there a good way to feed them exactly
> into cgal?
> 2. What would be a good alternative to the time-consuming exact
> calculations? If I use
>
>  typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
>  typedef CGAL::Hyperbolic_Delaunay_triangulation_traits_2<K> Gt;
>
> the program is very fast but also the outcome is very unsatisfactory.
> Am I right to assume that I should use
>
>  typedef CGAL::Hyperbolic_Delaunay_triangulation_CK_traits_2<> Gt;
>
> ? In that case, can someone indicate how to cast a
> Hyperbolic_segment_2 to a segment or a circular arc? In principle I
> appreciate this abstraction between interface and implementation but
> in practice I find that the interface doesn't provide what I need (see
> a previous discussion) so I need to access the actual implementation
> and then digging into a template with three nested template parameters
> is beyond me.
>
> Best,
> Stefan
>
> --
> 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: Construct_hyperbolic_segment_2 does not terminate

Stefan Witzel
Hi Monique,

Thank you! I do appreciate the time you take to answer my questions, even while traveling.

Best,
Stefan

Monique Teillaud <[hidden email]> schrieb am Fr., 21. Juni 2019, 00:19:
Hi,

I am travelling these days and cannot spend a lot of time on emails, so my answer right now will not be very detailed. 

It seems to me that you would need a general purpose hyperbolic geometry kernel, similar to what CGAL has for Euclidean geometry. I agree that it would be nice if we could have that in CGAL, but it would require some manpower...
What CGAL currently has for hyperbolic geometry is only Traits classes, specifically targeted at being used by the hyperbolic Delaunay triangulations package (rather than by users), that's why you don't find everything you need.

In fact, directly using the 2D circular geometry kernel could be better for you
see https://doc.cgal.org/latest/Manual/packages.html#PkgCircularKernel2
Its interface is about circles and circular arcs in Euclidean plane, not about hyperbolic geometry. Still, as a mathematician, you know how hyperbolic segments are constructed in the Poincaré disk and you can probably easily translate between the two geometries.

Note that the circular kernel is using some number types for quadratic extensions of Q (see "Roots of Polynomials" in the Reference Manual), in which you might feed your point coordinates.

Hope this helps.
Best,
--
Monique Teillaud
https://members.loria.fr/Monique.Teillaud/
INRIA Nancy - Grand Est, LORIA
Institut National de Recherche en Informatique et Automatique

----- Le 20 Juin 19, à 9:31, Stefan Witzel [hidden email] a écrit :

> Hi,
>
> Am Do., 20. Juni 2019 um 14:46 Uhr schrieb Stefan Witzel <[hidden email]>:
>> Here is an obscure issue: I have two points p and q for which
>> Construct_hyperbolic_segment_2 does not terminate. The points are
>> approximately Hyperbolic_point_2(0.9666536103464638,-0.0141826279439945)
>> and Hyperbolic_point_2(0.9666536103464638,0.0141826279439945) but I
>> don't know how I can dump them exactly. They arise as vertices of a
>> hyperbolic Voronoi diagram. Any suggestions?
>
> Actually it did terminate after minutes. So this must have to do with
> the exact calculations, climbing up some tower of quadratic
> extensions?
> I will use the occasion to ask a bit more about exact/inexact calculations:
> 1. My points do actually come from a quadratic extension of Q (but
> from a different program); is there a good way to feed them exactly
> into cgal?
> 2. What would be a good alternative to the time-consuming exact
> calculations? If I use
>
>  typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
>  typedef CGAL::Hyperbolic_Delaunay_triangulation_traits_2<K> Gt;
>
> the program is very fast but also the outcome is very unsatisfactory.
> Am I right to assume that I should use
>
>  typedef CGAL::Hyperbolic_Delaunay_triangulation_CK_traits_2<> Gt;
>
> ? In that case, can someone indicate how to cast a
> Hyperbolic_segment_2 to a segment or a circular arc? In principle I
> appreciate this abstraction between interface and implementation but
> in practice I find that the interface doesn't provide what I need (see
> a previous discussion) so I need to access the actual implementation
> and then digging into a template with three nested template parameters
> is beyond me.
>
> Best,
> Stefan
>
> --
> 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