El algoritmo de distancia de Gilbert–Johnson–Keerthi es un método para determinar la distancia mínima entre dos conjuntos convexos , publicado por primera vez por Elmer G. Gilbert , Daniel W. Johnson y S. Sathiya Keerthi en 1988. A diferencia de muchos otros algoritmos de distancia, no requiere que los datos de geometría se almacenen en ningún formato específico, sino que se basa únicamente en una función de soporte para generar iterativamente símplex más cercanos a la respuesta correcta utilizando el obstáculo del espacio de configuración (CSO) de dos formas convexas, más comúnmente conocido como la diferencia de Minkowski .
Los algoritmos "GJK mejorados" utilizan información de los bordes para acelerar el algoritmo al seguir los bordes cuando se busca el siguiente símplex. Esto mejora sustancialmente el rendimiento para politopos con una gran cantidad de vértices.
GJK utiliza el subalgoritmo de distancia de Johnson, que calcula en el caso general el punto de un tetraedro más cercano al origen, pero se sabe que sufre problemas de robustez numérica. En 2017, Montanari, Petrinic y Barbieri propusieron un nuevo subalgoritmo basado en volúmenes con signo que evita la multiplicación de cantidades potencialmente pequeñas y logró una aceleración del 15% al 30%.
Los algoritmos GJK se utilizan a menudo de forma incremental en sistemas de simulación y videojuegos. En este modo, el símplex final de una solución anterior se utiliza como estimación inicial en la siguiente iteración o "marco". Si las posiciones en el nuevo marco son cercanas a las del marco anterior, el algoritmo convergerá en una o dos iteraciones. Esto produce sistemas de detección de colisiones que funcionan en un tiempo casi constante.
La estabilidad, la velocidad y el pequeño tamaño de almacenamiento del algoritmo lo hacen popular para la detección de colisiones en tiempo real , especialmente en motores de física para videojuegos .
GJK se basa en dos funciones:
Los símplices manejados por NearestSimplex pueden ser cualquier subespacio símplice de R n . Por ejemplo, en 3D, pueden ser un punto, un segmento de línea, un triángulo o un tetraedro ; cada uno definido por 1, 2, 3 o 4 puntos respectivamente.
función GJK_intersection(forma p, forma q, vector eje_inicial): vector A = Soporte(p, eje_inicial) − Soporte(q, −eje_inicial) símplex s = {A} vector D = −A bucle : A = Soporte(p, D) − Soporte(q, −D) si punto(A, D) < 0: rechazar s = s ∪ {A} s, D, contiene_origen := NearestSimplex(s) Si contiene_origen: aceptar