Circular Arrangements inexact?

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

Circular Arrangements inexact?

schiefer
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
Reply | Threaded
Open this post in threaded view
|

Re: Circular Arrangements inexact?

Ophir Setter-2
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,
Ophir

On Mon, Mar 23, 2009 at 4:57 PM, Dennis Schieferdecker <[hidden email]> 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

Reply | Threaded
Open this post in threaded view
|

Re: Circular Arrangements inexact?

schiefer
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
Reply | Threaded
Open this post in threaded view
|

Re: Circular Arrangements inexact?

efif
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
Reply | Threaded
Open this post in threaded view
|

Re: Circular Arrangements inexact?

schiefer
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
Reply | Threaded
Open this post in threaded view
|

Re: Circular Arrangements inexact?

schiefer
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
Reply | Threaded
Open this post in threaded view
|

Re: Circular Arrangements inexact?

Monique Teillaud
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
Reply | Threaded
Open this post in threaded view
|

Re: Circular Arrangements inexact?

schiefer
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
Reply | Threaded
Open this post in threaded view
|

Re: Circular Arrangements inexact?

Sylvain Pion
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<CORE::Expr>();

(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