Identify isolated regions in a matrix (error in some special cases)

Question

Identify isolated regions in a matrix (error in some special cases)

Navigation

#1 by (1 votes)
#2 by (1 votes)
#3 by (1 votes)

1

I need to separate the different regions or "islands" formed by 1s within a matrix of any dimension. My example seemed to work correctly but there is some "special" case like the next one that does not work well. It should detect 2 elements or regions and yet it "gets confused" and finds 3 (when 2 and 3 should be the same). You can run the example to see more clearly what I explain.

var matrix = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 1, 1, 1, 0, 0, 0],
    [1, 1, 0, 1, 0, 0, 0, 1, 0, 0],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
    [0, 0, 1, 1, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 1, 1, 0],
    [0, 1, 0, 1, 0, 0, 0, 1, 1, 1],
    [0, 1, 0, 1, 1, 0, 0, 1, 1, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
];

var contFilas = matrix.length;
var contColumnas = matrix[0].length;
var canvas = document.querySelector("canvas");
var ctx = canvas.getContext("2d");
var sz = 20;
var regions = [];
var regionCollection = [];

canvas.width = sz * contColumnas;
canvas.height = sz * contColumnas;
ctx.fillStyle = "silver";
ctx.fillRect(0, 0, canvas.width, canvas.height);

for (var y = 0; y < contFilas; y++) {
    var regionline = [];
    regions.push(regionline);

    for (var x = 0; x < contColumnas; x++) {
        var pixelRegion = 0;
        regionline[x] = 0;
       


        if (matrix[y][x] === 1) {
            // check previous row
            if (y) {
                if (matrix[y - 1][x]) {
                    pixelRegion = regions[y - 1][x];
                } else if (x && matrix[y - 1][x - 1]) {
                    pixelRegion = regions[y - 1][x - 1];
                } else if (x + 1 < contColumnas && matrix[y - 1][x + 1]) {
                    pixelRegion = regions[y - 1][x + 1];
                } 
            }

            // check current row
            if (x && matrix[y][x - 1]) {
                pixelRegion = regions[y][x - 1];
            }

            // if not connected, start a new region
            if (!pixelRegion) {
                regionCollection.push([]);
                pixelRegion = regionCollection.length;
            }
            // remember region
            regionline[x] = pixelRegion;
            regionCollection[pixelRegion - 1].push([x, y]);

            // paint it
            ctx.fillStyle = "black";
            ctx.fillRect(x * sz + 1, y * sz + 1, sz - 2, sz - 2);
        }


        ctx.fillStyle = "white";
        ctx.fillText(pixelRegion, x * sz + 8, y * sz + 13);

    }
}
document.querySelector("#result").innerHTML = JSON.stringify(regionCollection);

<!DOCTYPE html>
<html>
<head>
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
  <title>getUserMedia</title>
</head>
<body>
	<canvas></canvas>
	<div id="result"></div>
</body>
</html>

How can I correct this? I can not solve the error ... It could be solved with a recursive function that traversing the matrix is called to check in each coordinate if it has 1s around it (up, down, left, right and diagonal). I'm stuck and I do not know how to fix the error

javascript matrices

asked by Norak 05.12.2017 в 10:03

source

3 answers

1

The problem is that you are checking if it belongs to the same region in the following way:

Check the 3 positions in the top row first:

Upper left diagonal box
Table above the current one
Upper right diagonal box

And then you check the current row (Here you only look at one position, since you have not passed through on the right):

Left frame to current

The problem occurs when the matrix arrives and reads the matrix[6][1] position. If you notice, after making all the checks listed above, none is positive. So you're assigning a new region!

NOTE: Row matrix[8][] is set to region 3 because you last checked the "Left frame to the current one". That is, even if you find a region called 2 above, then when you look to its left it is replaced by 3 .

answered by 05.12.2017 в 11:00

1

The element

"x": 1, "y": 6

It is surrounded by zeros in the row above, to its right and to its left. Although region 2 spreads down and right, it does not spread in the opposite direction.

var matrix = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 1, 1, 1, 0, 0, 0],
    [1, 1, 0, 1, 0, 0, 0, 1, 0, 0],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
    [0, 0, 1, 1, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 1, 1, 0],
    [0, 1, 0, 1, 0, 0, 0, 1, 1, 1],
    [0, 1, 0, 1, 1, 0, 0, 1, 1, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
];

var contFilas = matrix.length;
var contColumnas = matrix[0].length;
var canvas = document.querySelector("canvas");
var ctx = canvas.getContext("2d");
var sz = 20;
var regions = [];
var regionCollection = [];

canvas.width = sz * contColumnas;
canvas.height = sz * contColumnas;
ctx.fillStyle = "silver";
ctx.fillRect(0, 0, canvas.width, canvas.height);

