[OSM-dev] Polygon relationificator - CGAL?

Ben Supnik bsupnik at xsquawkbox.net
Mon Sep 14 21:31:27 BST 2009

Hi Guys,

Iván Sánchez Ortega wrote:

> P.S.: Remind me to take a course in computational geometry. I'm feeling like I 
> need it.

I figure this is as good of a time as any to plug CGAL...it's a hard 
core open source comp-geom lib:


in my work with OSM (exporting all roads + water and building flight sim 
scenery out of it) I use CGAL as my underlying geometry engine.

Three things to be said for CGAL:

1. The algorithms are correct.  I've written enough CG algs wrong to 
appreciate this. :-)

2. The algorithms are computationally fast.  They do things like sweep 
lines and other computationally optimal things so you can process a lot 
of data fast.  Processing the entire world in tiles often takes < 24 
hours using their algs.

3. The algorithms use arbitrary-precision numeric types, so they are 
correct.  What this means is that you can basically throw _any_ crap 
into the alg as numeric input data and still get something out.

This last point is sort of a mixed blessing..for a user like me who 
exports, converts, and is done, knowing I won't get degenerate output is 
a life-saver.  But for an app like OSM where the output is going back 
into fixed-precision, you'd need to process the data to bring it back 
down to our levels of precision.

Anyway, CGAL has two packages, arrangement_2 and boolean ops on polygons 
that can be used to do polygon processing:


Arrangements do the "graph" ops that Iván was describing, e.g. merging 
consolidated edges and discovering planar arrangements.  The boolean ops 
package sits on top of that to do merges, e.g. I have a set of polygons 
marked "grass" but maybe they overlap...the boolean ops package gives 
you the union.


Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: x-plane-scenery at yahoogroups.com
Developer mailing list: x-plane-dev at yahoogroups.com

More information about the dev mailing list