2.2 Fecho convexo de um conjunto de pontos

Vimos anteriormente que quando tratamos de posicionar objetos no plano que não devem ocupar o mesmo espaço (dois personagens, por exemplo) envolvemos esses objetos por uma figura geométrica que facilite a detecção de possíveis colisões. Isso pode ser feito com círculos, como mostramos na Aula 01, mas também pode ser feito com polígonos, que frequentemente aproximam melhor a área considerada para o tratamento de colisões do formato da imagem representada na tela.

Imagine, por exemplo, que a nossa personagem seja uma estrela.

Se utilizarmos um círculo para envolver essa estrela e representar o espaço que ela ocupa, teríamos algo como a Figura 16.

No entanto, se utilizarmos um polígono, a representação espacial da estrela pode ficar muito mais adequada à sua imagem, como na Figura 17.

A representação que utiliza o círculo tem o problema de considerar como sendo ocupado pela estrela um espaço que não é de fato ocupado por sua imagem. Já a representação pelo polígono da Figura 17 pode gerar um problema de alto custo computacional para a detecção de uma colisão com a estrela, principalmente pelo fato de sua representação não ser um polígono convexo.

A solução frequentemente utilizada em casos como esse é um meio termo entre as duas representações. Para isso é necessário definir o que chamamos de fecho convexo.