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 fro...