¿Existe un algoritmo para determinar regiones coloreadas contiguas en una cuadrícula?

Question

Dada una cuadrícula básica (como un trozo de papel cuadriculado), donde cada celda ha sido rellenada aleatoriamente con uno de n colores, ¿existe un algoritmo probado y verdadero que pueda decirme qué regiones contiguas (grupos de celdas del mismo color que se unen a un lado) hay? Digamos que n es algo razonable, como 5.

Tengo algunas ideas, pero todas se sienten terriblemente ineficientes.

Answer 1

El mejor algoritmo posible es O (número de celdas), y no está relacionado con el número de colores.

Esto se puede lograr iterando a través de las celdas, y cada vez que visita una que no ha sido marcada como visitada, haga un recorrido de gráfico para encontrar todas las celdas contiguas en esa región y luego continúe iterando.

Editar:

Aquí hay un ejemplo de pseudocódigo simple de una búsqueda en profundidad, que es un recorrido de gráfico fácil de implementar:

function visit(cell) {
    if cell.marked return
    cell.marked = true
    foreach neighbor in cell.neighbors {
        if cell.color == neighbor.color {
            visit(neighbor)
        }
    }
}

Answer 2

Además de la respuesta recursiva recursiva, puede usar una pila si la recursividad es demasiado lenta:

function visit(cell) {
    stack = new stack
    stack.push cell

    while not stack.empty {
        cell = stack.pop
        if cell.marked continue
        cell.marked = true
        foreach neighbor in cell.neighbors {
            if cell.color == neighbor.color {
                stack.push neighbor
            }
        }
    }
}

Answer 3

Puedes intentar hacer un relleno de inundación en cada cuadrado. A medida que se propaga la inundación, registre los cuadrados de la cuadrícula en una matriz o algo, y coloréelos en un color no utilizado, digamos -1.

Answer 4

El artículo de Wikipedia sobre inundación puede serle útil aquí: http: //en.wikipedia. org / wiki / Flood_fill

Answer 5

Union-find funcionaría aquí también. De hecho, puede formular su pregunta como un problema sobre un gráfico: los vértices son las celdas de la cuadrícula y dos vértices son adyacentes si sus celdas de la cuadrícula tienen el mismo color. Estás intentando encontrar los componentes conectados.

La forma en que usaría una estructura de datos de búsqueda de unión es la siguiente: primero cree una estructura de datos de búsqueda de unión con tantos elementos como celdas. Luego, recorra las celdas y union dos celdas adyacentes si tienen el mismo color. Al final, ejecute find en cada celda y almacene la respuesta. Las celdas con el mismo find están en la misma región de color contigua.

Answer 6

Si desea un poco más de control de grano fino, puede pensar en usar el A * algoritmo y use la heurística para incluir mosaicos de colores similares.

Answer 7

Recorre las regiones en una línea de exploración, yendo de izquierda a derecha de arriba a abajo. Para cada celda, hace una lista de celdas compartidas como el mismo objeto de memoria entre las celdas. Para cada celda, agrega la celda actual a la lista (ya sea compartida o creada). Luego, si la celda a la derecha o debajo es del mismo color, comparte esa lista con esa celda. Si esa celda ya tiene una lista, combine las listas y reemplace la referencia al objeto de lista en cada celda listada en las listas con la nueva lista fusionada.

Luego ubicado en cada celda hay una referencia a una lista que contiene cada celda contigua con esa celda. Esto combina acertadamente el trabajo del relleno de inundación entre cada celda. En lugar de repetirlo para cada celda. Como tiene las listas que reemplazan los datos con los datos combinados, solo está iterando a través de una lista. Será O (n * c) donde n es el número de celdas yc es una medida de cuán contigua es la gráfica. Una cuadrícula completamente desunida será n tiempo. Un gráfico de 1 color completamente contiguo con be n ^ 2/2.