Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
Have you tried link? – AranHase Oct 21 '12 at 21:41
@AranHase This is good for my other question. Here I get a raster as input. – zehelvion Oct 22 '12 at 20:41
possible duplicate of Algorithm for approximating sihlouette image as polygon – Byte56 Oct 24 '12 at 17:22
up vote 3 down vote accepted

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

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 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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.