[OSM-dev] Polygon relationificator - CGAL?

[Ben Supnik]

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:

http://www.cgal.org/

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:

http://www.cgal.org/Manual/last/doc_html/cgal_manual/Arrangement_on_surface_2/Chapter_main.html
http://www.cgal.org/Manual/last/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html

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.

cheers
Ben

-- 
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