Algorithm for decomposition of complex polygons

I am trying to create polygons for a Doom 2 level from the information contained in a WAD file. I have walls, all that is left are "apartments", floor and ceiling. The Doom map is divided into "sectors", each of which is evaluated as a flat complex polygon.

It would be easy to decompose a simple, convex polygon into triangles, since there are many algorithms for this. But many of the sectional polices are concave, and some even have "holes" in which other sectors are located. Here's an example: a particularly complex poly is shown in orange: http://screencast.com/t/BNKuzRVy8

Can anyone recommend an algorithm, or better yet, C # code that will decompose this type of complex poly into triangles?

I know the WAD file includes NODE, SEG information, SUBSECTOR, etc., which indirectly describes the breakdown in this way. But this is especially difficult. I don't need a b-tree structure. I would like you not to take all this information apart and combine it, since I have a complex polystructure of sector information.