CGAL users discussion list

[Ben Supnik <>]

Hi Y'all,

Looking at the boolean operations code, it seems to me that if I am 
joining a large number of polygons and they have a large number of sides 
and the number of intersecting areas is small, the merge is going to be 
slower than necessary because the polygons are merged pair-wise in a 
merge sort.

This means O(log N) sweeps over the entire set of edges...where N is the 
number of input polygons.  If the number of input polygons is large and 
the number of edges is large, my sweep time goes up.

I'm wondering if it is possible to implement a single-pass sweep 
algorithm...basically:

- Sweep every single line segment together once into one big arrangement.

- Traverse the arrangement once, determining the "contained" state of 
each face using a breadth-first search.

Basically each time I cross an edge in the arrangement, I would need to 
update a "depth" count to track whether I am inside one or more 
polygons...any face whose depth > 0 is in.

Is there any reason why this would not work, or why the performance 
would be worse than the existing merge?

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: 

Developer mailing list: