CGAL users discussion list

["Ch'Gans" <>]

On 5 April 2016 at 19:39, Efi Fogel 
<>
 wrote:
> On Tue, Apr 5, 2016 at 1:18 AM, Ch'Gans 
> <>
>  wrote:

[...]

>> Hi Efi,
>>
>> I'm interested to see this feature implemented (offset/inset of general
>> polygons).
>
>
> Very well
>
>>
>>
>> I had a quick look at the following files:
>> CGAL/approximated_offset_2.h
>> CGAL/offset_polygon_2.h
>> CGAL/Minkowski_sum_2/Exact_offset_base_2.h
>> CGAL/Minkowski_sum_2/Approx_offset_base_2.h
>> CGAL/Minkowski_sum_2/Offset_conv_2.h
>> CGAL/Minkowski_sum_2/Offset_decomp_2.h
>>
>> And AFAIU, the work-horse for offsetting/insetting polygons is located
>> in Exact_offset_base_2.h and Approx_offset_base_2.h.
>
>
> So far I fully agree.
>
>>
>> The synopsis of _offset_polygon being:
>>   Using vertex circulator:
>>    - 1. calculate current OP1 (first offset edge point, assuming linear
>> edge)
>>    - 2. connect previous OP2 to current OP1 using an arc if needed
>>    - 3. calculate current OP2 (second offset edge point, assuming linear
>> edge)
>>    - 4. connect current OP1 to current OP2 using a line
>>   Finally:
>>    - 5. connect last OP2 to first OP1 using an arc if needed
>
>
> It sounds right. Notice that I'm not an author of this component, so I read
> the code just as you do.
>>
>>
>> To make _offset_polygon() works with general polygons, one would have
>> to implement this modified synopsis:
>>   Using vertex circulator:
>>     - 1. Calculate OP1 with the foreknowledge of the edge 'type' (arc
>> or segment). In case of arc, OP1 is the extension of X1 (by a distance
>> of offset radius) along the semi-line [C, X1] (C being the center of
>> the supporting circle defined by X1, X2 and a radius).
>>     - 2. Connect previous OP2 to current OP1 using an arc if needed
>> (same as current implementation)
>>     - 3. Calculate OP2 (same way as OP1)
>>     - 4. Connect OP1 to OP2 with the foreknowledge of the edge 'type'
>> (arc or segment). In case of arc, the connection is an arc defined by
>> OP1, OP2 and the original radius augmented by the offset radius
>>   Finally
>>     - 5. Connect last OP2 to first OP1 using an arc (same as current
>> implementation)
>
>
> This sounds more or less right, but (i) I'm semi guessing, and (ii) there
> might be more cases t oconsider. Consider a concave general polygon that
> comprises linear segments and circular arcs. Assume it has a circular arc c
> one of the endpoints of which, say p, is a reflex vertex, so the tangent of
> c at p penetrates the general polygon at the tangency point p.
>
> - The offset of the endpoint p is a circular arc the radius of which is the
> offset radius.
> - The offset of the arc c is an arc with radius which is the difference of
> the original radius and the offset radius.
>
> The above holds not only for arcs that have reflex endpoints, but for arcs
> that are parts of concave pieces of the general polygon. I guess you need to
> determine whether to add or subtract radii and what to do when the
> subtraction yields a negative radius.

yes, you are right, It took me some times to visualise the case...

I might be able to use the direction of the arc, if the arc makes a
left turn, the radius of the offset arc is the original radius
expanded by the offset radius, if the arc makes a right turn, then the
radius of the offset arc is the original arc shrunk by the offset
radius, in case of negative result I should use the absolute value of
the result, and use the radial symmetric.

I think it's time for me to give it a go and focus first on nominal test 
cases.

>>
>> I haven't try to hack/code anything so far, this is just my
>> understanding of the existing code. Do you think this simple approach
>> might work or did I missed something important?
>>
>> If I was to implement this (in the exact case), as a starting point,
>> what about adding this function to Exact_offset_base_2:
>>
>> template <class OutputIterator>
>> OutputIterator _offset_polygon (const typename
>> CGAL::Gps_traits_2<Traits_2>::Polygon_2& pgn,
>>                                                    CGAL::Orientation
>> orient,
>>                                                    const Rational& r,
>>                                                    unsigned int cycle_id,
>>                                                    OutputIterator oi)
>> const;
>>
>
> Perhaps
>
> template <class OutputIterator>
> OutputIterator _offset_polygon(const typename Gps_traits_2::Polygon_2& pgn,
>                                CGAL::Orientation orient,
>                                const Rational& r,
>                                unsigned int cycle_id,
>                                OutputIterator oi) const;
>
> cause Gps_traits_2 is already a nested type in Exact_offset_base_2.

Agree, got confused with the visibility of this typedef.

Chris