How do I get simple arc information when using conic traits?

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

How do I get simple arc information when using conic traits?

KHartmann
If I am using CGAL::Gps_circle_segment_traits_2<Kernel>,
I can get the arc center points and
the arc orientations for any X_monotone_curve_2 with the code
shown below:

  Gen_Polygon_2::Curve_const_iterator curveIter;
  for (curveIter = poly.curves_begin();
       curveIter != poly.curves_end();
       curveIter++)
  {
    const X_monotone_curve_2& curve = (*curveIter);

    if (curve.is_circular())
    {
      double arc_center_x =
         CGAL::to_double( curve.supporting_circle().center().x() );
      double arc_center_y =
         CGAL::to_double( curve.supporting_circle().center().y() );
      bool clockWise =
         curve.orientation() == CGAL::CLOCKWISE
    }
  }

But how would I do the same, if I am using
CGAL::Arr_conic_traits_2<Rat_kernel, Alg_kernel, Nt_traits>?

I don't have "is_circular" or "supporting_circle" available to me
when I am using conic_traits.

I am stuck using conic_traits, since that is what CGAL::offset_polygon_2 uses.
Even though CGAL::offset_polygon_2 always returns line segments and circular arcs.

Reply | Threaded
Open this post in threaded view
|

Re: How do I get simple arc information when using conic traits?

Efi Fogel
Your observation(s) are correct and points to some deficiencies.

1. Conic_point_2 (or _Conic_x_monotone_arc_2 for that matter) are the types of the curves handled by Arr_conic_traits_2. They do not support convenient member functions that return the type of the underlying conic curve (being either a circle, an ellipse, a parabola, or a hyperbola), and if the underlying conic curve is a circle, for example, they do not support a member function that returns the square of the radius for example. However, it is not hard to extract this information from the coefficients of the conic, r, s, t, u, v, and w. Recall that the conic curve is the zero set of the following polynomial:

p(x,y) = r*x^2 + s*y^2 + t*xy + u*x + v*y + w

and a conic that represents a circle is the zero set of the following polynomial:

p(x,y) = (x-a)^2 + (y-b)^2 - R^2

in other words

x^2 + y^2 - 2*a*x - 2*b*y + (a^2 + b^2 - R^2) = 0

which implies that r == s, t == 0, etc.

2. I do not see a reason why CGAL::offset_polygon_2() cannot use Arr_circle_segment_traits_2 instead of Arr_conic_traits_2. (I might be wrong though.) I may try to provide an overload of CGAL::offset_polygon_2() that uses Arr_circle_segment_traits_2 (but it may take some time).


   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On Thu, Jan 5, 2017 at 11:12 PM, KHartmann <[hidden email]> wrote:
If I am using CGAL::Gps_circle_segment_traits_2<Kernel>,
I can get the arc center points and
the arc orientations for any X_monotone_curve_2 with the code
shown below:

  Gen_Polygon_2::Curve_const_iterator curveIter;
  for (curveIter = poly.curves_begin();
       curveIter != poly.curves_end();
       curveIter++)
  {
    const X_monotone_curve_2& curve = (*curveIter);

    if (curve.is_circular())
    {
      double arc_center_x =
         CGAL::to_double( curve.supporting_circle().center().x() );
      double arc_center_y =
         CGAL::to_double( curve.supporting_circle().center().y() );
      bool clockWise =
         curve.orientation() == CGAL::CLOCKWISE
    }
  }

But how would I do the same, if I am using
CGAL::Arr_conic_traits_2<Rat_kernel, Alg_kernel, Nt_traits>?

I don't have "is_circular" or "supporting_circle" available to me
when I am using conic_traits.

I am stuck using conic_traits, since that is what CGAL::offset_polygon_2
uses.
Even though CGAL::offset_polygon_2 always returns line segments and circular
arcs.





--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/How-do-I-get-simple-arc-information-when-using-conic-traits-tp4662448.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
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: How do I get simple arc information when using conic traits?

Efi Fogel
Hi KHartmann,

I've looked a bit more carefully into the second issue. Apparently, there is a good reason to use Arr_conic_traits_2 (or at least not to use Arr_circle_segment_traits_2).

The Arr_circle_segment_traits_2 supports segments and circular arcs. It uses an efficient, yet limited number type called CGAL::Sqrt_extension. If you reach the limitation, you fall back into using a more general traits, e.g., Arr_conic_traits_2, and in this case you do.

The segments supported by Arr_circle_segment_traits_2 can have endpoints with coordinates that are not necessarily rational. However, the underlying line must have rational coefficient. When constructing the (exact) offset we need to construct segments that do not necessarily lie on rational lines. More precisely, say you have a segment S = (s,t) in your original polygon. Let L be the underlying line of the offset segment. L : a * x + b * y + c = 0. Then, a and b are rational, but c in not necessarily so. 

