Sunday, July 16, 2017

collision detection - Are there well-known algorithms for fitting a polygon to an arbitrary shape?


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.



Answer



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.



No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...