Help me with this algorithm please

Picture: http://xs227.xs.to/xs227/08194/draw931.jpg

I have this matrix where each cell has N of width and M of height. (I know they appear to have diferent sizes but paint s*cks :P)


I have the values of p1 and p2 (x and y) given by p1[x] and p1[y], p2[x] and so on...

I have the (x,y) of the center C (of every cell, not only the 10th one).

I know the size of the whole matrix given by P(width) and Q(height).

The objective is: To find out all areas that include that blue box.
In this example areas 5 6 7 8 9 10 11 12 13 and 14 include it.

The box can have various sizes..
I cant find a good algorithm, can you help me? Thanks!

Usually I tell people who seem to think they need to get to Calculus III before they can program not to fret, but I am going to have to go ahead and suggest a couple more math classes to you, or at least a few hours of online tutorials.

If you know (x,y) is the center of an N by M square and you know which square (x,y) resides, you can certainly use basic algebra to calculate the absolute position of (x,y).

Example:

Code:

---

In my example I am going to use some ascii art, and ignore your duplicate "5" square.

Lets say you p2 is in some known relative location in square number 15.
I hate 2d arrays so we can see that each row is 5N wide, thus a the row is mathematically,
3M * 5N

From there you can add the column which you desire, which in this case is the fourth one
4N

So we know you are dealing with square 3M * 5N + 4N (yes this could be simplified further, but we needn't mess with that now).

---

That should get you started. On an important note: do not forget that when you are programming your geometry will be going the opposite direction and your counting will always be starting with 0.

Since you know p1 and p2, you have their x & y values.

Therefore, you get your minimum and maximum x values from p1 and p2, and get the min and max y values from p2.

Then, if any square in your grid satisfies both conditions for x (min_x <= your square <= max_x) and the same for y, you have the answer you need.

Todd