優化形狀檢測算法

Question

我有0和1的矩陣，我需要從該矩陣中提取「形狀」。形狀由1個8方向連接組成。在最後的結果中，我得到了二維數組形狀。原始矩陣中的每一組形狀都由小區索引組成。我寫了腳本，它的工作原理，除了它與更大的矩陣崩潰。而我在控制檯中得到錯誤Uncaught RangeError: Maximum call stack size exceeded我需要使它適用於1000 x 1000等更大的矩陣。

這裏是我的代碼：

var matrixCols = 150; 
 
var matrixRows = 150; 
 
var matrix = []; 
 
var shapes = []; 
 
var checkedCels = []; 
 

 

 
function createMatrix() { 
 
\t for(var i = 0; i < matrixRows; i++) { 
 
    \t var row = []; 
 
\t \t for(var j = 0; j < matrixRows; j++) { 
 
    \t var value = Math.round(Math.random()); 
 
     row.push(value); 
 
    \t matrix.push(value); 
 
    } 
 
    console.log(JSON.stringify(row)); 
 
    } \t 
 
} 
 

 
function getShapes() { 
 
\t for(var i = 0; i < matrix.length; i++) { 
 
    \t if(checkedCels.indexOf(i) === -1 && matrix[i] === 1) { 
 
    \t shapes.push(formShape(i)); 
 
    } 
 
    } 
 
    
 
    console.log('Total shapes:', shapes.length); 
 
    console.log(shapes); 
 
} 
 

 
function formShape(startIndex) { 
 
\t return getNeighbours(startIndex); 
 
} 
 

 
function getNeighbours(index) { 
 
\t if(checkedCels.indexOf(index) > -1) { 
 
    \t return []; 
 
    } 
 
    var cels = [index]; 
 
    checkedCels.push(index); 
 
    
 
    var nwIndex = index - matrixCols - 1; 
 
    var nwCel = matrix[nwIndex]; 
 
    if(typeof nwCel !== 'undefined' && nwCel === 1 && index % matrixCols > 0) { 
 
    \t cels = cels.concat(getNeighbours(nwIndex)); 
 
    } 
 
    
 
    var nIndex = index - matrixCols; 
 
    var nCel = matrix[nIndex]; 
 
    if(typeof nCel !== 'undefined' && nCel === 1) { 
 
    \t cels = cels.concat(getNeighbours(nIndex)); 
 
    } 
 
    
 
    var neIndex = index - matrixCols + 1; 
 
    var neCel = matrix[neIndex]; 
 
    if(typeof neCel !== 'undefined' && neCel === 1 && index % matrixCols < (matrixCols - 1)) { 
 
    \t cels = cels.concat(getNeighbours(neIndex)); 
 
    } 
 
    
 
    var wIndex = index - 1; 
 
    var wCel = matrix[wIndex]; 
 
    if(typeof wCel !== 'undefined' && wCel === 1 && index % matrixCols > 0) { 
 
    \t cels = cels.concat(getNeighbours(wIndex)); 
 
    } 
 
    
 
    var eIndex = index + 1; 
 
    var eCel = matrix[eIndex]; 
 
    if(typeof eCel !== 'undefined' && eCel === 1 && index % matrixCols < (matrixCols - 1)) { 
 
    \t cels = cels.concat(getNeighbours(eIndex)); 
 
    } 
 
    
 
    var swIndex = index + matrixCols - 1; 
 
    var swCel = matrix[swIndex]; 
 
    if(typeof swCel !== 'undefined' && swCel === 1 && index % matrixCols > 0) { 
 
    \t cels = cels.concat(getNeighbours(swIndex)); 
 
    } 
 
    
 
    var sIndex = index + matrixCols; 
 
    var sCel = matrix[sIndex]; 
 
    if(typeof sCel !== 'undefined' && sCel === 1) { 
 
    \t cels = cels.concat(getNeighbours(sIndex)); 
 
    } 
 
    
 
    var seIndex = index + matrixCols + 1; 
 
    var seCel = matrix[seIndex]; 
 
    if(typeof seCel !== 'undefined' && seCel === 1 && index % matrixCols < (matrixCols - 1)) { 
 
    \t cels = cels.concat(getNeighbours(seIndex)); 
 
    } 
 
    
 
    return cels; 
 
} 
 

 
createMatrix(); 
 
