Editar: Oh, mira, Simplifying Polygons
Usted mencionó la detección de colisiones. Podrías ir realmente simple y calcular un casco convexo de límite a su alrededor.
Si te preocuparon las áreas cóncavas, puedes calcular un casco cóncavo tomando el centroide de tu polígono y eligiendo un punto para comenzar. Desde el punto de partida, gire alrededor del centro de gravedad, encuentre cada vértice que desee conservar y asígnelo como el siguiente vértice en el casco delimitador. La complejidad del algoritmo vendría en cómo determinaste qué vértices conservar, pero estoy seguro de que ya pensaste en eso. Puedes lanzar todos tus vértices en cubos según su ubicación relativa al centroide. Cuando un cubo obtiene más de un número arbitrario de vértices completo, puede dividirlo. A continuación, tome la media de los vértices en ese cubo como el vértice para usar en su casco delimitador. O bien, olvide los cubos, y cuando se mueva alrededor del centroide, solo elija un punto si está a más de una distancia dada del último punto.
En realidad, probablemente puedas simplemente usar todos los vértices en tu polígono como "nube de puntos" y calcular el casco cóncavo alrededor de eso. Buscaré un enlace de algoritmo. El peor caso en esto sería un polígono completamente convexo.
Otra alternativa es comenzar con un rectángulo delimitador. Para cada vértice en el rectángulo, encuentre la distancia desde el punto al polígono. Para el vértice más alejado, divídelo en dos vértices más y muévelos en algunos. Repita hasta que se cumpla alguna proporción de vértices o área. Tendría que pensar en los detalles de este un poco más.
Si te preocupa que el polígono se vea realmente similar, incluso en el caso de un polígono autointersecante, entonces se necesitaría otro enfoque, pero no parece necesario ya que preguntaste sobre la detección de colisiones.
Este post tiene algunos detalles sobre la parte convexa del casco.
¡Guau! ¡Este algoritmo solo ROCKS! : D –