1

Necesito que se separen las diferentes regiones o "islas" formadas por 1s dentro de una matriz de cualquier dimensión. Mi ejemplo parecía funcionar correctamente pero hay algún caso "especial" como el siguiente que no trabaja bien. Debería detectar 2 elementos o regiones y sin embargo se "confunde" y encuentra 3 (cuando la 2 y 3 deberían ser la misma). Podéis correr el ejemplo para ver más claro lo que explico.

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>

¿Cómo puedo corregir esto? no consigo solucionar el error... Podría solucionarse con una función recursiva que el recorrer la matrix se llame para comprobar en cada coordenada si tiene 1s a su alrededor (arriba, abajo, izquierda, dcha y diagonales). Estoy estancada y no sé cómo solucionar el error

1
  • Puedes poner matrix[2][7]=0 y ver si te encuentra 4 islas? Si te encuentra 4 regiones ya sé dónde está el error.
    – Flowen
    Commented el 5 dic. 2017 a las 9:46

3 respuestas 3

1

El problema viene cuando la celda a partir de la que tiene que coger la región está debajo. Como únicamente se comprueban las celdas superiores y de la misma fila va a interpretar que es una región nueva cuando no es así.

Una solución podría ser la de utilizar una función recursiva para crear la región completa a partir de una celda. Cuando encuentres una celda activa que no pertenece a ninguna región se crea una nueva región y se van añadiendo las celdas continuas de forma recursiva.

Algo así:

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>

1

El problema es que estás comprobando si pertenece a la misma región del siguiente modo:

Compruebas primero las 3 posiciones de la fila superior:

  • Cuadro diagonal superior izquierda
  • Cuadro superior al actual
  • Cuadro diagonal superior derecha

Y posteriormente compruebas la fila actual (Aquí sólo miras una posición, ya que por la derecha aun no has pasado):

  • Cuadro izquierdo al actual

El problema ocurre cuando la matriz llega y lee la posición matrix[6][1]. Si te fijas, después de realizar todas las comprobaciones listadas arriba, ninguna resulta positiva. Por lo que está asignando una nueva región!

NOTA: La fila matrix[8][] se establece a región 3 porque compruebas en último lugar el "Cuadro izquierdo al actual". Es decir, aunque encuentre una región llamada 2 encima, después, cuando mira a su izquierda es sustituida por 3.

1

El elemento

"x": 1, "y": 6

Está rodeado de ceros en la fila de arriba, a su derecha y a su izquierda. Aunque la región 2 se propaga hacia abajo y la derecha, no se propaga en sentido inverso.

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>

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.