CGAL users discussion list

[Andreas Fabri <>]

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