Desfiles en formación

En gráficos por computadora , el algoritmo de cuadrados marchantes genera contornos para un campo escalar bidimensional ( una matriz rectangular de valores numéricos individuales). Un método similar se puede utilizar para contornear mallas triangulares bidimensionales .

Los contornos pueden ser de dos tipos:

• Isolíneas : líneas que siguen un único nivel de datos o isovalor .
• Isobandas : áreas rellenas entre isolíneas.

Entre las aplicaciones típicas se incluyen las curvas de nivel en mapas topográficos o la generación de isobaras para mapas meteorológicos .

El algoritmo de cuadrados marchantes adopta un enfoque similar al del algoritmo de cubos marchantes en 3D :

• Procese cada celda de la cuadrícula de forma independiente.
• Calcula un índice de celda utilizando comparaciones del nivel o niveles de contorno con los valores de datos en las esquinas de la celda.
• Utilice una tabla de búsqueda predefinida , basada en el índice de la celda, para describir la geometría de salida de la celda.
• Aplique una interpolación lineal a lo largo de los límites de la celda para calcular la posición exacta del contorno.

Estos son los pasos del algoritmo:

Aplique un umbral al campo 2D para crear una imagen binaria que contenga:

• 1 donde el valor de los datos está por encima del isovalor
• 0 donde el valor de los datos está por debajo del isovalor

Nota: Los datos iguales al isovalor deben tratarse como superiores o inferiores de forma coherente.

Cada bloque de píxeles de 2x2 en la imagen binaria forma una celda de contorno, por lo que la imagen completa se representa mediante una cuadrícula de dichas celdas (mostradas en verde en la imagen inferior). Cabe destacar que esta cuadrícula de contorno es una celda más pequeña en cada dirección que el campo 2D original.

Para cada celda en la cuadrícula de contorno:

1. Para construir un índice binario, combine los 4 bits ubicados en las esquinas de la celda: recorra la celda en sentido horario agregando cada bit al índice, utilizando la operación OR bit a bit y el desplazamiento a la izquierda , desde el bit más significativo en la esquina superior izquierda hasta el menos significativo en la esquina inferior izquierda. El índice resultante de 4 bits puede tener 16 valores posibles en el rango de 0 a 15.
2. Utilice el índice de celda para acceder a una tabla de búsqueda predefinida con 16 entradas que enumeran los bordes necesarios para representar la celda (como se muestra en la parte inferior derecha de la imagen a continuación).
3. Aplique una interpolación lineal entre los valores de los datos de campo originales para encontrar la posición exacta de la línea de contorno a lo largo de los bordes de la celda.

El mismo algoritmo básico puede aplicarse a mallas triangulares , que consisten en triángulos conectados con datos asignados a los vértices. Por ejemplo, un conjunto disperso de puntos de datos podría conectarse mediante una triangulación de Delaunay para permitir la representación del contorno del campo de datos.

Una celda triangular siempre es plana , porque es un 2-símplex (es decir, está definida por n + 1 vértices en un espacio n -dimensional). Siempre existe un único interpolante lineal que atraviesa un triángulo, y no hay posibilidad de un punto de silla ambiguo.

El espacio de datos para el algoritmo Marching Squares es bidimensional, ya que los vértices a los que se les asigna un valor de datos están conectados a sus vecinos en una cuadrícula topológica bidimensional , pero las coordenadas espaciales asignadas a los vértices pueden ser bidimensionales, tridimensionales o de dimensiones superiores.

Por ejemplo, una malla triangular puede representar una superficie de datos bidimensional incrustada en un espacio tridimensional, donde las posiciones espaciales de los vértices y los puntos interpolados a lo largo de un contorno tendrán coordenadas tridimensionales. Cabe destacar que el caso de los cuadrados es ambiguo, ya que un cuadrilátero incrustado en un espacio tridimensional no es necesariamente plano, por lo que existe la posibilidad de elegir un esquema de interpolación geométrica para dibujar las superficies con bandas en 3D.

