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

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 2

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 3

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 4

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

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.

Answer 7

You iterate through the regions in a scanline, going left-right top-bottom. For each cell you make a list of cells shared as the same memory object between the cells. For each cell, you add the current cell to the list (either shared with it or created). Then if the cell to the right or below is the same color, you share that list with that cell. If that cell already has a list, you combine the lists and replace the reference to the list object in each cell listed in the lists with the new merged list.

Then located in each cell is a reference to a list that contains every contiguous cell with that cell. This aptly combines the work of the floodfill between every cell. Rather than repeating it for each cell. Since you have the lists replacing the data with the merged data is just iterating through a list. It will be O(n*c) where n is the number of cells and c is a measure of how contiguous the graph is. A completely disjointed grid will be n time. A completely contiguous 1 color graph with be n^2/2.