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:

Field

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:

Field

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!

Is the bottom picture the desired output or do you want small little numbers inside each box? It is a bit unclear as to what you are asking — DUUUDE123, Jun 07 '15 at 14:59
I also dont understand what you are asking. Do you want a visual representation of the teamid on the image? — Matt, Jun 07 '15 at 15:59
I'm still a bit confused... Do you want a method to group together the "neighborhoods"? — DUUUDE123, Jun 07 '15 at 22:18
check the answer below: http://stackoverflow.com/questions/30694603/detect-coherent-neighbors-neighborhood-in-2d-array/30698982#30698982 — InsOp, Jun 07 '15 at 22:47

score 0 · Answer 1 · answered Jun 07 '15 at 16:43

You can use the logic from dots and block games. A block belongs to a player if he has surrounded it with the walls. So, you need for each cell also 4 walls except for the outer cells. To test if a cell is closed you can use 4 class variables:

var Block = function() {
  this.isclosed=0;
  this.left=0;
  this.top=0;
  this.right=0;
  this.bottom=0;
  return this;
}

Block.prototype = {
  isClosed : function () {
    if (this.isclosed==true) {
      return false;
    } else if (this.left && this.top && this.right && this.bottom) {
      this.isclosed=true;
      return true;
    } else {
      return this.left && this.top && this.right && this.bottom;
    }
  }
}

You can try my implementations of dots and blocks game @ https://dotsgame.codeplex.com/.

im not exactly sure, whether this solves my problem. since im having neighbors with more than 9 fields — InsOp, Jun 07 '15 at 20:14
Can you add a variable player to the class? My idea is to use this if-else statement with all 4 walls. — Micromega, Jun 07 '15 at 22:15

score -1 · Accepted Answer · edited May 23 '17 at 11:51

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>

Isn't this similar to adjacency list:http://www.geeksforgeeks.org/graph-and-its-representations/. — Micromega, Jun 07 '15 at 22:38

Detect coherent neighbors / neighborhood in 2d array

2 Answers2