CGAL users discussion list

[Marko Kukovec <>]

Hello Andreas!

I was in such a hurry that I missed that an original question to your
answer was "Is it possible to compute the inner offset of a polygon
(with Minkowski method, not with a Straight Skeleton method) ?" I
apologize for my mistake.

I didn't consider Minkowski Sum method for my needs because after quick
fly trough chapter I figured that algorithm can only be used for offset
calculations. I need both, offsets and insets.

Regards,
Marko


-----Original Message-----
From: Andreas Fabri 
<>
Reply-To: 

To: 

Subject: Re: [cgal-discuss] 2D Straight Skeleton and Polygon Offsetting
Date: Sat, 03 May 2008 10:02:25 +0200

Marko Kukovec wrote:
> Hello!
> 
> I'm honored to have a word with a straight skeleton algorithm
> implementer. I read your document
> www.cgal.org/UserWorkshop/2004/straight_skeleton.pdf and Peter Felkels
> www.dma.fi.upm.es/mabellanas/tfcs/skeleton/html/documentacion/Straight%
> 20Skeletons%20Implementation.pdf . I'm fairly new to the computational
> geometry and I admit I'll have to do some more documents reruns before
> I'll understand the algorithm in detail.
> 
> I read the CircularArcSubdivision algorithm document you sent me and is
> really straight forward. Maybe the only drawback is that resulting
> segments vertices are not sorted to have proper orientation. The
> segments will have to be sorted from start to the end of an arc. I'll
> implement this approach in polygon offset/inset calculation and report
> about performance penalties (huge number of resulting vertices fed to
> the offset algorithm).
> 
> While browsing the CGAL discussion group archive, I stumbled upon the
> mail
> https://lists-sop.inria.fr/wws/arc/cgal-discuss/2008-02/msg00198.html
> where Andreas Fabri discuses that extending the straight skeleton
> algorithm to circular arcs is possible. As an author of this part of
> CGAL library do you agree?

Hi Marko,

I wrote that the offseting algorithm based on Minkowski sums should
be extensible to circular arcs. I discussed that with the authors of
the Minkowski sum package: It is feasible, but not straightforward.

andreas


> 
> Regards,
> Marko Kukovec
>  
> 
> -----Original Message-----
> From: Fernando Cacciola 
> <>
> Reply-To: 
> 
> To: 
> 
> Subject: Re: [cgal-discuss] 2D Straight Skeleton and Polygon Offsetting
> Date: Fri, 2 May 2008 15:51:56 -0300
> 
> Hello Marko,
> 
>> Greetings!
>>
>> I managed to compose some polygons based on the example "14.3.2
>> Operating on Polygons with Circular Arcs"
>> http://www.cgal.org/Manual/3.3/examples/Boolean_set_operations_2/circle_segment.cpp
>>
>> the example result looks like
>> http://img138.imageshack.us/img138/5940/goodresultsrf7.jpg
>>
>> and I played a little and I got another one like
>> http://img229.imageshack.us/img229/1839/pcbhy4.jpg
>>
>>
>> Now I would like to do offsetting on this polygons. First I went trough
>> chapter "Chapter 19 2D Straight Skeleton and Polygon Offsetting" and
>> compiled and executed the example
>> http://www.cgal.org/Manual/3.3/examples/Straight_skeleton_2/Straight_skeleton_2.cpp
>>
>> First thing I noticed that different kernel configuration is used than
>> in the Boolean operations example. Then I noticed I can "feed"
>> Straight_skeleton_builder_2 (enter_contour method) only with the points
>> array that have some orientation. The same goes for the
>> compute_outer_frame_margin helper method.
>>
> Indeed.
> 
>> My polygons are constructed with line and arc segments. Lines don't
>> present any problem, but is there any way to feed the algorithm with arc
>> segments?
> 
> Not directly. You need to "polygonize" your circular arcs I'm afraid.
> 
>> If not, is there any smart way to dissect arcs into many small
>> line segments using CGAL? I know that this way I would get huge amount
>> of vertexes. Is there any smarter way?
>>
> I think the best way to polygonize a circular arc for this purpose is to do 
> an 
> error-based subdivision approach in order to avoid getting more segments 
> than 
> needed for a certain desired resolution.
> 
> Here's a reference to a simple algorithm doing just that:
> 
> http://www.worldserver.com/turk/computergraphics/CircularArcSubdivision.pdf
> 
> HTH
> 
> Fernando Cacciola
> GeometryFactory
> 
> 
>