In my game, I need a way to produce convex polygons from pngs of objects.

For example, a maple leaf would result like this: enter image description here

Essentially right now, the way my algorithm works is by putting all pixels that have an alpha of 255 in a list. I then create a convex hull from this list, and finally optimize the hull with a graph algorithm. The part I'm trying to optimize is the first part. I'd like a way to have the outline / border pixels of the shape rather than all pixels of the shape.

What sort of algorithm could do this?



2 Answers 2


Scan each line and only record a point on entry to your 255 areas and then another point on exit from the 255 areas. You can then pick a point and start finding closest neighbors and walk all the way around to build your contour lines.

That will end up being pretty dense, but then you could collapse multiple points that are on the same slope into a beginning and end point for your final result.


The marching squares algorithm should work really well for this. Another really good algorithm is the "Canny edge-detection algorithm".

For your purposes, marching squares should be good enough (and way faster than canny), since you don't want to actually detect lines "inside" the image but just the outlines of the shape (using the alpha).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .