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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.