Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] How do I get simple arc information when using conic traits?

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] How do I get simple arc information when using conic traits?


Chronological Thread 
  • From: Efi Fogel <>
  • To:
  • Subject: Re: [cgal-discuss] How do I get simple arc information when using conic traits?
  • Date: Tue, 10 Jan 2017 20:43:25 +0200
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-phdr: 9a23:nq4p1xIm2RsNTLg819mcpTZWNBhigK39O0sv0rFitYgVKfzxwZ3uMQTl6Ol3ixeRBMOAuq4C0bSd6vixESxYuNDa7yBEKMQNHzY+yuwo3CUYSPafDkP6KPO4JwcbJ+9lEGFfwnegLEJOE9z/bVCB6le77DoVBwmtfVEtfre9Scbvid+q3bWy54HLeFcPwyGsZKt7ahSwtwTY8McMxpBzL744jRrPrHwPcOtfwSZkJEmYgg3ntfq254NppiRMp+o6pYkHSrT/Z61+TLpCDT1gPXpy/9zurRCETA2B4TwXXWwS1xZJGAPY9wqpY5HqryGvtvZhwDLIeortXLUsUHKj6b1qQVnmkmAcJjsh+SbWjMJ3y6lUqRbkqx1kyJPPe9KpM691carZON8bXmFcRd15VipbA4r6YZFcIfAGOLN1oYi1iVwBoB/2UQSiBe3oxTJMrnDz1Kw+le8mFFeVj0QbA9sSvSGM/53OP6AIXLXtwQ==

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 <> 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






Archive powered by MHonArc 2.6.18.

Top of Page