Efi
 

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On Sun, Jan 8, 2017 at 2:35 AM, Efi Fogel <[hidden email]> wrote:
Your observation(s) are correct and points to some deficiencies.

1. Conic_point_2 (or _Conic_x_monotone_arc_2 for that matter) are the types of the curves handled by Arr_conic_traits_2. They do not support convenient member functions that return the type of the underlying conic curve (being either a circle, an ellipse, a parabola, or a hyperbola), and if the underlying conic curve is a circle, for example, they do not support a member function that returns the square of the radius for example. However, it is not hard to extract this information from the coefficients of the conic, r, s, t, u, v, and w. Recall that the conic curve is the zero set of the following polynomial:

p(x,y) = r*x^2 + s*y^2 + t*xy + u*x + v*y + w

and a conic that represents a circle is the zero set of the following polynomial:

p(x,y) = (x-a)^2 + (y-b)^2 - R^2

in other words

x^2 + y^2 - 2*a*x - 2*b*y + (a^2 + b^2 - R^2) = 0

which implies that r == s, t == 0, etc.

2. I do not see a reason why CGAL::offset_polygon_2() cannot use Arr_circle_segment_traits_2 instead of Arr_conic_traits_2. (I might be wrong though.) I may try to provide an overload of CGAL::offset_polygon_2() that uses Arr_circle_segment_traits_2 (but it may take some time).


   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On Thu, Jan 5, 2017 at 11:12 PM, KHartmann <[hidden email]> wrote:
If I am using CGAL::Gps_circle_segment_traits_2<Kernel>,
I can get the arc center points and
the arc orientations for any X_monotone_curve_2 with the code
shown below:

  Gen_Polygon_2::Curve_const_iterator curveIter;
  for (curveIter = poly.curves_begin();
       curveIter != poly.curves_end();
       curveIter++)
  {
    const X_monotone_curve_2& curve = (*curveIter);

    if (curve.is_circular())
    {
      double arc_center_x =
         CGAL::to_double( curve.supporting_circle().center().x() );
      double arc_center_y =
         CGAL::to_double( curve.supporting_circle().center().y() );
      bool clockWise =
         curve.orientation() == CGAL::CLOCKWISE
    }
  }

But how would I do the same, if I am using
CGAL::Arr_conic_traits_2<Rat_kernel, Alg_kernel, Nt_traits>?

I don't have "is_circular" or "supporting_circle" available to me
when I am using conic_traits.

I am stuck using conic_traits, since that is what CGAL::offset_polygon_2
uses.
Even though CGAL::offset_polygon_2 always returns line segments and circular
arcs.





--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/How-do-I-get-simple-arc-information-when-using-conic-traits-tp4662448.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
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: How do I get simple arc information when using conic traits?

KHartmann
Thank you for researching this issue!  I will attempt to follow your advice #1.

One quick additional question.   Is there a self intersection test for General_Polygon_2?
Polygon_2 has an is_simple() function, but General_Polygon_2 doesn't.
Since there isn't such a function, is there a way for me to do the test that doesn't take O(n^2) time?


Efi Fogel wrote
Hi KHartmann,

I've looked a bit more carefully into the second issue. Apparently, there
is a good reason to use Arr_conic_traits_2 (or at least not to use
Arr_circle_segment_traits_2).

The Arr_circle_segment_traits_2 supports segments and circular arcs. It
uses an efficient, yet limited number type called CGAL::Sqrt_extension. If
you reach the limitation, you fall back into using a more general traits,
e.g., Arr_conic_traits_2, and in this case you do.

The segments supported by Arr_circle_segment_traits_2 can have endpoints
with coordinates that are not necessarily rational. However, the underlying
line must have rational coefficient. When constructing the (exact) offset
we need to construct segments that do not necessarily lie on rational
lines. More precisely, say you have a segment S = (s,t) in your original
polygon. Let L be the underlying line of the offset segment. L : a * x + b
* y + c = 0. Then, a and b are rational, but c in not necessarily so.

Efi


   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On Sun, Jan 8, 2017 at 2:35 AM, Efi Fogel <[hidden email]> wrote:

