CGAL users discussion list

[Ben Supnik <>]

Hi Y'all,

First, if this is a FAQ or already covered, I do apologize.  I am just 
getting back to CGAL after several years; X-Plane's open source scenery 
generation code base uses CGAL for Delauney triangulation to build our 
irregular mesh and we have a planar map that is an offshoot of the old 
pmwx class.  (We're looking at moving to the new arrangement_2.)

We need polygon-inset operations for GIS-type algorithms; there seem to 
be two candidates:

1. Build a straight skeleton and use the offset builder; our current 
code uses a home-rolled version of Fernando Cacciola's algorithm (and he 
was exceedingly helpful in understanding the problem when we were 
working on it :-).

2. Use an arrangement to build the buffer curves around the basic 
polygon and its holes.  The arrangement's ability to find intersections 
will give us something consistent that we can then use to find the 
derived shapes of the buffer zone.  (Essentially we deal with merging 
polygons by letting the arrangement figure out what happened.)  This 
approach is similar to how GEOS does its buffers.

Before I replace our existing code with one of these technquies, does 
anyone have any suggestions on which way to go?

- We have a lot of input data cases where the input polygon has a really 
large number of sides (1000+) but the offset distance is very, very 
small compared to the overall size of the polygon.  The inset contours 
will have very few "events".

In my old code, where I was only interested in a slightly inset contour 
and not the entire skeleton, I got a big performance win by halting the 
inset operation once I'd exceeded the "time" that my offset needed. 
Basically I could throw out and not evaluate the entire event list.

Is there a way to do this in the CGAL skeleton/offset classes?  If not, 
am I going to hit a performance problem?

Anyway, any advise from people who are doing polygon insetting/buffering 
would be much appreciated!

cheers
Ben

--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
Scenery mailing list: 

Developer mailing list: