Anyone knows an algorithm for finding "shapes" in 2d arrays?

Question

Let's take this map, where '#' illustrates a taken square and '.' illustrates a free square:

1 . # # # . .
2 . # . . # .
3 # . . . . #
4 . # # # . .
5 . . . . . .
6 . . . . . .
- 1 2 3 4 5 6

Now, if I put a '#' in the square 4,5 the area would be "filled" like this:

1 . # # # . .
2 . # # # # .
3 # # # # # #
4 . # # # # .
5 . . . . . .
6 . . . . . .
- 1 2 3 4 5 6

So, what is the best way to find "a limited square", where I can start flood fill or other filling algorithm that fills the limited area?

Answer 1

If you can convert your problem to a graph, what you are looking for is to identify connected components. And if a connected component does not contain an edge that is the boundary edge, then you have found the region that needs to be filled.

If I define the graph like this:

G = (V, E)
V = {r1, r2, r3, r4, r5, r6, c1, c2, c3, c4, c5, c6}
E = {(u, v) | u, v are elements of V && the cell(u, v) is not taken}

Now run DFS to find all disconnected trees. Algorithm:

for each u in V:
    color[u] = white

for each u in V:
    if color[u] == white:
        contains_boundary_edge = False
        DFS-visit( u, contains_boundary_edge )

        if not contains_boundary_edge:
            Flood-fill( u )

DFS-visit( u, contains_boundary_edge ):
    color[u] = gray
    for each v in adjacent( u ):
        if color[v] == white:
            if edge(u, v) is a boundary edge: // Can be easily identified if one of u, v is start or end row/col.
                contains_boundary_edge = True

            DFS-visit( v, contains_boundary_edge )

    color[u] = black

Answer 2

I think this question can be reduced to a convex hull problem if we consider each # as point x,y then convex hull be give us the x,y of all the # which are absent

http://en.wikipedia.org/wiki/Convex_hull

I will try to code it in leisure ..

Answer 3

You could attack this by processing each '.' node.

Definition: A '.' node is enclosed if there does not exist a path from the node to the boundary of the map.

If you agree with the above definition, the algorithm would be to maintain a graph of '.' nodes, where adjacent nodes are connected.

Every time a node is changed to '#', remove it from this graph, and check each remaining '.' node to see if a path exists from it to one of the nodes on the map border.

Depending on the size of your map, you made need to attempt various optimizations to limit the number of path searches performed each turn.