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:
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.
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.
"Programs must be written for people to read, and only incidentally for machines to execute."
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:eque in the function GetComponent(...), but you can replace this with whatever you need.
Don't forget to rate, if this helped you.
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky
* The Best Reasons to Target Windows 8
Learn some of the best reasons why you should seriously consider bringing your Android mobile development expertise to bear on the Windows 8 platform.
Reply With Quote
eque in the function GetComponent(...), but you can replace this with whatever you need.
