CODEWITHSUNDEEP
algorithmmatch
candied_orange
candied_orange

Reputation: 7334

Locate a shape in a 2D array of integers

On a fixed size map of integers

1,1,1,0,0,0,0,0,0,0,0,0,0
0,1,1,0,0,1,0,0,0,0,0,0,0
0,0,1,0,1,2,1,0,0,1,2,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0

Find where an arbitrary unrotated shape is located:

0,0,0,1,0
1,0,1,1,1

Output: [2,1] (The upper left corner of the shape)

The solution is a region that can supply the needed values for the shape from their relative positions in the map. Finding an integer value that is too large does not disqualify a region. Only one too small.

The brute force approach is to loop through every possible offset for the shape and then loop both matrixes testing if enough values are there.

Another approach is to sum the rows and columns of the map and the shape, then find where possible solutions exist then test each to see if they work. This would only help when the map is sparsely populated.

Can you suggest a better approach? Looking to reduce Big O complexity.

Upvotes: 1

Views: 680

Answers (1)

samgak
samgak

Reputation: 24417

One possible optimization would be to use an integral image.

Do the following steps:

1) Find the highest value in your shape and then pre-process the map clamping all values higher than max to max.

2) Create an integral image array, where an entry ii[y][x] contains the sum of all entries in the map[j][i] where j <= y and i <= x, computed similar to this:

for(int y = 0; y <= rows; y++)
{
    int rowsum = 0;
    for(int x = 0; x <= columns; x++)
    {
        rowsum += map[y][x];
        ii[y][x] = rowsum + (y > 0) ? ii[y-1][x] : 0;
    }
}

You can use the integral image array to quickly calculate the sum of all entries in a given rectangle of the map with just 4 array lookups (upper bounds checking of array indices omitted):

int computeRectSum(int x, int y, int width, int height)
{
    int sum = ii[y + (height - 1)][x + (width - 1)];
    if(x > 0)
        sum -= ii[y + (height - 1)][x-1];
    if(y > 0)
        sum -= ii[y-1][x + (width - 1)];
    if((x > 0) && (y > 0))
        sum += ii[y-1][x-1];
    return sum;
}

3) Sum the total of all values in your search shape.

4) Iterate across the map, and for each (x,y) compute the rectangle sum for (x, y, shape width, shape height). If it's less than the shape sum then there can't be a possible shape in the map with its top-left corner at (x,y) so you can skip it. Otherwise check.

Like row and column summing, this optimization will work best with sparse arrays, but I think performance should be slightly better because it's a more localized test. You could use both of them at once: if the sum for a row is less than the top row sum for the shape then exclude that entire row.

If the map is very sparsely populated you could also use the integral image to exclude large chunks of the map in a divide-and-conquer approach by checking areas much larger than the search shape.

Checking for a shape when the test in (4) passes:

For large shapes you could (breadth-first) recursively subdivide the shape, testing sub-regions at each step: first test the whole shape rectangle with the integral image (i.e. step 4), then if that passes subdivide into 4 sub-regions and test those in the same way, then test sub-sub-regions etc until you end up with a 1x1 sub-region in which case you are just doing your original check. You would have to compute the integral image for the shape also to use this algorithm.

Upvotes: 3

Related Questions