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?

wouldn't this be better on [programmers](http://programmers.stackexcahnge.com)? — zmo, Jun 17 '13 at 13:56
I think, the algorithm depends on the data structure used to represent your map. Can you please be more explicit on your implementation (since you've tagged "graph") — ibi0tux, Jun 17 '13 at 13:59
I'm thinking of undirected graph as a data structure, where each square is a vertex connected to others with edges. — Kaltsoon, Jun 17 '13 at 14:02
Seems like you don't want just to fill the region, you want to maximize the area of a filled region — Boyko Perfanov, Jun 17 '13 at 14:02
Another question : are the areas you're trying to find always convex or not. If they are convex there are some good convex-hull detection algorithms, you should be able to use ; if not ... let me think about it. — ibi0tux, Jun 17 '13 at 14:06
Or, is it that you want to fill the region(s) which don't leak out to the boundary? — Matthew Gilliard, Jun 17 '13 at 14:06
Specify the problem more precisely and correct the mistake in the example (or explain the example if there is no mistake in it). — Bartosz Marcinkowski, Jun 17 '13 at 14:10
@Kaltsoon : i know this problem and i worked on an algorithm a few years ago. If you have a few hours/day i can retrieve my notes and post it here. — ibi0tux, Jun 17 '13 at 14:12
Just to answer to my own question, I think square is limited, if I can't get to the border of the map from there. In other words "border vertices" are out of reach from there. I think simple BFS should to the trick. Thanks everyone! — Kaltsoon, Jun 17 '13 at 14:15
I assume your definition of "limited square" is a closed loop, which in graph terminology is a [cycle](http://en.wikipedia.org/wiki/Cycle_(graph_theory)). Just apply any standard algorithm to [detect cycles](http://stackoverflow.com/q/526331/21727) in an undirected graph. — mbeckish, Jun 17 '13 at 14:16
So '#' vertices would be walls or such, something that can't be crossed. — Kaltsoon, Jun 17 '13 at 14:16
@mbeckish : Cycle detection won't do the trick. In first map every '.' vertex is in a loop and there are no "limited squares". — Kaltsoon, Jun 17 '13 at 14:18
@Kaltsoon - From your problem description, I thought you were just looking for closed loops of '#' nodes, not '.' nodes. — mbeckish, Jun 17 '13 at 14:19
It looks like you're looking for an [articulation point](http://en.wikipedia.org/wiki/Biconnected_component). — svick, Jun 17 '13 at 14:22
@mbeckish : Yes, you would detect that there is maybe a limited area, but maybe it's already filled and there's no way of knowing where to start the fill. — Kaltsoon, Jun 17 '13 at 14:23
Have You looked into edge detection algorithms? http://en.wikipedia.org/wiki/Edge_detection — Denis de Bernardy, Jun 17 '13 at 14:24
@Denis I don't think that's useful, this is not a photograph, or something like that. — svick, Jun 17 '13 at 14:25
@svick: depends on how you view it. Technically, it's a representation of a black and white photography. :-) — Denis de Bernardy, Jun 17 '13 at 14:34

Vikas · Accepted Answer · 2013-06-17T19:15:10.370

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

score 3 · Answer 2 · answered Jun 17 '13 at 14:21

3

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 ..

answered Jun 17 '13 at 14:21

sethi

1,869
2
17
27

1

This algorithm needs a modification since in this case, nodes have to be adjacent to delimit the area. – ibi0tux Jun 17 '13 at 14:23
Huh? How will convex hull specifically find the 4,5 square? And wouldn't it also incorrectly find 1,2? – svick Jun 17 '13 at 14:24
The set isn't necessarily convex, so the convex hull won't really help a lot. – G. Bach Jun 17 '13 at 15:16

score 2 · Answer 3 · answered Jun 17 '13 at 14:26

2

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.

answered Jun 17 '13 at 14:26

mbeckish

10,485
5
30
55

This is something that I was thinking. It's just that I'm making a game and searching every free node 60 times a second seems a bit heavy. – Kaltsoon Jun 17 '13 at 14:28
Something like 300-350. I think it's not too much. – Kaltsoon Jun 17 '13 at 14:34
I think what you are looking for is [Flood Fill](http://en.wikipedia.org/wiki/Flood_fill). See [here](http://stackoverflow.com/a/1348995/21727). – mbeckish Jun 17 '13 at 14:37
The searching would be easier if you have a tree that identifies at least one path from the boundary to each free point. This tree is of course a subgraph of the total connectivity graph. When you claim a point, you cut that point from the graph. In general, this may detach one or more trees. If those can be reconnected to other points of the tree, do so (often a local operation on the neighbouring points). If not, those points can all be filled. – MSalters Jun 17 '13 at 15:15
@MSalters That's exactly what I was thinking when I first saw the question. You would need some way to prevent a subtree from connecting to one of its own branches, though, in order to do this correctly. – AJMansfield Jun 17 '13 at 15:50
@AJMansfield: That's actually easy, using "distance to boundary" as a measure. – MSalters Jun 17 '13 at 16:24

score 1 · Answer 4 · answered Jun 17 '13 at 14:31

If you model this map as a graph, and each square is connected to its four neighbours, you can use a bridge finding algorithm to find the square you need.

Note this model gives you several subgraphs to work with sometimes, so it might produce a number of false positives around the border, since adding a # there would certainly separate some nodes from the rest. To get around this, you could pad two levels of squares around the graph, so that no single # could separate a border node from the rest.

@svick's comment inspired this method.

score 1 · Answer 5 · answered Jun 17 '13 at 14:31

I would start from each neighbor of the picked square, and try to 'escape' to the boundary of the grid. Meanwhile, mark the path followed by 'X'. If you can escape: undo every 'X'. If you cannot escape, replace every 'X' by '#'. I made an example in Java, as shown below.

int W, H;   
char[][] input;
final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public void handle(int x, int y) {
    // try each neihgbor
    for (int[] d : directions) {
        if (canEscape(input, x, y)) {
            // if we can escape, the path found shouldn't be filled
            // so replace the Xes by '.';
            handleXes(input, false);                
        } else {
            // if we cannot escape, this is a closed shape, so
            // fill with '#'
            handleXes(input, true);
        }
        // note that this can be written more concisely as
        // handleXes(input, !canEscape(input, x, y));
    }
}    

public boolean canEscape(char[][] grid, int x, int y) {
    if (isEscape(grid, x, y))
        return true

    if (isValid(grid, x, y)) {
        // mark as visited
        grid[x][y] = 'X';
        // try each neighbor
        for (int[] d : directions) {
            if (canEscape(grid, x+d[0], y+d[1]))
                return true;
        }
    }

    return false;
}

public boolean isValid(char[][] grid, int x, int y) {
    return 0 <= x && x < W && 0 <= y && y < H && grid[x][y] == '.';
}

public boolean isEscape(char[][] grid, int x, int y) {
    return (0 == x || x == W-1 || 0 == y || y == H-1) && grid[x][y] == '.';
}   

public void handleXes(char[][] grid, boolean fill) {
    for (int x = 0; x < W; x++)
        for (int y = 0; y < H; y++)
            if (grid[x][y] == 'X')
                grid[x][y] = fill ? '#' : '.';
}

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

5 Answers5

Linked