Polygon triangulation

Question

Hey,

I am working on nesting of sheet metal parts and am implementing Minkowski Sums to find No Fit Polygons for nesting. The problem is I can give only convex sets as input to the code which calculates Minkowski sums for me. Hence I need to break a concave polygon, with holes into Convex sets. I am open to triangulation also, but I am looking for a working code on VC++ (6.0). I am slightly running short on time as my whole code is ready and just waiting for input in the form of convex sets.

I would really appreciate if somebody with prior experience can help me in this. I have gone through other posts but did not find anything matching to this. I am a student of mechanical engineering and really dun have much idea about computer languages. All I can handle is compiling a code on VC++ and incorporate it with my existing code.

Looking forward to responses!! Thanks Warm regards Saurabh India

Answer 1

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Did you tried to Google?

Answer 2

@ Dmitriy: I had gone through this website earlier and the problem is:

"// ** THIS IS A CODE SNIPPET WHICH WILL EFFICIEINTLY TRIANGULATE ANY // ** POLYGON/CONTOUR (without holes) AS A STATIC CLASS" It works on polygons without holes. In my case I need it to work for concave polygons with holes. I tried google also and am working on implementing GPC(General Polygon Clipper). Though I am not sure if I will be able to implement it successfully to triangulate polygons with holes.

Regards Saurabh India

Answer 3

This paper (Decomposition of a polygon with holes into convex polygons) is dedicated to solving the problem that you face.

Note that it only explains the algorithm, it does not give you any implementation. It seems to be well explained using pseudo code, which shouldn't be too hard to translate to any language.

You are dealing with a very specific problem, in those cases, you often have to implement the algorithm yourself.

Answer 4

You could try to search ready code with Google Code Search.

Answer 5

If you have access to OpenGL, you can take advantage of GLU's tessellation. You don't have to actually use OpenGL to use the tessellator, but I leave that as an exercise to the reader.