getShapes();

我如何優化呢？

Answer 1

可避免getNeighbours函數的遞歸，以維持細胞的表檢查（最初只包含startIndex），並在每次迭代：

• 採取一個項目從列表中
• 檢查它是否正常（不檢查，該索引的矩陣值1）
• 它的鄰居添加到列表中，檢查
• 重複

當沒有更多單元要檢查時，此循環停止。

通過不使用遞歸，程序不會用完堆棧空間，並且算法將能夠處理更大的矩陣（只要當前檢查的列表不超過可用內存）。

除此之外，還有另一種可能的優化：checkedCells目前是一個數組，並且查看是否已使用.indexOf()（這是O（n）操作）分析了單元。將checkedCells更改爲保留鍵的分析單元索引將減少O（1）的查找。

這裏是你的代碼，根據以上兩點修改：

console.clear(); 
 

 
var matrixCols = 7; 
 
var matrixRows = 7; 
 
var matrix = []; 
 
var shapes = []; 
 
var checkedCels = {}; 
 

 

 
function createMatrix() { 
 
    for (var i = 0; i < matrixRows; i++) { 
 
    var row = []; 
 
    for (var j = 0; j < matrixRows; j++) { 
 
     var value = Math.round(Math.random()); 
 
     // value = Math.random() > 0.75 ? 1 : 0; // to change the probability of a cell being "set" 
 
     row.push(value); 
 
     matrix.push(value); 
 
    } 
 
    console.log(row.map(function(x) { 
 
     return " X" [x] 
 
    }).join('')); 
 
    } 
 
} 
 

 
function getShapes() { 
 
    for (var i = 0; i < matrix.length; i++) { 
 
    if (!checkedCels[i] && matrix[i] === 1) { 
 
     shapes.push(formShape(i)); 
 
    } 
 
    } 
 

 
    console.log('Total shapes:', shapes.length); 
 
    console.log(shapes); 
 
} 
 

 
function formShape(startIndex) { 
 
    var cels = []; 
 
    var toCheck = [startIndex]; 
 

 
    while (toCheck.length) { 
 
    var index = toCheck.pop(); 
 

 
    if (checkedCels[index]) { 
 
     continue; 
 
    } 
 

 
    if (matrix[index] !== 1) { 
 
     continue; 
 
    } 
 

 
    cels.push(index); 
 
    checkedCels[index] = 1; 
 

 
    var neighbours = []; 
 

 
    if (index % matrixCols > 0) { 
 
     neighbours.push(index - matrixCols - 1); // NW 
 
     neighbours.push(index - 1); // W 
 
     neighbours.push(index + matrixCols - 1); // SW 
 
    } 
 
    if (index % matrixCols < (matrixCols - 1)) { 
 
     neighbours.push(index - matrixCols + 1); // NE 
 
     neighbours.push(index + 1); // E 
 
     neighbours.push(index + matrixCols + 1); // SE 
 
    } 
 
    neighbours.push(index - matrixCols); // N 
 
    neighbours.push(index + matrixCols); // S 
 

 
    neighbours.forEach(function(n) { 
 
     if (typeof matrix[n] !== 'undefined') { 
 
     toCheck.push(n); 
 
     } 
 
    }); 
 
    } 
 

 
    return cels; 
 
} 
 

 

 
createMatrix(); 
 
getShapes();

我限制了矩陣的尺寸爲7x7的可讀性，但上面的代碼應該解決1000×1000矩陣在幾秒。