javascript - Detecting closed loop in a 2D array pattern - Stack Overflow

admin管理员组

文章数量:1410674

Let's assume that you get the following array:

foo = [
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,1,1,1,1,1,0,0],
    [0,0,0,1,0,0,0,1,0,0],
    [0,0,0,1,0,0,0,1,0,0],
    [0,0,0,1,1,1,0,1,0,0],
    [0,0,0,0,0,1,0,1,0,0],
    [0,0,0,0,0,1,1,1,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
]

How can I determine if the pattern of 1s is a closed loop? I have struggled with this for a few days. I have tried a recursive loop to find neighbors and words, but when you have a more plex pattern it won't work, for example:

foo = [
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,1,1,1,0,0,0,0],
    [0,0,0,1,0,1,0,0,0,0],
    [0,0,0,1,0,1,0,0,0,0],
    [0,0,0,1,1,1,1,1,0,0],
    [0,0,0,0,0,1,0,0,0,0],
    [0,0,0,0,0,1,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
]

Do someone have a magic algorithm to solve this ? :(

Let's assume that you get the following array:

foo = [
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,1,1,1,1,1,0,0],
    [0,0,0,1,0,0,0,1,0,0],
    [0,0,0,1,0,0,0,1,0,0],
    [0,0,0,1,1,1,0,1,0,0],
    [0,0,0,0,0,1,0,1,0,0],
    [0,0,0,0,0,1,1,1,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
]

How can I determine if the pattern of 1s is a closed loop? I have struggled with this for a few days. I have tried a recursive loop to find neighbors and words, but when you have a more plex pattern it won't work, for example:

foo = [
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,1,1,1,0,0,0,0],
    [0,0,0,1,0,1,0,0,0,0],
    [0,0,0,1,0,1,0,0,0,0],
    [0,0,0,1,1,1,1,1,0,0],
    [0,0,0,0,0,1,0,0,0,0],
    [0,0,0,0,0,1,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
]

Do someone have a magic algorithm to solve this ? :(

• javascript
• arrays
• html5-canvas
• phaser-framework

Share Improve this question Follow edited Jun 18, 2015 at 3:42 user1693593 asked Jun 17, 2015 at 22:26 Thiago FriasThiago Frias 13411 silver badge99 bronze badges 6

• You probably want to implement Dijkstra's Algorithm and iterate through your array as nodes. Then test to see if you have returned to your starting location. – Zze Commented Jun 17, 2015 at 22:30
• 1 Sorry, do you want the second example to count as having a closed loop? Also, do you need zeros within the loop or will four 1s in a square count? – user1675642 Commented Jun 17, 2015 at 22:34
• 1 I could see the "Flood Fill" algorithm working in this case, as in the bucket fill in a paint program. If you "fill" a region of 0's and it doesn't spill out of the edges of the array, it must be closed. You would have to try every separate region of 0's though. – lhoworko Commented Jun 17, 2015 at 22:38
• yes the second example a "magic" function should return a array with the coordinates of only the 1 that is a closed loop, my recursive function can make this with the first example, but with the second when it find 2 neighbors the function assume one direction and continue the loop, but like in the second example, it could get wrong direction and not closed the loop, its plex and my english is bad I trie'd the Dijkstra's Algorithm but it works for polygons, i dont know if it fit for this problem, and flood fill will expend too much of cpu Thank you guys wanna hear more ideias – Thiago Frias Commented Jun 18, 2015 at 3:55
• You could count the numbers of extremities of a loop and the number of fork. If the loop is closed, there will be as many forks as there is extremities (could be more) – AdminXVII Commented Jun 18, 2015 at 17:11

 |  Show 1 more ment

1 Answer 1

Sorted by: Reset to default 6

As Dagrooms said, try to find 1(s) with only one adjacent 1. Code looks like:

function isValid1(x,y){
  return (foo[x-1][y] + foo[x+1][y] + foo[x][y-1] + foo[x][y + 1])>1;
}

function validLoop(){
  for(var i = 0; i < rows; i++){
    for(var j = 0; j < columns; j++){
      if(foo[i][j] === 1 && !isValid1(i,j)) {
        return false;
      }
    }
  }
  return true;
}

where rows and columns are the 2d array size.

UPDATE

This will return true if there is at least one closed loop:

function numTouching1(x,y){
  return foo[x - 1][y] + foo[x + 1][y] + foo[x][y - 1] + foo[x][y + 1];
}

function validLoop(){
  var n = 0, x = 0; // x is current point's number of touching 1 and n is total
  for(var i = 0; i < rows; i++){
    for(var j = 0; j < columns; j++){
      if(foo[i][j] === 1) {
        x = numTouching1(i, j) - 2;
        if(x === -1 || x === 1 || x === 2){
          n += x;
        } 
      }
    }
  }
  return n > -1;
}

JSFiddle: https://jsfiddle/AdminXVII/b0f7th5d/

UPDATE 2 Extract the loop(s):

function numTouching1(x,y){
  return foo[x - 1][y] + foo[x + 1][y] + foo[x][y - 1] + foo[x][y + 1];
}

function extractLoop(){
  for(var i = 0; i < rows; i++){
    for(var j = 0; j < columns; j++){
      if(foo[i][j] === 1 && numTouching1(i, j) === 1){
          foo[i][j] = 0;
          extractLoop();break;
      }
    }
  }
}

JSFiddle: https://jsfiddle/AdminXVII/b0f7th5d/7/

UPDATE 3

This is to threat if there's more than one loop, thougth for one loop it's slower.

function numTouching1(x, y) {
    return foo[x - 1][y] + foo[x + 1][y] + foo[x][y - 1] + foo[x][y + 1];
}

function extractLoop() {
    for (var i = 0; i < rows; i++) {
        for (var j = 0; j < columns; j++) {
            if (foo[i][j] === 1 && numTouching1(i, j) === 1) {
                foo[i][j] = 0;
                extractLoop(); break;
            }
        }
    }
}

function validLoop(){
  extractLoop();
  for(var i = 0; i < rows; i++){
    for(var j = 0; j < columns; j++){
      if(foo[i][j] === 1 && numTouching1(i,j) == 2) {
        return true;
      }
    }
  }
  return true;
}

JSFiddle: https://jsfiddle/AdminXVII/w7zcgpyL/

UPDATE 4

Safer numTouching1() method:

function numTouching1(x, y) {
    return ((x > 0) ? foo[x - 1][y] : 0) + ((x < rows-1) ? foo[x + 1][y] : 0) + ((y > 0) ? foo[x][y - 1] : 0) + ((y < columns-1) ? foo[x][y + 1] : 0);
}

Modified previous JSFiddle

本文标签： javascriptDetecting closed loop in a 2D array patternStack Overflow