I need the different regions or "islands" made up of 1s within an array of any dimension to be separated. My example seemed to work correctly but there are some "special" cases like the following that don't work well. It should detect 2 elements or regions and yet it gets "confused" and finds 3 (when the 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't solve the error... It could be solved with a recursive function that calls the traversal of the matrix to check in each coordinate if it has 1s around it (up, down, left, right and diagonals). I'm stuck and I don't know how to fix the error
The problem is that you are checking if it belongs to the same region as follows:
You first check the 3 positions of the top row:
And then you check the current row (Here you only look at one position, since you haven't passed to the right yet):
The problem occurs when the array arrives and reads the position
matrix[6][1]. If you look, after performing all the checks listed above, none of them are positive. So you are assigning a new region!NOTE: The row
matrix[8][]is set to region3because you check the "Left to Current Box" last. That is, even if you find a region named2above, later when you look to its left it is replaced by3.The problem comes when the cell from which it has to take the region is below. Since only the cells above and in the same row are checked, it will interpret that it is a new region when it is not.
One solution might 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 that:
The element
"x": 1, "y": 6
It is surrounded by zeros in the top row, to its right and to its left. Although region 2 propagates down and to the right, it does not propagate in the reverse direction.