¿Hay un algoritmo para determinar las regiones de color contiguas en una cuadrícula?

Question

Dada una cuadrícula básica (como una hoja de papel cuadriculado), donde cada celda se ha rellenado aleatoriamente con uno de n colores, ¿hay algún algoritmo probado y verdadero que pueda decirme qué regiones contiguas (grupos de celdas de el mismo color que se unen en el lado) hay? Digamos que n es algo razonable, como 5.

Tengo algunas ideas, pero todas se sienten horriblemente 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 recorriendo las celdas, y cada vez que visita una que no se ha marcado como visitado, haga un recorrido de gráfico para encontrar todas las celdas contiguas en esa región, y luego continúe la iteración.

Editar:

Aquí está un ejemplo simple pseudo código de una primera búsqueda en profundidad, que es una forma fácil de poner en práctica el gráfico de recorrido:

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

Answer 2

Puede tratar de llenar un relleno en cada casilla. A medida que se propaga la inundación, grabe los cuadrados de la cuadrícula en una matriz o algo así, y coloreéelos en un color no utilizado, digamos -1.

Answer 3

El artículo de Wikipedia sobre relleno de inundación podría ser útil para usted aquí : http://en.wikipedia.org/wiki/Flood_fill

Answer 4

Además de respuesta recursiva de recursiva, puede utilizar una pila si la repetición es demasiado lento:

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 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 grilla, y dos vértices son adyacentes si sus celdas tienen el mismo color. Estás tratando de encontrar los componentes conectados.

La forma en que usaría una estructura de datos union-find es la siguiente: primero cree una estructura de datos union-find con tantos elementos como células tenga. Luego itere a través de 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 algoritmo A* y usar la heurística para incluir mosaicos de colores similares.