Existem algoritmos conhecidos para ajustar um polígono a uma forma arbitrária?

10

Estou usando o mecanismo de física Chipmunk para fazer os níveis de um jogo 2D em C. Eu gostaria de poder ajustar um polígono a uma forma arbitrária para servir como máscara de colisão. Dada uma máscara de colisão em preto e branco para um objeto de nível arbitrário como este:

Uma bolha preta

Existem algoritmos conhecidos para obter isso: Agora com um polígono ajustado

Eu poderia então usar o polígono vermelho para criar um objeto de física para acompanhar a imagem.

davidscolgan
fonte

Respostas:

9

Isso é conhecido como gerar um casco côncavo e, no caso geral, é bastante complicado (muito mais do que o casco convexo).

Um método comumente recomendado é o uso de formas alfa .

Há mais bons recursos sobre o problema aqui , aqui e aqui .

BlueRaja - Danny Pflughoeft
fonte