A community for technology geeks in Lebanon.

You are not logged in.

- Topics: Active • Unanswered

Pages: **1**

**arithma****Member**

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.

*Last edited by arithma (November 7 2010)*

**saeidw****Member**

arithma wrote:

The 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****Member**

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

**arithma****Member**

@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****Member**

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 = ??

or I did understand the thing wrong ?

**Joe****Member**

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.

Pages: **1**