Is there an algorithm to determine contiguous colored regions in a grid?

Question

Given a basic grid (like a piece of graph paper), where each cell has been randomly filled in with one of n colors, is there a tried and true algorithm out there that can tell me what contiguous regions (groups of cells of the same color that are joined at the side) there are? Let's say n is something reasonable, like 5.

I have some ideas, but they all feel horribly inefficient.

Answer 1

You could try doing a flood fill on each square. As the flood spreads, record the grid squares in an array or something, and colour them in an unused colour, say -1.

Answer 2

The best possible algorithm is O(number of cells), and is not related to the number of colors.

This can be achieved by iterating through the cells, and every time you visit one that has not been marked as visited, do a graph traversal to find all the contiguous cells in that region, and then continue iterating.

Edit:

Here's a simple pseudo code example of a depth first search, which is an easy to implement graph traversal:

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

Answer 3

The Wikipedia article on flood fill might be useful to you here: http://en.wikipedia.org/wiki/Flood_fill

Answer 4

In addition to recursive's recursive answer, you can use a stack if recursion is too slow:

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 would work here as well. Indeed, you can formulate your question as a problem about a graph: the vertices are the grid cells, and two vertices are adjacent if their grid cells have the same color. You're trying to find the connected components.

The way you would use a union-find data structure is as follows: first create a union-find data structure with as many elements as you have cells. Then iterate through the cells, and union two adjacent cells if they have the same color. In the end, run find on each cell and store the response. Cells with the same find are in the same contiguous colored region.

Answer 6

If you want a little more fine grain control, you might think about using the A* algorithm and use the heuristic to include similarly colored tiles.