An optimal (for things like opengl rendering) triangulation is very time consuming to compute because you need to add additional points to ensure a uniform triangulation that works well for things like lighting (normals) and such.

For navigation this may or may not be bad.

My method:

• fill contour bounding box with random points.

clip points not inside contour (your triangulation -> point in triangle test)

• perform voronoi tesselation of point set

- clip/subdivide resultant triangles touching bounding edges (this is where i fail, this is really difficult to do)
- move each point to its cell centroid to ensure more uniform spacing.

• perform delauney triangulation of the point set. Clip edge triangles again.

• profit