Convert Bitmap to Polygon - (Reverse-Rasterizing)

Question

Given a bitmap image with some blots of solid color on it, what algorithm would you employ to construct polygons in the same shape as the blots?

This can be done in multiple steps: a high-resolution polygon could be later cut down by a best fit algorithm. Bonus points if you can tell me how to cut the resulting polygons into convex components so that they can be rendered in OpenGL without problems.

Answer 1

Reverse rasterizing is referred to as vectorizing. The algorithms are generally quite complex, here's a googlet of a few of them. Check out sparse pixel tracking and sparse pixel vectorization for some good examples.

For good algorithms for polygon partitioning, check out Joespeh O'Rourkes 'Computational Geometry in C', ISBN 0-521-44034-3, or search for concave polygon partitioning algorithms, such as this

Answer 2

This is quite common in GIS - e.g. extracting features automatically from aerial photography. The OpenSource tool of choice would be:

http://www.gdal.org/gdal_polygonize.html

http://www.gdal.org/gdal__alg_8h.html#3f522a9035d3512b5d414fb4752671b1