for (var y = 0; y < contFilas; y++) {
    var regionline = [];
    regions.push(regionline);

    for (var x = 0; x < contColumnas; x++) {
        var pixelRegion = 0;
        regionline[x] = 0;
       


        if (matrix[y][x] === 1) {
            // check previous row
            if (y) {
                if (matrix[y - 1][x]) {
                    pixelRegion = regions[y - 1][x];
                } else if (x && matrix[y - 1][x - 1]) {
                    pixelRegion = regions[y - 1][x - 1];
                } else if (x + 1 < contColumnas && matrix[y - 1][x + 1]) {
                    pixelRegion = regions[y - 1][x + 1];
                }  
            }

            // check current row
            if (x && matrix[y][x - 1]) {
                pixelRegion = regions[y][x - 1];
            }  

            // if not connected, start a new region
            if (!pixelRegion) {
                console.log('New region on',{x:x, y:y});
                regionCollection.push([]);
                pixelRegion = regionCollection.length;
                console.log('pixelRegion on',{x:x, y:y}, 'is '+pixelRegion);
            }
            // remember region
            regionline[x] = pixelRegion;
            regionCollection[pixelRegion - 1].push([x, y]);

            // paint it
            ctx.fillStyle = "black";
            ctx.fillRect(x * sz + 1, y * sz + 1, sz - 2, sz - 2);
        }


        ctx.fillStyle = "white";
        ctx.fillText(pixelRegion, x * sz + 8, y * sz + 13);

    }
}

regionCollection.forEach(function(region,index) {
   console.log('region '+index, JSON.stringify(region));
});

<canvas></canvas>

answered by 05.12.2017 в 12:41

Doubt with the include php How do I pass an image from my view to a controller? MVC

score 1 · Accepted Answer

The problem comes when the cell from which you have to take the region is below. As only the upper cells are checked and the same row is going to interpret that it is a new region when it is not like that.

One solution could be to use a recursive function to create the entire region from one cell. When you find an active cell that does not belong to any region, a new region is created and the continuous cells are added recursively.

Something like this:

var matrix = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 1, 1, 1, 0, 0, 0],
    [1, 1, 0, 1, 0, 0, 0, 1, 0, 0],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
    [0, 0, 1, 1, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 1, 1, 0],
    [0, 1, 0, 1, 0, 0, 0, 1, 1, 1],
    [0, 1, 0, 1, 1, 0, 0, 1, 1, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
];

var contFilas = matrix.length;
var contColumnas = matrix[0].length;
var canvas = document.querySelector("canvas");
var ctx = canvas.getContext("2d");
var sz = 20;
var regions = [];
var regionCollection = [];

canvas.width = sz * contColumnas;
canvas.height = sz * contColumnas;
ctx.fillStyle = "silver";
ctx.fillRect(0, 0, canvas.width, canvas.height);

function createRegion(board, row, col, regionNum, region){
  // Si no viene array para la región lo creamos
  region = region || [];
  // Añadimos la celda a la región
  region.push([col, row]);
  board[row][col] = regionNum;
  // Si alguna celda contigua tiene valor -1 se añade a la región
  // llamando a la función recursiva
  if (board[row-1]){
    if (board[row-1][col-1]===-1) createRegion(board, row-1, col-1, regionNum, region);
    if (board[row-1][col]===-1) createRegion(board, row-1, col, regionNum, region);
    if (board[row-1][col+1]===-1) createRegion(board, row-1, col+1, regionNum, region);
  }
  if (board[row][col-1]===-1) createRegion(board, row, col-1, regionNum, region);
  if (board[row][col+1]===-1) createRegion(board, row, col+1, regionNum, region);
  if (board[row+1]){
    if (board[row+1][col-1]===-1) createRegion(board, row+1, col-1, regionNum, region);
    if (board[row+1][col]===-1) createRegion(board, row+1, col, regionNum, region);
    if (board[row+1][col+1]===-1) createRegion(board, row+1, col+1, regionNum, region);
  }
  // Devolvemos la región con las celdas añadidas
  return region;
}

// Crea un array igual que matrix con valores 0 y -1
var regionline = matrix.map(y => y.map(x => -x));
var regionCollection = [];

for (var y = 0; y < contFilas; y++) {
  for (var x = 0; x < contColumnas; x++){
    // Si el valor es -1 es una nueva región. Llama a la función recursiva a partir de esa posición
    if (regionline[y][x] === -1){
      regionCollection.push(createRegion(regionline, y, x, regionCollection.length +1));
    }
    // Dibuja la celda
    if (regionline[y][x] > 0){
        ctx.fillStyle = "black";
        ctx.fillRect(x * sz + 1, y * sz + 1, sz - 2, sz - 2);
    }
        ctx.fillStyle = "white";
        ctx.fillText(regionline[y][x], x * sz + 8, y * sz + 13);
  }
}
document.querySelector("#result").innerHTML = JSON.stringify(regionCollection);

	<canvas></canvas>
	<div id="result"></div>