Bitmap, check if orthogonal path is closed
A 2d bit array is given.
var map1 = [[0,0,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0],
[0,0,1,1,1,1,1,0],
[0,0,1,0,0,0,1,0],
[0,0,1,1,0,0,1,0],
[0,0,1,0,0,0,1,0],
[0,0,1,1,1,1,1,0],
[0,0,0,0,0,0,0,0]];
How can I programmatically check if some "those" are forming a closed path?
The two left bitmaps contain closed paths, the top one is obvious, the bottom one is just a closed path with nothing in it.
Two correct bitmaps do not contain closed paths, in the upper example one bit is missing, in the lower example one diagonal pixel is not counted, only orthogonal paths.
source to share
Find the cell that has 1, then "flood" from there. By this I mean: use the second card, everything is initially set to 0. When you encounter the first 1, set the cell in the second card to 1. Now check all adjacent cells by setting the cell in the second card to 1, if it is in the original card as well equals 1. As soon as you try to set a cell that was already 1, you know you have encountered a closed path; don't check that cell again or you will end up with an infinite loop.
EDIT: if you want a complete list of all cells connected to one cell by closed paths, juts adds every cell you encounter during the "flood" to the list that initially only contains the starting cell. If at some point you don't find another flood cell, there is no closed path and you can throw away the list. Depending on whether you want the little "stubs" in your linked bitmaps to be considered part of the path or not, you will need to do some kind of branching, introducing new lists for each branch, merging them if they cross.
source to share
I split your fiddle and added the findCycle () method.
var fill = function(map, x, y) {
if (Math.min(x,y) >= 0 && Math.max(x,y) < mapSize && map[x][y] == 0) {
map[x][y] = -1;
for (var dx = -1; dx <=1; dx +=1) {
for (var dy=-1; dy<=1; dy += 1) {
fill(map, x+dx, y+dy);
}
}
}
}
function detect(map) {
for(var x = 0; x + 1 < mapSize; x++){
for(var y = 0; y + 1 < mapSize; y++){
if (map[x][y] == 0) {
map[x][y] = -2;
return;
}
else if (map[x][y]== 1 && map[x+1][y]==1 && map[x][y+1]== 1 && map[x+1][y+1]==1) {
map[x][y] = -2;
return;
}
}
}
}
function findCycle(mapData) {
for(var x = 0; x < mapSize; x++){
for(var y = 0; y < mapSize; y++){
if (mapData[x][y] == 0) {
fill(mapData, x, y);
detect(mapData);
return;
}
}
}
}
It finds the first 0. Recursively fills in all adjacent 0's with "-1". It then searches for any remaining 0 that cannot be reached from the initial 0. (while searching for a square of four squares "1" (red).
A black square is drawn at the first point where it finds the loop.
source to share
How about this:
for each cell that set to 1
set that cell to -1
recursively look for neighbouring cells set to 1, and set them to -1
if you find a neighbouring cell that is already set to -1, loop found
clean-up (set all cells that are set to -1 to 0, they are no longer relevant)
This should work close to O (N).
Here I have implemented this in fiddle, look here . You will notice that the 4th example is odd: I have not worked out the kinks because your problem definition does not indicate whether you want the largest possible loop or any. In fact, you just wanted to know if the loop that is known exists when you hit the light blue pixel.
source to share