> Your observation(s) are correct and points to some deficiencies.
>
> 1. Conic_point_2 (or _Conic_x_monotone_arc_2 for that matter) are the
> types of the curves handled by Arr_conic_traits_2. They do not support
> convenient member functions that return the type of the underlying conic
> curve (being either a circle, an ellipse, a parabola, or a hyperbola), and
> if the underlying conic curve is a circle, for example, they do not support
> a member function that returns the square of the radius for example.
> However, it is not hard to extract this information from the coefficients
> of the conic, r, s, t, u, v, and w. Recall that the conic curve is the zero
> set of the following polynomial:
>
> p(x,y) = r*x^2 + s*y^2 + t*xy + u*x + v*y + w
>
> and a conic that represents a circle is the zero set of the following
> polynomial:
>
> p(x,y) = (x-a)^2 + (y-b)^2 - R^2
>
> in other words
>
> x^2 + y^2 - 2*a*x - 2*b*y + (a^2 + b^2 - R^2) = 0
>
> which implies that r == s, t == 0, etc.
>
> 2. I do not see a reason why CGAL::offset_polygon_2() cannot use
> Arr_circle_segment_traits_2 instead of Arr_conic_traits_2. (I might be
> wrong though.) I may try to provide an overload of CGAL::offset_polygon_2()
> that uses Arr_circle_segment_traits_2 (but it may take some time).
>
>
>    ____  _        ____             _
>   /_____/_) o    /__________  __  //
>  (____ (   (    (    (_/ (_/-(-'_(/
>                          _/
>
>
>
> On Thu, Jan 5, 2017 at 11:12 PM, KHartmann <[hidden email]> wrote:
>
>> If I am using CGAL::Gps_circle_segment_traits_2<Kernel>,
>> I can get the arc center points and
>> the arc orientations for any X_monotone_curve_2 with the code
>> shown below:
>>
>>   Gen_Polygon_2::Curve_const_iterator curveIter;
>>   for (curveIter = poly.curves_begin();
>>        curveIter != poly.curves_end();
>>        curveIter++)
>>   {
>>     const X_monotone_curve_2& curve = (*curveIter);
>>
>>     if (curve.is_circular())
>>     {
>>       double arc_center_x =
>>          CGAL::to_double( curve.supporting_circle().center().x() );
>>       double arc_center_y =
>>          CGAL::to_double( curve.supporting_circle().center().y() );
>>       bool clockWise =
>>          curve.orientation() == CGAL::CLOCKWISE
>>     }
>>   }
>>
>> But how would I do the same, if I am using
>> CGAL::Arr_conic_traits_2<Rat_kernel, Alg_kernel, Nt_traits>?
>>
>> I don't have "is_circular" or "supporting_circle" available to me
>> when I am using conic_traits.
>>
>> I am stuck using conic_traits, since that is what CGAL::offset_polygon_2
>> uses.
>> Even though CGAL::offset_polygon_2 always returns line segments and
>> circular
>> arcs.
>>
>>
>>
>>
>>
>> --
>> View this message in context: http://cgal-discuss.949826.n4.
>> nabble.com/How-do-I-get-simple-arc-information-when-using-
>> conic-traits-tp4662448.html
>> Sent from the cgal-discuss mailing list archive at Nabble.com.
>>
>> --
>> 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: How do I get simple arc information when using conic traits?

Efi Fogel
Yes, you can insert it into an arrangement and count, e.g., the number of faces. For a valid (general) polygon, the result should be 2 faces. The polygon itself and the unbounded face.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On Mon, Jan 9, 2017 at 11:27 PM, KHartmann <[hidden email]> wrote:
Thank you for researching this issue!  I will attempt to follow your advice
#1.

One quick additional question.   Is there a self intersection test for
General_Polygon_2?
Polygon_2 has an is_simple() function, but General_Polygon_2 doesn't.
Since there isn't such a function, is there a way for me to do the test that
doesn't take O(n^2) time?



Efi Fogel wrote
> Hi KHartmann,
>
> I've looked a bit more carefully into the second issue. Apparently, there
> is a good reason to use Arr_conic_traits_2 (or at least not to use
> Arr_circle_segment_traits_2).
>
> The Arr_circle_segment_traits_2 supports segments and circular arcs. It
> uses an efficient, yet limited number type called CGAL::Sqrt_extension. If
> you reach the limitation, you fall back into using a more general traits,
> e.g., Arr_conic_traits_2, and in this case you do.
>
> The segments supported by Arr_circle_segment_traits_2 can have endpoints
> with coordinates that are not necessarily rational. However, the
> underlying
> line must have rational coefficient. When constructing the (exact) offset
> we need to construct segments that do not necessarily lie on rational
> lines. More precisely, say you have a segment S = (s,t) in your original
> polygon. Let L be the underlying line of the offset segment. L : a * x + b
> * y + c = 0. Then, a and b are rational, but c in not necessarily so.
>
> Efi
>
>
>    ____  _        ____             _
>   /_____/_) o    /__________  __  //
>  (____ (   (    (    (_/ (_/-(-'_(/
>                          _/
>
>
>
> On Sun, Jan 8, 2017 at 2:35 AM, Efi Fogel &lt;

> efifogel@

> &gt; wrote:
>
>> Your observation(s) are correct and points to some deficiencies.
>>
>> 1. Conic_point_2 (or _Conic_x_monotone_arc_2 for that matter) are the
>> types of the curves handled by Arr_conic_traits_2. They do not support
>> convenient member functions that return the type of the underlying conic
>> curve (being either a circle, an ellipse, a parabola, or a hyperbola),
>> and
>> if the underlying conic curve is a circle, for example, they do not
>> support
>> a member function that returns the square of the radius for example.
>> However, it is not hard to extract this information from the coefficients
>> of the conic, r, s, t, u, v, and w. Recall that the conic curve is the
>> zero
>> set of the following polynomial:
>>
>> p(x,y) = r*x^2 + s*y^2 + t*xy + u*x + v*y + w
>>
>> and a conic that represents a circle is the zero set of the following
>> polynomial:
>>
>> p(x,y) = (x-a)^2 + (y-b)^2 - R^2
>>
>> in other words
>>
>> x^2 + y^2 - 2*a*x - 2*b*y + (a^2 + b^2 - R^2) = 0
>>
>> which implies that r == s, t == 0, etc.
>>
>> 2. I do not see a reason why CGAL::offset_polygon_2() cannot use
>> Arr_circle_segment_traits_2 instead of Arr_conic_traits_2. (I might be
>> wrong though.) I may try to provide an overload of
>> CGAL::offset_polygon_2()
>> that uses Arr_circle_segment_traits_2 (but it may take some time).
>>
>>
>>    ____  _        ____             _
>>   /_____/_) o    /__________  __  //
>>  (____ (   (    (    (_/ (_/-(-'_(/
>>                          _/
>>
>>
>>
>> On Thu, Jan 5, 2017 at 11:12 PM, KHartmann &lt;

> khartmann@

> &gt; wrote:
>>
>>> If I am using CGAL::Gps_circle_segment_traits_2
> <Kernel>
> ,
>>> I can get the arc center points and
>>> the arc orientations for any X_monotone_curve_2 with the code
>>> shown below:
>>>
>>>   Gen_Polygon_2::Curve_const_iterator curveIter;
>>>   for (curveIter = poly.curves_begin();
>>>        curveIter != poly.curves_end();
>>>        curveIter++)
>>>   {
>>>     const X_monotone_curve_2& curve = (*curveIter);
>>>
>>>     if (curve.is_circular())
>>>     {
>>>       double arc_center_x =
>>>          CGAL::to_double( curve.supporting_circle().center().x() );
>>>       double arc_center_y =
>>>          CGAL::to_double( curve.supporting_circle().center().y() );
>>>       bool clockWise =
>>>          curve.orientation() == CGAL::CLOCKWISE
>>>     }
>>>   }
>>>
>>> But how would I do the same, if I am using
>>> CGAL::Arr_conic_traits_2&lt;Rat_kernel, Alg_kernel, Nt_traits&gt;?
>>>
>>> I don't have "is_circular" or "supporting_circle" available to me
>>> when I am using conic_traits.
>>>
>>> I am stuck using conic_traits, since that is what CGAL::offset_polygon_2
>>> uses.
>>> Even though CGAL::offset_polygon_2 always returns line segments and
>>> circular
>>> arcs.
>>>
>>>
>>>
>>>
>>>
>>> --
>>> View this message in context: http://cgal-discuss.949826.n4.
>>> nabble.com/How-do-I-get-simple-arc-information-when-using-
>>> conic-traits-tp4662448.html
>>> Sent from the cgal-discuss mailing list archive at Nabble.com.
>>>
>>> --
>>> 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





--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/How-do-I-get-simple-arc-information-when-using-conic-traits-tp4662448p4662451.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
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: How do I get simple arc information when using conic traits?

KHartmann
Perfect!  Thanks!

------------------------------------------------------------------------

Yes, you can insert it into an arrangement and count, e.g., the number of
faces. For a valid (general) polygon, the result should be 2 faces. The
polygon itself and the unbounded face.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On Mon, Jan 9, 2017 at 11:27 PM, KHartmann <[hidden email]> wrote:


> One quick additional question.   Is there a self intersection test for
> General_Polygon_2?
> Polygon_2 has an is_simple() function, but General_Polygon_2 doesn't.
> Since there isn't such a function, is there a way for me to do the test
> that
> doesn't take O(n^2) time?
>