Detección de áreas de difusión isotrópica versus anisotrópica en una operación de relleno por inundación (o similar)

7

¡Hola compañeros programadores!

Tengo un gráfico 2D que se describe mejor como una cuadrícula cartesiana con celdas transitables y no transitables. Me gustaría poder detectar subconjuntos de este gráfico donde la difusión se comporta de forma anisotrópica, es decir, está restringida por pasajes de tipo corredor.

Inicialmente recurrí a imágenes de tensor de difusión en neurociencia, pero estoy teniendo muchos problemas para digerir el material. Me pregunto si algo de esto ya se ha convertido en un algoritmo utilizable, o si hay otros enfoques que podrían ser fructíferos.

Específicamente, me gustaría poder determinar lo siguiente:

  1. Áreas en las que la difusión es anisotrópica : altamente restringida a dos direcciones (piense en el agua que fluye a través de un corte 2D de una pajilla).
  2. Áreas en las que la difusión es isotrópica : en gran medida sin restricciones (es decir, el agua se difunde a través de un gran espacio aunque de forma irregular .

Dado que el gráfico solo contiene áreas muy estrechas o abiertas, sería suficiente determinar cualquiera de las dos opciones anisotrópica o y deducir la otra con un simple contraste.

TL; DR : ¿Cómo puedo encontrar la "media" dirección de una difusión en una operación de relleno de inundación o similar?

EDITAR: Este es un ejemplo de mi gráfico como imagen:

    
pregunta blz 17.04.2013 - 16:31

1 respuesta

1

No estoy al tanto de ninguna solución conocida, pero al principio pensé que podría funcionar una simple inundación que se llene según la conectividad.

Suposiciones:

  • La 'apertura' de cada nodo será una función de su conectividad a otros nodos. Es decir, en un gráfico bidireccional que simula una cuadrícula cuadrada, un nodo completamente abierto tendrá 8 bordes.

No probado, pero el siguiente pseudocódigo puede ser capaz de encontrar áreas abiertas.

public class graph
{
    private static List<node> GetArea(node n)
    {
        if (isConnectedEnough(n))
        {
            yield n;
            yield! GetArea(n.neighbours)
        }
    }

    private static bool isConnectedEnough(node n)
    {
        return n.neighbours.Count >= 3;
            /* better: a connectivity threshold function */
    }
}

Imaginé llamar a GetArea secuencialmente en la lista de todos los nodos en el gráfico ordenados por conectividad hasta que se encontrara un área de tamaño suficiente. Dependiendo de las características de su (s) gráfico (s) que podrían no ser suficientes, pero asumí que el gráfico estaba estructurado de tal manera que había numerosas áreas separadas por pasillos (es decir, habitaciones conectadas por pasillos).

El umbral de conectividad es la clave en esta situación. Se requeriría algo de experimentación aquí basada en las características de su (s) gráfico (s) porque:

  • Si la conectividad promedio de los nodos vecinos es igual a la conectividad de n , entonces es probable que el área tenga un tamaño consistente (es decir, no se acerque a un punto de choque, tampoco se expanda en tamaño).
  • Si la conectividad promedio de los nodos vecinos es mayor que la conectividad de n , entonces podemos expandirnos a un área. Dependiendo de cómo usted defina un área, eso puede estar bien, (potencialmente describe un "pellizco" en un área). Se debe considerar una consideración cuidadosa aquí porque esto también describe esquinas y "corredores" de ancho 2 nodos / 1 borde (el umbral mínimo de 3 permitiría esquinas en el área).

Eso es todo lo que tengo por ahora, pero volveré a registrarme aquí. Este es un problema interesante.

    
respondido por el Steven Evers 17.04.2013 - 18:07

Lea otras preguntas en las etiquetas