Fastest triangulation algorithm with holes?

Question

I'm working on path finding for an RTS game, where I am building a navigation mesh from the game's grid.

I have written an algorithm similar to Marching Squares which creates and simplifies the borders between the walkable and unwalkable regions of the map. Now I have a "mesh" consisting of only edges. I need to triangulate this mesh so that the final triangulation contains the initial edges, and then I can remove the unwalkable regions to create holes in the navigation mesh. For example, I need to do this...

The triangles represent the walkable regions of the map. The holes represent unwalkable regions such as mountains or buildings. The mesh can be considered 2D, since the height is irrelevant. This is obviously a very simplified case. The navigation mesh in the game will consist of thousands of vertices and many holes, but I may break it down into smaller chunks for dynamic updating.

I have looked at constrained Delaunay Triangulation algorithms, which first create a Delaunay Triangulation of the points, and then remove any triangles that intersect the constrained edges, then re-triangulates the removed triangles.

This seems a little redundant for my purposes. My mesh does not need to be Delaunay, and it consists completely of constrained edges, so I'd like to skip doing the extra triangulations if possible. Is there a better algorithm for this? I have looked and looked, and have only been able to find constrained Delaunay algorithms. Or maybe I'm wrong, and a constrained Delaunay algorithm would be best?

I've done navigation mesh path finding from scratch before, but never had to generate the navigation mesh myself. Triangulation algorithms are new to me. Any insight?

Answer 1

Fernandez et al 2008 seems to be close to the state-of-the-art when it comes to the problem of decomposing complex domains. If you're looking for (possibly simpler) alternatives, the authors list other possible algorithms in the second paragraph of p370.