CGAL users discussion list

[Ben Supnik <>]

Hi James,

Hrm - well, it won't be fast but you I suppose you can do a "join" on a 
huge list of triangles (turn each triangle into a polygon_2 and join 
them into a general polygon set).  Then use CGAL to re-triangulate the 
resulting output polygons with holes.

If you were already trying this and got orientation errors you'll need 
to hand-check your triangles - call orientation() on each triangle - if 
it is clockwise, reverse its vertex order; if it is collinear you'll 
need to throw it out - CGAL doesn't like degenerate geometry.

(This is in line with your current approach I think.)

It looks like others have discussed going from polygon-with-holes back 
to triangulation.

http://stackoverflow.com/questions/406301/polygon-triangulation-with-holes#406647

Note that you'll need an exact constructions kernel, and you'll hit a 
speed penalty for that.

cheers
Ben

On 12/23/11 7:20 PM, James Swift wrote:
> No meta data is really required after the merge, just a new list of triangles.
> I suppose, optimally an opengl like triangle-list would be better than
> each triangle described individually where vertices of shared edges
> would be needlessly repeated.
>
>
> On 24 December 2011 01:00, Ben 
> Supnik<>
>   wrote:
> > Sorry, one more q: is it important to track either whether a result triangle
> > is from an "overlap" and/or which source triangle (or triangle list) the
> > triangle comes from)?
> >
> > The more of this "meta data" you care about, the more complex the
> > implementation I suspect...
> >
> >
> >
> >
> > On 12/23/11 6:49 PM, James wrote:
> > > Hi,
> > >
> > > I am trying to merge a list of 2d triangles that may or may not overlap
> > > into
> > > a new list of triangles that no longer overlap.
> > >
> > > E.g. two overlapping triangles T1 and T2 merge to create 8 new smaller
> > > triangles
> > >
> > > http://i.imgur.com/WvXaO.png
> > >
> > > (ignore the colours)
> > >
> > > I tried out the example Boolean_set_operations_2/sequence.cpp and then
> > > modified it as it seemed to be what I want to do but my simple changes
> > > resulted in an orientation error. I'm somewhat out of my depth here.
> > >
> > > Can someone experienced with CGAL give me a small example of how this
> > > might
> > > be achieved and what problems I might encounter. I suspect it should be a
> > > simple problem.
> > >
> > > thanks,
> > >
> > > James
> > >
> > >
> > > --
> > > View this message in context:
> > > http://cgal-discuss.949826.n4.nabble.com/Merging-2d-triangles-tp4230142p4230142.html
> > > Sent from the cgal-discuss mailing list archive at Nabble.com.
> >
> > --
> > Scenery Home Page: http://scenery.x-plane.com/
> > Scenery blog: http://www.x-plane.com/blog/
> > Plugin SDK: http://www.xsquawkbox.net/xpsdk/
> > X-Plane Wiki: http://wiki.x-plane.com/
> > Scenery mailing list: 
> >
> > Developer mailing list: 
> >
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://lists-sop.inria.fr/wws/info/cgal-discuss

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

Developer mailing list: