Preparing to Triangulate

When I started this blog I had a list of interesting bits of code to share. I've gotten through most of them but have held back polygon triangulation until now. It's my personal symbol of jumping the shark; once I've presented polygon triangulation I've got nothing of importance left to say. It's time to get it out of the way, though, so over the long weekend I found the code and have been dusting it off as well as rereading the sources I used when I wrote it.

The polygon triangulation problem is as follows. We have a polygon outline, which may be concave and may include holes or interior lines. It may also consist of several disjoint polygons. It does not have intersecting lines. For each edge in the outline we know whether each side is inside or outside the polygon. In addition we may have individual vertices inside the polygon which we wish to be incorporated into the triangulation.

The goal is to produce a good triangulation of the polygonal interior without introducing any new vertices. Something like this:



Polygon triangulation turns out to be useful in a lot of different situations once you've got good robust code for doing it. For instance, in last week's post on river generation I used a disc because it's easy to generate uniform random points inside the disc. It would be nice to be able to have a more interesting coastline, though. With triangulation, I can take the coast outline, turn it into a triangle mesh, and then generate a uniform random point by picking a triangle at random (weighted by area) and then a random point within that triangle.

Here are the primary sources I used in writing my triangulator:

• David Mount
• Jonathan Shewchuk

Hopefully I'll have finished the code cleanup next week and can get started on the presentation of the triangulation algorithm.