On Sunday, 16 July 2017 at 10:37:39 UTC, kerdemdemir wrote:
My goal is to find connected components in a 2D array for
example finding connected '*'
chars below.
x x x x x x
x x x x x x
x x * * x x
x x * * x x
x x x * * x
* x x x x x
There are two connected '*' group in this example. First group
is composes of six '*' located closer to middle and the second
group composes only one '*' char located in the left bottom
corner.
Do to this I generally implement a recursive algorithm which
repeat calling the same function by checking all neighbors
around the current index. I generally end up with something
like :
void foo( int row, int col)
{
//Do something here like caching the index
if ( twoDimensionData[row - 1][col] == '*')
foo(row- 1, col);
else if ( twoDimensionData[row + 1][col] == '*')
foo(row+ 1, col);
else if ( twoDimensionData[row - 1 ][col - 1] == '*')
foo(row - 1, col - 1);
//..... I need 5 more of this bad boys I mean if checks
}
Is there any better way to achieve this with cool std functions
like enumerate or iota without needing to write eight if checks?
What you probably want is a convolution, used a lot in image
processing.
insted of using recursion you walk left to right in blocks of 3x3
and compute a "sum"
and then do the same vertically, then each cell contains the
number of neighbours that are *.
In this case you want the kernel
111
101
111
o o o x x x
o o o x x x
o o # * x x
x x * * x x
x x x * * x
* x x x x x
x o o o x x
x o o o x x
x o # # x x
x x * * x x
x x x * * x
* x x x x x
x x o o o x
x x o o o x
x x # # o x
x x * * x x
x x x * * x
* x x x x x
x x x o o o
x x x o o o
x x * # o o
x x * * x x
x x x * * x
* x x x x x
Have a look at the video on http://halide-lang.org describing the
different methods used.
