Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

I'm using the Chipmunk physics engine to make the levels for a 2D C game. I'd like to be able to fit a polygon to an arbitrary shape to serve as the collision mask. Given a black and white collision mask for an arbitrary level object like this:

A black blob

Are there any well-known algorithms for getting this: Now with a fitted polygon

I could then use the red polygon to create a physics object to go with the image.

share|improve this question
up vote 9 down vote accepted

This is known as generating a concave hull, and is in the general case pretty complicated (much more so than the convex hull).

One commonly-recommended method is using alpha shapes.

There are more good resources on the problem here, here, and here.

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.