El salto de plantilla , a veces llamado desplazamiento de plantilla , es un algoritmo para localizar el elemento de la cuadrícula que encierra un punto determinado para cualquier malla estructurada. En palabras simples, dado un punto y una malla estructurada , este algoritmo ayudará a localizar el elemento de la cuadrícula que encierra el punto dado.
Este algoritmo se utiliza ampliamente en dinámica de fluidos computacional (CFD) en términos de corte de agujeros e interpolación cuando dos mallas se encuentran una dentro de la otra. Las otras variaciones del problema serían algo así: Dado un lugar, ¿en qué latitud y longitud se encuentra? El algoritmo de fuerza bruta encontraría la distancia del punto desde cada punto de la malla y vería cuál es el más pequeño. Otro enfoque sería utilizar un algoritmo de búsqueda binaria que arrojaría un resultado comparable en velocidad al algoritmo de salto de plantilla. Una combinación tanto de la búsqueda binaria como del algoritmo de salto de plantilla arrojará un resultado óptimo en el mínimo tiempo posible.
Considere un elemento de cuadrícula de una malla bidimensional como se muestra, para simplificar, y considere un punto O en el interior. Los vértices del elemento de cuadrícula se denotan por A, B, C y D y se representan los vectores AB, BC, CD, DA, OA, OB, OC y OD. El producto vectorial de OA y AB dará como resultado un vector perpendicular al plano que sale de la pantalla. Decimos que la magnitud del producto vectorial es positiva. Se observará que los productos vectoriales de OB y BC, OC y CD; y OD y DA son todos positivos.
Esto no sucede cuando el punto está fuera. Aquí vemos que no todos los productos cruzados son positivos. Este es el criterio de prueba principal del algoritmo.
El algoritmo necesita un elemento de cuadrícula de conjetura para comenzar. El elemento de cuadrícula se puede encontrar por la ubicación de un punto, por ejemplo A. Los otros puntos se pueden ubicar automáticamente obteniendo los puntos subsiguientes. Luego, los productos cruzados requeridos se encuentran en el orden
Cada uno de estos productos cruzados se comprueba uno por uno (en el orden que se muestra) en cuál se vuelve negativo primero. Si OA × AB se vuelve negativo primero, la siguiente aproximación debe estar un paso por delante a lo largo de DA. Si OB × BC es negativo primero, avanzar un paso a lo largo de AB para encontrar la siguiente aproximación y así sucesivamente.
El algoritmo convergerá en el elemento exacto de la cuadrícula donde todos los productos cruzados sean positivos.