CODEWITHSUNDEEP
javascriptimage-processing
Anderson Green
Anderson Green

Reputation: 31810

Find all occurrences of one 2D array inside another 2D array

In JavaScript, I'm trying to find all matching coordinates of this 2D integer array:

enter image description here

inside this 2D integer array, with overlapping sub-arrays being counted:

enter image description here

Each image represents a 2D JavaScript integer array, and the black pixels correspond to 1, and the yellow pixels correspond to 0, but I depicted the arrays this way so that they would be easier to visualize.

So how can I find all matches of the array enter image description here inside the array enter image description here?

Here's the function I'm trying to implement:

findAllMatchesOfOne2DArrayInsideAnother2DArray(containedArray, containingArray){
    //find all matching coordinates of containedArray inside containingArray, and return a 2D array of coordinates
}

Upvotes: 0

Views: 426

Answers (1)

basilikum
basilikum

Reputation: 10526

Here is a way to get all occurances of any given 2D array inside another 2D array. It is assumed that all subarrays have the same dimension (nothing like [[1,0,0],[1,0]]).

var x = [[0,1,0,0,0,0,0],
        [1,1,1,0,0,1,0],
        [0,1,0,0,1,1,1],
        [0,0,0,0,0,1,0],
        [0,0,1,0,0,0,0],
        [0,1,1,1,0,0,0],
        [0,0,1,0,0,0,0]];

var y = [[0,1,0],[1,1,1],[0,1,0]];

var res = [];
for (var i = 0; i < x.length - y.length + 1; i++) {
    for (var k = 0; k < x[0].length - y[0].length + 1; k++) {
        var count = 0;
        for (var l = 0; l < y.length; l++) {
             for (var m = 0; m < y[l].length; m++) {
                count += Math.abs(y[l][m] - x[i + l][k + m]);
            }       
        }
        if (count === 0) {
            res.push([i, k]);
        }

    }
}

The array res will contain the "coordinates" of the top-left corner of each match. I'm sure you'll find better performing algorithms but this one seems to work :)

Upvotes: 2

Related Questions