Geometry Boost List: [ggl] Proposal for Delauney triangulation algorithm

Subject: [ggl] Proposal for Delauney triangulation algorithm
From: John Swensen (jpswensen)
Date: 2011-10-14 23:50:13

I found a Delauney triangulation library at http://code.google.com/p/poly2tri/ . It has a permissive license that I think would allow it to be incorporated in Boost.Geometry (I will email the authors to verify).  Since I don't know geometry in great detail, I don't know how good the algorithm is, but it has worked flawlessly for the relatively simple polygons with holes that I have in my game. I also like this implementation because it is both well documented and not very, very complex like some of the other Delauney implementations I have seen.

The reason I need it is to make the OpenGL drawing of the polygons on the iPhone easier (the GLU tesselation functions are not available for iPhone).  I have also seen during searching that it is an oft asked question on StackOverflow and other forums.

The existing code is fortunately very compatible with the existing data structures of Boost.Geometry. They have a Point class that could easily be represented with the point_xy geometry.  The current code defines a polygon with a std::vector for the outer ring and any number of std::vector's for the holes which can be replaced with the polygon geometry associating the exterior and interior rings with the outer ring and the holes.  The output of the current code is a std::vector of Triangle instances.  This could easily be replaced with an output of a multi_polygon of the individual triangle polygons.

Would you be open to the inclusion of this into Boost.Geometry?  What is your opinion on including an algorithm that is know to not work for all cases?  I'm sure this won't cover all possibilities well. 

John Swensen