CGAL users discussion list

[Marko Kukovec <>]

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?

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