Exercise - Overlapping Rectangle Sum

arithma

You are given a grid of integral values.
Ex:

0 1 2 3 4 5
6 7 8 9 0 1
1 3 5 7 9 1
5 6 5 6 5 6

In addition to its width and height.

You are asked to find the sum of the elements that fall inside the domain. The domain is defined as a list of rectangles that can overlap. Each rectangle is defined by four values: col (starting column), row(starting row), cols (width in columns), rows (height in rows).

An example domain to sum over for the above grid is:
Rectangle 1: 0 0 2 2
Rectangle 2: 1 1 2 2

The above two rectangles overlap on the single cell at coordinates (1, 1). The element in there should be added to the sum [strike]twice[/strike] once. The sum would then be: 0 + 1 + 6 + 7 + 8 + 3 + 5 = 30.

saeidw

arithma wroteThe above two rectangles overlap on the single cell at coordinates (1, 1). The element in there should be added to the sum twice. The sum would then be: 0 + 1 + 6 + 7 + 8 + 3 + 5 = 30.

Wouldn't that be 0 + 1 + 6 + 7 + 7 +8 + 3 + 5 = 37?

This looks like a fun exercise, I'll see if I can put up some simple code to do it later on.

jsaade

I think he meant it should be added once as it is an intersection.

arithma

@jsaade: You got it right.

The naive solution for the problem would be to go through each cell, check its inclusion-status in any of the rectangles, and then accordingly sum to a sentinel. I encourage you to see past that and try to solve for a performant algorithm (in possibly an infinite grid with arbitrarily large rectangles)

GN90

um shouldn't rectangle 1 be : 1 1 2 2 ?

cause in your case (0 0 2 2) rect1 would be :

0 1 2
6 7 8
1 3 5

and rect 2 would be :

7 8
3 5

so the overlap thing will be 7 8 3 5
and the sum will be 0 + 1 + 2 + 6 + 7 + 8 + 1 + 3 + 5 = ?? :P

or I did understand the thing wrong ?

Joe

rect1 (0 0 2 2) is

0 1 
6 7

rect2 (1 1 2 2) is

7 8
3 5

Look carefully at the definition of rectangles.