El algoritmo es fácilmente paralelizable , ya que todas las celdas se procesan de forma independiente. Es fácil escribir un algoritmo paralelo suponiendo que:

• Campo escalar de entrada compartido de solo lectura.
• Flujo de salida de geometría compartida de solo adición.

Una implementación simple del algoritmo Marching Squares, que procesa cada celda de forma independiente, realizará cada interpolación lineal dos veces (isolínea) o cuatro veces (isobanda). De manera similar, la salida contendrá dos copias de los vértices 2D para líneas disjuntas (isolínea) o cuatro copias para polígonos (isobandas). [Esto se basa en las siguientes suposiciones: la cuadrícula es grande, de modo que la mayoría de las celdas son internas; y se crea un conjunto completo y contiguo de isobandas.]

Es posible reducir la carga computacional almacenando en caché los resultados de la interpolación. Por ejemplo, una versión serial de un solo hilo solo necesitaría almacenar en caché los resultados interpolados para una fila de la cuadrícula de entrada.

También es posible reducir el tamaño de la salida utilizando primitivas geométricas indexadas, es decir , creando una matriz de vértices 2D y especificando líneas o polígonos con desplazamientos enteros cortos dentro de la matriz.

• Maple, C. (2003). «Diseño geométrico y planificación espacial mediante los algoritmos de cuadrados marchantes y cubos marchantes». Conferencia Internacional de Modelado Geométrico y Gráficos de 2003, 2003. Actas . págs. 90–95 . doi : 10.1109/GMAG.2003.1219671 . ISBN  978-0-7695-1985-2. S2CID 11320513 . 
• Banks, DC (2004). "Counting cases in substitope algorithms". IEEE Transactions on Visualization and Computer Graphics . 10 (4): 371– 384. CiteSeerX 10.1.1.582.7221 . doi : 10.1109/TVCG.2004.6 . PMID 18579966 . S2CID 2450480 .   
• Laguardia, JJ; Cueto, E.; Doblaré, M. (2005). "Un método de Galerkin de vecinos naturales con estructura de quadtree" . International Journal for Numerical Methods in Engineering . 63 (6): 789– 812. Bibcode : 2005IJNME..63..789L . doi : 10.1002/nme.1297 . S2CID 122746298 . 
• Schaefer, Scott; Warren, Joe (2005). "Cubos marchantes duales: contorneado primal de cuadrículas duales". Computer Graphics Forum . 24 (2): 195– 201. doi : 10.1111/j.1467-8659.2005.00843.x . S2CID 10015045 . 
• Mantz, Huber; Jacobs, Karin; Mecke, Klaus (2008). "Utilización de funcionales de Minkowski para el análisis de imágenes: un algoritmo de cuadrados marchantes". Journal of Statistical Mechanics: Theory and Experiment . 2008 (12) 12015. Bibcode : 2008JSMTE..12..015M . doi : 10.1088/1742-5468/2008/12/P12015 . S2CID 122873298 . 
• Cipolletti, Marina P.; Delrieux, Claudio A.; Perillo, Gerardo ME; Piccolo, M. Cintia (2012). "Segmentación y medición de bordes de superresolución en imágenes de teledetección". Computers & Geosciences . 40 : 87–97 . Bibcode : 2012CG.....40...87C . doi : 10.1016/j.cageo.2011.07.015 .

• Algoritmo de Matlab para el método de los cuadrados marchantes : un algoritmo de código abierto fácil de entender para el método de los cuadrados marchantes.
• implementación en Java
• Código de Marching Squares en Java. Dado un conjunto de datos 2D y umbrales, devuelve GeneralPath[] para facilitar la representación gráfica.
• Explicación de los triángulos serpenteantes y ejemplo de implementación en Python.
• Código de Marching Squares en C : una biblioteca de un solo archivo de cabecera para Marching Squares que puede exportar mallas triangulares para una fácil representación.