Find medial axis of a polygon using C#

One simple solution would be as suggested in the comments:

1. Build the Delaunay triangulation of the polygon vertices.
2. Identify the Voronoi vertices inside the polygon (see http://en.wikipedia.org/wiki/Point_in_polygon)
3. Output the Voronoi edges connecting two interior Voronoi vertices.

If you have huge data the intersections might be quite costly.

Then you could do a similar approach like in the question, and this solution could work for you, as well. The way I would do it:

1. Build the Delaunay triangulation of the polygon vertices.
2. Insert the midpoint of every polygon edge that is not covered by a delaunay edge. Do this recursively until all polygon edges are covered by Delaunay edges.
3. Mark all Delaunay edges which correspond to a polygon edge.
4. Extract the medial axis using steps 3.-5. in this solution

PS. Note that both solutions give some approximation of the medial axis, computing it exactly is much more costly but as a teaser... you can get results like this for the black input sample points:

A similar construct is the Straight skeleton, which can be constructed by shrinking the polygon into itself and tracing the vertices as they approach the center. This may be a little easier to construct, though it's not quite the same curve as the medial axis.