test your algorithm knowledge

[jeffpr]

I have been trying to think about how to do this and I can't come up with anything. Imagine I have a data set of 220x220 rows and columns, below is a smaller version of what it looks like:

0000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000
0000000002222222200000000000222222222200000000
0000000021111111220000000000221111111112000000
0000000211000001222222222222100000000012200000
0000002110000001111111111111100000000012000000
0000002110000012222222222222000000000120000000
0000000211111220000000000000211111111120000000
0000000002222220000000000000022222222200000000
0000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000

where each of the 1's represent a sequence of numbers between 0 and 100, while everything outside this figure is 0. The sequence of numbers is large depending on where you are in the figure, but usually ranges from 10-15 numbers. My problem is the only numbers I want here are the 2's, which represent the boundary of the figure, I don't want the two little holes inside with the zeros. I have no problem getting the boundary of the figure, I just search through the elements until I come to a non-zero one and I check if any of its nearest neighbors are zero and if so then it represents a boundary piece.

The problem is that this method also gives me the inner boundary as well, where there are two holes cut out with zero elements. Can somebody think of a way just to get the 2's and nothing else. The numbers that aren't zero range between 1 and 100 and have no particular pattern to them.
Thanks if anybody can help.

Jeff

[RoboTact]

Just fill image with flow starting from border of image area (rectangle). Check for flow algorithms. And I'm sure one can end with constantly better solution for this particular case of 2D raster image.

[D_Drmmr]

Seems like a connected component problem to me. Consider each cell (row, column combination) as a vertex. Adjacent vertices are connected by an edge, if the cells represented by both vertices have a value equal to 0. The connected components of this graph will represent the 'islands' of 0's in your grid. So all cells in a connected component that contains one of the outer cells with value 0, form the set of values that you want to ignore. Now to find the border, you just have to identify all cells in that/those connected component(s) that are adjacent to a node that represents a cell with value 1 (in your example grid).

I've added a simple algorithm to find connected components in an undirected graph. It uses a std::deque in the function GetComponent(...), but you can replace this with whatever you need.

Don't forget to rate, if this helped you. :)

[jeffpr]

Thanks for the suggestion, I'll give your code a try. I'm not following the first post, can you explain it a bit better.

Jeff