Plazas de marcha

Marching Squares (del inglés - "moving squares") es un algoritmo en gráficos por computadora que genera isolíneas en un campo escalar bidimensional .

Aplicación

El algoritmo se utiliza para visualizar isobaras en mapas meteorológicos y líneas de contorno en mapas geográficos. Es una simplificación del algoritmo de cubos en marcha para el caso plano.

Cómo funciona

Como entrada, el algoritmo recibe una cuadrícula regular, en cada nodo del cual se conoce el valor del campo. La cuadrícula de salida (indicada en azul en la figura) puede tener una resolución más baja (en este caso, se pierde precisión, pero se reduce el aliasing). A continuación, para cada nodo de la cuadrícula de salida, se verifica si el valor en él es mayor que en la isosuperficie. A todos los nodos que son más altos se les asigna "+", el resto - "-". A continuación, consideramos los cuadrados de la cuadrícula de salida, cuyos vértices se encuentran en los nodos marcados. En total, hay 16 casos diferentes, que, teniendo en cuenta las simetrías y rotaciones, se pueden reducir a cuatro:

Caso 1: todos los vértices tienen el mismo signo
Caso 2: un vértice tiene un signo diferente
Caso 3: los vértices con los mismos signos tienen una arista común
Caso 4: Los vértices con el mismo signo no comparten arista

En el cuarto caso, es imposible determinar sin ambigüedades la forma del segmento de isolínea, por lo que también se ve el valor en el centro del cuadrado (si los datos de entrada lo permiten). Si es imposible averiguar el valor en el centro del cuadrado, la decisión tomada puede afectar la conectividad de la isolínea.

Caso 1 : Todos los vértices están por encima (o por debajo) de la isosuperficie.
Caso 2 : A excepción de uno, todos los vértices están por encima (o por debajo) de la isosuperficie.
Caso 3 : dos vértices en el mismo borde están por encima (o por debajo) de la isosuperficie.
Caso 4 : dos vértices que no comparten un borde están por encima (o por debajo) de la isosuperficie.
Solución del Caso 4 con valor positivo en la celda.
Solución del Caso 4 con valor negativo en la celda.

La interpolación lineal se utiliza para mejorar la calidad de la isolínea resultante . En este caso, el segmento final de la isolínea en el borde del cuadrado divide el borde en relación con , donde son los valores en los extremos del borde del cuadrado, es el valor de la isolínea. De hecho, el final del segmento de la isolínea se "tira" hacia el final del borde, que está más cerca de la isolínea real. ${\frac{f_{1}-c}{c-f_{2}}}$ $f_{1},f_{2}$ $C$

Enlaces

Implementación en Java
Algoritmo Marching Square Matlab : un algoritmo de Marching Square de código abierto fácil de entender.
Isoline Isoband - Descripciones de algoritmos y código C / Fortran de fuente abierta para el sistema de visualización científica AVS (Mike French, 1992).