I am creating procedurally generated levels by stitching together "tilesets" created in a 3D modeling program such as 3DS max. Each tile consists of a 2x2x2 "section" of geometry, such as a wall, floor, corner, etc. These tiles are placed next to each other to form rooms and hallways.

After all the tiles are placed, I run a mesh simplification algorithm over the resulting geometry to reduce polygon counts for rendering and physics (and eventually NavMesh generation). The algorithm goes something like this:

1) Form groups of adjacent coplanar triangles that all have the same UV barycentric parameterizations (e.g. removing vertices wouldn't cause "warping").

2) Combine each group into a single polygon, possibly with holes.

3) Remove excess collinear vertices from the boundaries.

4) Triangulate the polygons using constrained delaunay triangulation.

The issue is that step 4) is prone to producing long skinny triangles, which is causing problems everywhere (e.g. breaking my thresholds used to detect collinearity). Can anyone provide some advice on how to approach this problem, or point me to some resources or algorithms that deal with avoiding this?