Is there any heuristic to polygonize a closed 2D raster shape with n triangles?

Question

Let's say we have a 2D image black on white that shows a closed geometric shape.

Is there any (not naive brute force) algorithm that approximates that shape as closely as possible with n triangles? If you want a formal definition:

Approximate the shape with a polygon that when rendered into a new 2D image will match the largest number of pixels possible with the original image.

Answer 1

I think you'll need to do it in two or three steps:

For converting a raster image to polygons you can use pre-existing software like http://en.wikipedia.org/wiki/Potrace

Optimizing the result from that to get the best possible result with a specific number of polygons I believe is much harder. However efficiently optimizing an existing mesh down to a lower poly count isn't too difficult if you don't care about the result being optimal. For example http://research.microsoft.com/en-us/um/people/hoppe/proj/meshopt/ describes one algorithm to optimize a 3D mesh, based on a parameter saying how much to optimize it.

Once you have that optimized mesh you could apply a hill climbing algorithm to the vertex positions to try to further improve the fit.