Polygon Triangulator!!

For my 3D games, I've been playing around with ideas around semi-procedural geometry, by which I mean geometry which is generated from a small amount of authored data.  For example, I could draw out the shape of an island in a dozen or so 3D points, and the actual terrain geometry could be generated from that.

A big step along the way to that is splitting up a non-convex polygon into triangles.  The triangles mustn't overlap, nor must they cover any space which the polygon itself doesn't cover.  For example, this diagram.

Today, I managed to get a python program* running which took a list of 2D points defining a polygon, split it into sub-triangles and displayed them in a tkinter canvas**.

I am certain this has been solved by clever people in much better ways, but I still feel proud to have figured this one out (and I haven't managed to break it yet!).

The basic algorithm is:

• Create a temporary copy of the polygon points list
• start with the three points from the beginning of the list e.g. [0,1,2]
• can I make a valid triangle with these points?
• Is the winding correct? (this stops me generating triangles which would be outside the polygon)
• If so, are any other polygon points within this triangle? (this stops me generating triangles which overlap)
• If there aren't any points inside it, go ahead and make the triangle!
• If I made a triangle, remove the point which is no longer necessary from the list (essentially, making the polygon smaller by that one triangle)
• If I did not make a triangle, take the three points starting at the next one along (e.g. [1,2,3]) 
• Try to make the next triangle (in the smaller poly, or from the next set of points)!
• Keep going until there are only three points left
• Make the final triangle
• et voilà!

I think my next step will be to make the program produce a polygon graph (with edge and adjacency information) so I can do the edge-flipping to make it a valid DeLaunay triangulation (which will have much more nicely shaped triangles).

Or I might write a Unity version of this before I do the DeLaunay stuff.

Anyways - I feel like this is a big step forward! :D

* why python?  Well, because it was there - I was only playing after all.
** why tkinter?  I know it sucks so badly, but again, it was there and I knew how to use it quickly.