# Circular Arrangements inexact?

9 messages
Open this post in threaded view
|

## Circular Arrangements inexact?

 Hi, I am trying to compute exact circular arrangements with CGAL but even with a simple example I run into trouble: I use three circles at (0.01, 0.00), (-0.01, 0.00) and (0.00, 0.01) with a radius of 0.01 each. Thus the circles intersect at (0.00, 0.00), (0.01, 0.01) and (-0.01, 0.01). After computing the arrangement, I iterate through the border (i.e. the halfedges) of each face and print the source and target of each edge. Here I saw two things, that should not happen with exact calculations: First, there are edges which seem to have the same source and target, but when comparing them with the appropriate equal-predicate they are reported to be different. Secondly, e.g. instead of a location at (0.00, 0.00) a location at (0.00, -2.50766e-11) is reported. Are the circular arrangements currently not implemented for exact calculation or am I doing something wrong? (I am using the CGAL::Exact_circular_kernel_2 and the CGAL::Arr_circle_segment_traits_2) bye, Dennis -- Dennis Schieferdecker Universität Karlsruhe (TH)           | Fon  : +49 (721) 608-6781 Institut für Theoretische Informatik | Fax  : +49 (721) 608-3088 Am Fasanengarten 5, Zimmer 220       | D-76131 Karlsruhe, Germany           | Email: [hidden email] ----------------------------------------------------------------- -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Circular Arrangements inexact?

 The problem is probably that 0.01 is not translated to 1/100 in an exact manner.You should construct 1/100 using a rational number constructor; probably something like: Kernel::FT(1, 100).Regards, OphirOn Mon, Mar 23, 2009 at 4:57 PM, Dennis Schieferdecker wrote: Hi, I am trying to compute exact circular arrangements with CGAL but even with a simple example I run into trouble: I use three circles at (0.01, 0.00), (-0.01, 0.00) and (0.00, 0.01) with a radius of 0.01 each. Thus the circles intersect at (0.00, 0.00), (0.01, 0.01) and (-0.01, 0.01). After computing the arrangement, I iterate through the border (i.e. the halfedges) of each face and print the source and target of each edge. Here I saw two things, that should not happen with exact calculations: First, there are edges which seem to have the same source and target, but when comparing them with the appropriate equal-predicate they are reported to be different. Secondly, e.g. instead of a location at (0.00, 0.00) a location at (0.00, -2.50766e-11) is reported. Are the circular arrangements currently not implemented for exact calculation or am I doing something wrong? (I am using the CGAL::Exact_circular_kernel_2 and the CGAL::Arr_circle_segment_traits_2) bye, Dennis -- Dennis Schieferdecker Universität Karlsruhe (TH)           | Fon  : +49 (721) 608-6781 Institut für Theoretische Informatik | Fax  : +49 (721) 608-3088 Am Fasanengarten 5, Zimmer 220       | D-76131 Karlsruhe, Germany           | Email: [hidden email] ----------------------------------------------------------------- -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Circular Arrangements inexact?

 Ophir Setter schrieb: > The problem is probably that 0.01 is not translated to 1/100 in an > exact manner. > You should construct 1/100 using a rational number constructor; > probably something like: Kernel::FT(1, 100). > Thanks that did the trick (and significantly decreased the number of faces with my larger setup). Maybe you could help me with another type problem later in my program? After having computed the circular arrangement, I need to perform several calculations with the vertices of the arrangement. Unfortunately the points they represent are of type Traits::Point_2 instead od Kernel::Point_2 and use a different numerical type ( Traits::CoordNT, i.e. one_root_number< Kermel::FT >). Here, I run into a problem, since I cannot perform the typical operations I can with type Kernel::Point_2 and by converting Traits::Point_2 to Kernel::Point_2 I losse my exactness. In principle I need to compute the point that lies in the middle of two vertices and the orientation of three vertices. Also, a related problem is the compuatation of the intersection point of one edge E of a face of the arrangement with a line L. Line L is defined by two points of type Traits::Point_2 and Edge E is represented as X_monotone_curve using a number type Traits::CoordNT. Now, the intersection functor requires two lines of the same type. Thus I have to represent line L as X_monotone_curve. Unfortunately, there is no way to contruct one of two points of type Traits::Point_2, only of type Kernel::Point_2. Is there another (obvious) transformation I am missing, or are the Traits::Point_2 the "end of the road" with regards to the reusability in further calculations? bye Dennis -- Dennis Schieferdecker Universität Karlsruhe (TH)           | Fon  : +49 (721) 608-6781 Institut für Theoretische Informatik | Fax  : +49 (721) 608-3088 Am Fasanengarten 5, Zimmer 220       | D-76131 Karlsruhe, Germany           | Email: [hidden email] ----------------------------------------------------------------- -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Circular Arrangements inexact?

 Dennis Schieferdecker wrote: > Ophir Setter schrieb: >   >> The problem is probably that 0.01 is not translated to 1/100 in an >> exact manner. >> You should construct 1/100 using a rational number constructor; >> probably something like: Kernel::FT(1, 100). >> >>     > Thanks that did the trick (and significantly decreased the number of > faces with my larger setup). Maybe you could help me with another type > problem later in my program? > > After having computed the circular arrangement, I need to perform > several calculations with the vertices of the arrangement. Unfortunately > the points they represent are of type Traits::Point_2 instead od > Kernel::Point_2 and use a different numerical type ( Traits::CoordNT, > i.e. one_root_number< Kermel::FT >). Here, I run into a problem, since I > cannot perform the typical operations I can with type Kernel::Point_2 >   What operations are you missing? > and by converting Traits::Point_2 to Kernel::Point_2 I losse my > exactness. In principle I need to compute the point that lies in the > middle of two vertices and the orientation of three vertices. > Also, a related problem is the compuatation of the intersection point of > one edge E of a face of the arrangement with a line L. Line L is defined > by two points of type Traits::Point_2 and Edge E is represented as > X_monotone_curve using a number type Traits::CoordNT. Now, the > intersection functor requires two lines of the same type. Thus I have to > represent line L as X_monotone_curve. Unfortunately, there is no way to > contruct one of two points of type Traits::Point_2, only of type > Kernel::Point_2. >   The traits supports curves that are either circular arcs or segments the coefficients of which are rational, and it contains a functor that computes the intersection between any pairs of curves supported by the traits. Intersections between segments the coefficients of which are not rational is not supported, at least not by the traits class. > Is there another (obvious) transformation I am missing, or are the > Traits::Point_2 the "end of the road" with regards to the reusability in > further calculations? > > bye > Dennis >   There are two traits that support circular arcs and segments in the arrangement package, namely, Arr_circle_segment_traits_2 and Arr_circular_line_arc_traits_2. The latter may support more operations, as it is based on a CircularKernel. --   ____  _        ____             _  /_____/_) o    /__________  __  // (____ (   (    (    (_/ (_/-(-'_(/                         _/ -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Circular Arrangements inexact?

 Efraim Fogel schrieb: > What operations are you missing? - computing the orientation of three points - creating vectors with these points and performing vector operations like adding vectors etc. > There are two traits that support circular arcs and segments in the > arrangement package, namely, Arr_circle_segment_traits_2 and > Arr_circular_line_arc_traits_2. The latter may support more > operations, as it is based on a CircularKernel. I tried the latter one, but I after inserting circles into the arrangement and trying to traverse the faces with the Face_const_iterator in an otherwise empty for-loop, the program fails with an invalid free() operation. To insert the circles I create a Kernel::Circle_2 and convert it to a Kernel::Circular_Arc_2 and then to an Traits::Curve_2 which I insert into the arrangement. My ultimate goal is to compute a point for each face of the arrangement that lies within the face. Maybe this information is more useful. bye dennis -- Dennis Schieferdecker Universität Karlsruhe (TH)           | Fon  : +49 (721) 608-6781 Institut für Theoretische Informatik | Fax  : +49 (721) 608-3088 Am Fasanengarten 5, Zimmer 220       | D-76131 Karlsruhe, Germany           | Email: [hidden email] ----------------------------------------------------------------- -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Circular Arrangements inexact?

 Dennis Schieferdecker schrieb: >> There are two traits that support circular arcs and segments in the >> arrangement package, namely, Arr_circle_segment_traits_2 and >> Arr_circular_line_arc_traits_2. The latter may support more >> operations, as it is based on a CircularKernel. >>     > I tried the latter one, but I after inserting circles into the > arrangement and trying to traverse the faces with the > Face_const_iterator in an otherwise empty for-loop, the program fails > with an invalid free() operation. To insert the circles I create a > Kernel::Circle_2 and convert it to a Kernel::Circular_Arc_2 and then to > an Traits::Curve_2 which I insert into the arrangement. >   Correction: The error already happens when inserting the circle into the arrangement, using Arr_circular_line_arc_traits_2 as Traits class. -- Dennis Schieferdecker Universität Karlsruhe (TH)           | Fon  : +49 (721) 608-6781 Institut für Theoretische Informatik | Fax  : +49 (721) 608-3088 Am Fasanengarten 5, Zimmer 220       | D-76131 Karlsruhe, Germany           | Email: [hidden email] ----------------------------------------------------------------- -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Circular Arrangements inexact?

 In reply to this post by efif Efraim Fogel wrote: > Dennis Schieferdecker wrote: >> Ophir Setter schrieb: >>   >>> The problem is probably that 0.01 is not translated to 1/100 in an >>> exact manner. >>> You should construct 1/100 using a rational number constructor; >>> probably something like: Kernel::FT(1, 100). >>> >>>     >> Thanks that did the trick (and significantly decreased the number of >> faces with my larger setup). Maybe you could help me with another type >> problem later in my program? >> >> After having computed the circular arrangement, I need to perform >> several calculations with the vertices of the arrangement. Unfortunately >> the points they represent are of type Traits::Point_2 instead od >> Kernel::Point_2 and use a different numerical type ( Traits::CoordNT, >> i.e. one_root_number< Kermel::FT >). Here, I run into a problem, since I >> cannot perform the typical operations I can with type Kernel::Point_2 >> and by converting Traits::Point_2 to Kernel::Point_2 I losse my >> exactness. >> In principle I need to compute the point that lies in the >> middle of two vertices and the orientation of three vertices. > There are two traits that support circular arcs and segments in the > arrangement package, namely, Arr_circle_segment_traits_2 and > Arr_circular_line_arc_traits_2. The latter may support more operations, > as it is based on a CircularKernel. Hi Dennis, The Circular kernel does not provide the orientation of three Circular_arc_point_2's either. The coordinates of such 3 points are algebraic numbers of degree 2 that do not necessarily lie in the same extension. We are thinking of adding new operations in the CGAL::Root_of_2 number type, to allow such computations, this will not be available in a close future. What you might want to do is convert the Circular_arc_point_2's computed by the arrangement into Point_2< Cartesian< Core::Expr > >, then all functionalities of the cgal Kernel would be available on them. I have not tried but I guess it would work (you probably have to do the conversion of coordinates "by hand"). I am afraid this would be rather slow, though. Best         Monique Teillaud -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Circular Arrangements inexact?

 Monique Teillaud schrieb: > What you might want to do is convert the Circular_arc_point_2's > computed by the arrangement into Point_2< Cartesian< Core::Expr > >, > then all functionalities of the cgal Kernel would be available on them. > I have not tried but I guess it would work (you probably have to do > the conversion of coordinates "by hand"). I am afraid this would be > rather slow, though. Thanks for the information. I have tried to do an exact conversion but it seems that this cannot be done. In particular, I don't seem to be able to convert the MP_Float type to the respective CORE type without going over the double type. I also tried to use the circular Kernel based on the CORE::Expr number type but that proved to be much too slow. bye Dennis -- Dennis Schieferdecker Universität Karlsruhe (TH)           | Fon  : +49 (721) 608-6781 Institut für Theoretische Informatik | Fax  : +49 (721) 608-3088 Am Fasanengarten 5, Zimmer 220       | D-76131 Karlsruhe, Germany           | Email: [hidden email] ----------------------------------------------------------------- -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Circular Arrangements inexact?

 Administrator Dennis Schieferdecker a écrit : > Monique Teillaud schrieb: >> What you might want to do is convert the Circular_arc_point_2's >> computed by the arrangement into Point_2< Cartesian< Core::Expr > >, >> then all functionalities of the cgal Kernel would be available on them. >> I have not tried but I guess it would work (you probably have to do >> the conversion of coordinates "by hand"). I am afraid this would be >> rather slow, though. > Thanks for the information. I have tried to do an exact conversion but > it seems that this cannot be done. In particular, I don't seem to be > able to convert the MP_Float type to the respective CORE type without > going over the double type. You can try :   CGAL::MP_Float m;   CORE::Expr e = m.to_rational(); (I don't make any promise that you will get usable speed though) > I also tried to use the circular Kernel based on the CORE::Expr number > type but that proved to be much too slow. -- Sylvain Pion INRIA Sophia-Antipolis Geometrica Project-Team CGAL, http://cgal.org/-- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss