1 Use Marching Squares algorithm to convert obstacle tiles into outlines. Note that map edges is an outline too and need to be included as well.
2 Reduce number of points in outlines using Douglas-Peucker algorithm (purple lines on the bottom picture)
4 Add additional points in empty areas and along the map edges (to get more even navmesh)
5 Check along obstacle outlines and flip polygons produced by Delaunay to match outlines. - Often Delaunay could place triangles (grey) mismatching your outlines (red), then you need to detect and flip them. Adjoining them back into a polygon, split it along outline(s) and triangulate it manually enter image description here
6 Clip obstacles innards - remove polygons that are within obstacles (pink on the picture above)
7 Fill in connectivity data between remaining triangles and vertices as you need - that‘s your navmesh.