Buen algoritmo para la determinación de no convexa 2D figuras de colisión

Question

¿Me podría proporcionar alguna información (o sugerir un artículo) en buen algoritmo de detección de colisiones para 2D no convexas cifras?

Gracias!

Answer 1

Prueba esto:
http://www.cs.man.ac.uk/~toby/alan/software/
Tenga en cuenta que no es libre para uso comercial.

Para más detalles se puede seguir a esta pregunta similar:

Un algoritmo sencillo para polígono intersección

---

Para determinar si dos polígonos simples se cruzan:

Si dos polígonos simples tienen una intersección no nula entonces uno de sucederá lo siguiente:

A) Uno de ellos tiene una esquina interior del interior de la otra.
B) Una de ellas tiene un borde de todo el interior del interior de la otra (las esquinas de que el borde no necesariamente pueden estar en el interior). Esto significa que la mitad de ese borde estarán dentro del interior.
C) Los polígonos son idénticos.
D) Hay dos aristas que se cruzan en un ángulo. El punto de intersección no ser una esquina cualquiera de los polígonos.

Lo que hay que hacer es comprobar si los polígonos son idénticos (tienen las mismas esquinas), o una de las esquinas o uno de la mitad de los bordes se encuentra dentro del interior del otro polígono o si hay dos aristas que se cruzan en otro lugar que en una esquina.

determinar si un punto se encuentra en el interior de un polígono.

Answer 2

Siempre encontró las páginas de Wikipedia a ser muy útil para mis necesidades:

Sutherland Hodgman

Liang Barsky

Weiler Atherton

Así como este documento en el algoritmo Weiler Atherton.