Tweeted twitter.com/#!/StackCompSci/status/568095031954968577
2 edited tags
| link
1
source | link

Efficient way to calculate sum in sliding window?

Assume you have a grid as below:

enter image description here

The square is the sliding window. I want to slide this window over all the possible position such that the window is contained in the grid (i.e the edges of the window should not cross the boundaries of the grid.)

For each such position I want to calculate the sum of the cells in the window. I'd like to be able to do this with different sizes of windows as well. More specifically, given some range for the possible widths and possible heights of windows, I want to calculate and store all the sums over the cells in the window, for all positions of the window, and for all possible width/height combinations.

As an example: if the possible widths are 2 and 3 and the possible heights are 4, 5 and 6, then there are 6 combinations: $2 \times 4$, $2 \times 5$, $2 \times 6$ $3 \times 4$, $3 \times 5$, $3 \times 6$ and for each such sliding window size, I want to store the sums over cells in the sliding window for all possible positions of the sliding window.

What would be an efficient way to do this?

Cheers