[OSM-dev] Polygon relationificator - CGAL?
bsupnik at xsquawkbox.net
Mon Sep 14 21:31:27 BST 2009
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