¿Existen algoritmos bien conocidos para ajustar un polígono a una forma arbitraria?

10

Estoy usando el motor de física Chipmunk para hacer los niveles para un juego 2D C. Me gustaría poder ajustar un polígono a una forma arbitraria para que sirva como máscara de colisión. Dada una máscara de colisión en blanco y negro para un objeto de nivel arbitrario como este:

Una mancha negra

¿Hay algún algoritmo conocido para obtener esto? Ahora con un polígono ajustado

Entonces podría usar el polígono rojo para crear un objeto de física que vaya con la imagen.

davidscolgan
fuente

Respuestas:

9

Esto se conoce como generar un casco cóncavo, y en el caso general es bastante complicado (mucho más que el casco convexo).

Un método comúnmente recomendado es usar formas alfa .

Hay más buenos recursos sobre el problema aquí , aquí y aquí .

BlueRaja - Danny Pflughoeft
fuente