Hello world and welcome to my blog.
Recently I have (inefficiently) implemented an efficient greedy algorithm, which removes those points from a polygon which span up the smallest triangle with their 2 neighbors until the removed triangle would be too large or the vertex count you specified is reached. If you want, you can tell it to only produce convex polygons, as some physic engines need them. This is achieved by not ignoring the sign of the calculated triangle area.
I have added a png reader with libpng to get the base polygon as follows: Use alpha thresholding to differentiate between fore- and background. Then use an edge detector to get the shape and then interpret every pixel on the edge as a polygon vertex. This is way too many vertices, so then the above greedy algorithm comes in handy to reduce the vertex count.
The given code can generate image files (pbm format) showing all vertices or python (py) files that define a variable named “polygon” to contain a list of pairs representing the (x,y) coordinates of each vertex. The former is primarily there for debugging and calibration purpose, the latter is useful if you want to actually use the polygon for something. You can easily alter the code to print the polygon in any other useful format.
Configuration, compilation and execution: Configure the program by opening polymaker.cpp and searching for comments containing the word TWEAK. Compile the program by typing make (the Makefile is very simple, make sure you have libpng dev headers installed). Execute the program with the path to the png file as only argument and forward the standard output to a file of the desired type ( e.g. if you want a pbm with vertices of pic.png do ./polymaker pic.png > polypic.pbm )
Remark: This code is far from being perfect. Known issues:
You currently can only make the polygons in clockwise order. This can be easily fixed (look for the according TODOs in polymaker.cpp) Recompiling the polymaker on every configuration change may be unpleasant The program has quadratic runtime although the algorithm could easily have amortized linear runtime in the length of the contour. This is due to a cache for triangle areas missing. If you have pngs large enough to be not processed in an eyeblink no more, this is the place to optimize. The algorithm is a greedy algorithm and delivers quite good, but definitely not optimal results. UPDATE: For some shapes with very sharp edges the tool creates wrong polygons or doesn’t terminate at all due to the rapidly and poorly written shape recognition algorithm
I release this stuff into the Public Domain. Have fun with it!
Download link: dysfunctional I hope I’ll soon have the time to push this on github or somewhere.
UPDATE: Now it IS on github: https://github.com/ConnyOnny/polymaker If you like it, you will probably make some changes. Please fork me and send me a pull request. If some people use this tool, it could become more useful over time.
Here you see a small space ship, a convex polygon with 8 vertices and a non-convex polygon with 16 vertices. The lines between the vertices are drawn with GIMP.