algoritmo de inundación por salto

El algoritmo de inundación por salto ( JFA ) es un algoritmo de inundación utilizado en la construcción de diagramas de Voronoi y transformadas de distancia . El JFA fue presentado por Rong Guodong en un simposio de la ACM en 2006. ^{[ 1 ]}

El algoritmo JFA posee atributos deseables en la computación GPU , especialmente por su eficiente rendimiento. Sin embargo, se trata solo de un algoritmo aproximado y no siempre calcula el resultado correcto para cada píxel, aunque en la práctica los errores son escasos y su magnitud suele ser pequeña. ^{[ 1 ]}

La formulación original de JFA es sencilla de implementar.

Toma un${\displaystyle N\times N}$cuadrícula de píxeles ^{[ 2 ]} (como una imagen o textura). Todos los píxeles comenzarán con un color "indefinido" a menos que sean píxeles "semilla" de color único. A medida que avanza el JFA, cada píxel indefinido se rellenará con un color que corresponda al de un píxel semilla.

Para cada tamaño de paso${\displaystyle k\in \{{\tfrac {N}{2}},{\tfrac {N}{4}},\dots ,1\}}$, ejecutar una iteración del JFA:

Iterar sobre cada píxel${\displaystyle p}$en${\displaystyle (x,y)}$.

Por cada vecino${\displaystyle q}$en${\displaystyle (x+i,y+j)}$dónde${\displaystyle i,j\in \{-k,0,k\}}$:

si${\displaystyle p}$no está definido y${\displaystyle q}$está coloreado, cambia${\displaystyle p}$color a${\displaystyle q}$'s

si${\displaystyle p}$es coloreado y${\displaystyle q}$está coloreado, si${\displaystyle \mathrm {dist} (p,s)>\mathrm {dist} (p,s')}$dónde${\displaystyle s}$y${\displaystyle s'}$son los píxeles semilla para${\displaystyle p}$y${\displaystyle q}$, respectivamente, luego cambiar${\displaystyle p}$color a${\displaystyle q}$'s.

Tenga en cuenta que los píxeles pueden cambiar de color más de una vez en cada paso, y que el JFA no especifica un método para resolver los casos en los que las distancias son iguales; por lo tanto, se utiliza el color del último píxel comprobado.

El JFA finaliza después de evaluar el último píxel en el último tamaño de paso. Independientemente del contenido de los datos iniciales, el bucle más interno ejecuta un total de${\displaystyle 9\log _{2}(N)}$veces sobre cada píxel, para una complejidad computacional general de${\displaystyle O(N^{2}\log _{2}(N))}$.

El algoritmo de inundación de saltos y sus variantes pueden utilizarse para calcular mapas de Voronoi ^{[ 1 ] [ 3 ]} y teselaciones de Voronoi centroidales (CVT), ^{[ 4 ]} generar campos de distancia , ^{[ 5 ]} renderizado de nubes de puntos , ^{[ 6 ]} coincidencia de características , ^{[ 7 ]} el cálculo de diagramas de potencia , ^{[ 8 ]} y renderizado de sombras suaves . ^{[ 9 ]} El desarrollador de juegos de gran estrategia Paradox Interactive utiliza el JFA para renderizar fronteras entre países y provincias. ^{[ 10 ]}

El JFA ha inspirado el desarrollo de numerosos algoritmos similares. Algunos tienen propiedades de error bien definidas que los hacen útiles para la computación científica. ^{[ 11 ]}

En el ámbito de la visión por computadora , el JFA ha inspirado nuevos algoritmos de propagación de creencias para acelerar la solución de diversos problemas. ^{[ 12 ] [ 13 ]}

Al momento de esta edición , este artículo utiliza contenido de "¿Es separable el algoritmo de inundación de salto?" , escrito por alan-wolfe y trichoplax en Stack Exchange, cuya licencia permite su reutilización bajo la Licencia Creative Commons Atribución-CompartirIgual 3.0 No Adaptada , pero no bajo la GFDL . Deben respetarse todos los términos pertinentes.