javascript: Fast way to find connected components in array (looking for speed up / alternative way)

Question

I have an matrix (1d array, x&y-axe) like this:

var matrix=[
'00000000000000000000000000000000000000000000000000000000000000000000111111111',
'11111100000000000000000000001000000000000000000000000000000000000000000001111',
'00000000000000000000000000000000001000000000000000000000000000000000000000011',
'11111000000000000000000000000000000000000001111110000000000000000000000000001',
'11111000000000000111000000000000000000111111000000000000000000000000000000000',
'00000000000111111111111100000000000000111111000000000000000000000000000000000',
'00000000000000000110000000000000000000111111000000000000000000010000000000000',
'00000000000000000000000000000001111111000000000000000000000000000000000000000',
'00000100000000000000000000000000000000000000000000000000000000000010000000000',
'00000010010000000000000000000000000000111111110000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000100000000000000',
'00000000000000000000000000000000000000000000000000000100000000000000000000000'
]

and I'D like to find all connected groups of '1'-characters and extract all of their positions to get something like this as result:

[{"0": [[68,0],[69,0],[70,0],[71,0],[72,0],[73,0],[73,1],[74,1],[75,1],[75,2],[76,2],[76,3],[76,1],[76,0],[75,0],[74,0]],"1": [[0,1],[1,1],[2,1],[3,1],[4,1],[5,1]],"2": [[28,1]],"3": [[34,2]],"4": [[0,3],[0,4],[1,4],[2,4],[3,4],[4,4],[4,3],[3,3],[2,3],[1,3]],"5": [[43,3],[43,4],[43,5],[43,6],[42,6],[42,5],[42,4],[41,4],[41,5],[41,6],[40,6],[40,5],[40,4],[39,4],[39,5],[39,6],[38,6],[38,5],[38,4],[44,3],[45,3],[46,3],[47,3],[48,3]],"6": [[17,4],[17,5],[17,6],[18,6],[18,5],[19,5],[20,5],[21,5],[22,5],[23,5],[19,4],[18,4],[16,5],[15,5],[14,5],[13,5],[12,5],[11,5]],"7": [[63,6]],"8": [[31,7],[32,7],[33,7],[34,7],[35,7],[36,7],[37,7]],"9": [[5,8]],"10": [[66,8]],"11": [[6,9]],"12": [[9,9]],"13": [[38,9],[39,9],[40,9],[41,9],[42,9],[43,9],[44,9],[45,9]],"14": [[62,11]],"15": [[53,12]]}]

I have already developed some kind of a flood fill algorithm that is working quiet well with the matrix above.

But there must be a way more efficient & fast way to find connected components in a bigger matrix (e.g 10 or even 100 times bigger). --> My idea was maybe this result could be also achieved with some kind of regex expression combined with javascript code, but I'm absolutely not sure how to code this, so I hope somebody has an good idea to fast up my little algorithm below so that I can avoid Overflow Errors :

var matrix=[
'00000000000000000000000000000000000000000000000000000000000000000000111111111',
'11111100000000000000000000001000000000000000000000000000000000000000000001111',
'00000000000000000000000000000000001000000000000000000000000000000000000000011',
'11111000000000000000000000000000000000000001111110000000000000000000000000001',
'11111000000000000111000000000000000000111111000000000000000000000000000000000',
'00000000000111111111111100000000000000111111000000000000000000000000000000000',
'00000000000000000110000000000000000000111111000000000000000000010000000000000',
'00000000000000000000000000000001111111000000000000000000000000000000000000000',
'00000100000000000000000000000000000000000000000000000000000000000010000000000',
'00000010010000000000000000000000000000111111110000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000100000000000000',
'00000000000000000000000000000000000000000000000000000100000000000000000000000'
]

Array.prototype.extract_components_positions = function(offset) {
 var array = this.map(item => item.split('')).map(str => Array.from(str, Number)),
  default_value = 0,
  result_object = {}

 function test_connection(array, i, j) {
  if (array[i] && array[i][j] === -1) {
   if (!result_object[default_value]) result_object[default_value] = [];
   result_object[default_value].push([j, i]);
   array[i][j] = 1;
   for (var k = offset; k > 0; k--) {
    test_connection(array, i + k, j); // left - right
    test_connection(array, i, j + k); // top - bottom
    test_connection(array, i - k, j); // right - left
    test_connection(array, i, j - k); // bottom - top
   }
   return true
  }
 }
 array.forEach(function(a) {
  a.forEach(function(b, i, bb) {
   bb[i] = -b
  })
 });
 array.forEach(function(a, i, aa) {
  a.forEach(function(b, j, bb) {
   test_connection(aa, i, j) && default_value++
  })
 })
 return [result_object];
}



