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

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?


share|improve this question
up vote 5 down vote accepted

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.

share|improve this answer

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

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.