Detect coherent neighbors / neighborhood in 2d array

Question

Im having an arbitrary 2d array and each field has an id and a teamid (here illustrated as colors 1).

I want for every neighborhood an array with the ids in it.

A neighborhood consists of fields with neighbors with the same teamid horizontally and vertically (not diagonally)

e.g.: This is what i have:

array[0][0] = {id:1,teamId:1} 
array[1][0] = {id:2,teamId:1} 
array[2][0] = {id:3,teamId:0}
array[3][0] = {id:4,teamId:2}
array[4][0] = {id:5,teamId:2}
array[5][0] = {id:6,teamId:0}

array[0][1] = {id:7,teamId:1} 
array[1][1] = {id:8,teamId:1} 
array[2][1] = {id:9,teamId:1}
array[3][1] = {id:10,teamId:2}
array[4][1] = {id:11,teamId:2}
array[5][1] = {id:12,teamId:0}

//and so on..

This is what i want:

neighborhood[1] = [1,2,7,8,9,13,14]
neighborhood[2] = [4,5,10,11]
neighborhood[3] = [16,22,23,24,29,30]
neighborhood[4] = [25,31,32,37,38]
neighborhood[5] = [35,41]

I am not searching for the images, but for the array

neighborhood

thanks in advance!

Answer 1

The method for solving this issue is refered as Connected Component Labelling

A similar question was asked once before from which i have my solution:

// matrix dimensions
var row_count = 20;
var col_count = 20;
var numOfTeams = 2;

// the input matrix
var m = [];
// the labels, 0 means unlabeled
var label = [];
var source = document.getElementById("source");
for (var i = 0; i < row_count; i++) {
  var row = source.insertRow(0);
  m[i] = [];
  label[i] = [];
  for (var j = 0; j < col_count; j++) {
    //m[i][j] = Math.round(Math.random());
    m[i][j] = getRandomInt(0, numOfTeams + 1);
    label[i][j] = 0;
    var cell1 = row.insertCell(0);
    cell1.innerHTML = m[i][j];
  }
}

// direction vectors
var dx = [1, 0, -1, 0];
var dy = [0, 1, 0, -1];

function dfs(x, y, current_label, team) {
  if (x < 0 || x == row_count) return; // out of bounds
  if (y < 0 || y == col_count) return; // out of bounds
  if (label[x][y] || team != m[x][y]) return; // already labeled or not marked with 1 in m


  // mark the current cell
  label[x][y] = current_label;

  // recursively mark the neighbors
  for (var direction = 0; direction < 4; ++direction) {
    dfs(x + dx[direction], y + dy[direction], current_label, team);
  }
}


function find_components() {
  var component = 0;

  for (var i = 0; i < row_count; ++i) {
    for (var j = 0; j < col_count; ++j) {

      if (!label[i][j] && m[i][j]) dfs(i, j, ++component, m[i][j]);
    }
  }
}

find_components();

var result = document.getElementById("result");


for (var i in label) {
  var string = ""
  var row = result.insertRow(0);
  for (var j in label[i]) {
    string += label[i][j] + " "
    var cell1 = row.insertCell(0);
    cell1.innerHTML = label[i][j];
  }
}

function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min)) + min;
}

table tr td {
  min-width: 14px
}

<div style="float:left">
  <table id="source"></table>
</div>
<div style="float:right">
  <table id="result"></table>
</div>