var result = matrix.extract_components_positions(1);
console.log((result))

.as-console-wrapper { max-height: 100% !important; top: 0; }

Edit 1.0 BTW It would be also not that bad if the algorithm is just able to connect bigger components (e.g minimum group of 5 connected characters)

You might want to take a look at [math.js](http://mathjs.org/docs/datatypes/matrices.html). There's also an entire [article on matrices by Mozilla](https://developer.mozilla.org/en-US/docs/Web/API/WebGL_API/Matrix_math_for_the_web) — ctwheels, Dec 04 '17 at 20:38
Can not even find one matching information to my question. Just some less important information about other kinds of matrixes. Not really helpful @ctxwheels — , Dec 04 '17 at 20:47
Well since no one else was able to help I figured I'd try. If that's not helpful I do apologize, but both links I provided include matrix math in JavaScript. I figured *maybe* one of them might be of use to you. — ctwheels, Dec 04 '17 at 20:50
Just (x/y) positions in an object, should be easy to see @revo — , Dec 05 '17 at 16:58
Your implementation of the recursive version you linked to seems pretty good to me. Further down that link is a mention about scanline fill (https://en.wikipedia.org/wiki/Flood_fill#Scanline_fill) being more efficient. Perhaps you could look up some algorithms / pseudocode for that. — גלעד ברקן, Dec 05 '17 at 17:19

score 0 · Answer 1 · answered Dec 04 '17 at 21:44

Code

This is the method I figured out. I'm sure it can be optimized, but I feel it's at least a big step in the right direction.

I've also taken information from the following answers and applied it.

var matrix=[
'00000000000000000000000000000000000000000000000000000000000000000000111111111',
'11111100000000000000000000001000000000000000000000000000000000000000000001111',
'00000000000000000000000000000000001000000000000000000000000000000000000000011',
'11111000000000000000000000000000000000000001111110000000000000000000000000001',
'11111000000000000111000000000000000000111111000000000000000000000000000000000',
'00000000000111111111111100000000000000111111000000000000000000000000000000000',
'00000000000000000110000000000000000000111111000000000000000000010000000000000',
'00000000000000000000000000000001111111000000000000000000000000000000000000000',
'00000100000000000000000000000000000000000000000000000000000000000010000000000',
'00000010010000000000000000000000000000111111110000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000100000000000000',
'00000000000000000000000000000000000000000000000000000100000000000000000000000'
]

var results = [];

function charPos(str, char) {
  return str
         .split("")
         .map(function (c, i) { if (c == char) return i; })
         .filter(function (v) { return v >= 0; });
}

matrix.forEach(function(s, i) {
  var p = charPos(s, '1');
  results[i] = [];
  matrix.forEach(function(s2, i2) {
    var p2;
    if((p2 = charPos(s2, '1').filter((n) => p.includes(n))).length) {
      p2.forEach(function(v) {
        if(JSON.stringify(results).indexOf(JSON.stringify([v, i2])) === -1)
          results[i].push([v, i2]);
      });
    }
  });
});

console.log(results.filter(v => v.length > 0));

@revo I know it doesn't, but from the specifications of the question itself, it does match. It gets an array of positions where the first match is returned based on the index of the string in the matrix, setting priority on the lowest array items such that if a match is found in array item 0 and array item 2, the match is reported in array item 0. — ctwheels, Dec 04 '17 at 21:59
@revo If I'm misunderstanding this question, then I can delete my answer, I just feel like this might help the OP or someone else design a better method for the OP to resolve their problem. I'm sure with some minor tweaks that the OP's result can be achieved with my above methods. — ctwheels, Dec 04 '17 at 22:05
By _connected_ the querist means adjacent in a 2-dimensional grid as it appears in the source matrix of columns and lines. So, for example the `1` at position `[28,1]` is not connected to the cluster `[0,1],[1,1],[2,1],[3,1],[4,1],[5,1]`. — Armali, Aug 23 '19 at 08:02

javascript: Fast way to find connected components in array (looking for speed up / alternative way)

1 Answers1

Code

Linked