Re: [pygame] Polygon triangulation

["Dave LeCompte (really)" <dave@xxxxxxxxxxxx>]

Ethan Glasser-Camp asked about polygon triangulation routines:

> Do any of you guys use
> triangulation in your code? If so, how? Roll your own? Or is it not as
> useful as I think it ought to be?

I took a quick pass at this a while ago, and I was able to crank out a
library without too much difficulty - basically all you do is you walk
around the perimeter, keeping track of the last three verts you've visited
- if those three points bend "outward", they can form a triangle and be
removed from your working shape.

I think I was dealing with some pretty forgiving data, though - it looks
like the general case (including complex polygons) is a lot harder:

http://mathworld.wolfram.com/Triangulation.html


-Dave LeCompte