CODEWITHSUNDEEP
carraysalgorithmmatrix
Deegriz
Deegriz

Reputation: 1925

C Language - General algorithm to read a square matrix, based on the square number of it's side?

So we're reading a matrix and saving it in an array sequentially. We read the matrix from a starting [x,y] point which is provided. Here's an example of some code I wrote to get the values of [x-1,y] [x+1,y] [x,y-1] [x,y+1], which is a cross. 

for(i = 0, n = -1, m = 0, array_pos = 0; i < 4; i++, n++, array_pos++) {
   if(x+n < filter_matrix.src.columns && x+n >= 0 ) 
    if(y+m < filter_matrix.src.lines && y+m >= 0){
            for(k = 0; k < numpixels; k++) {
                arrayToProcess[array_pos].rgb[h] = filter_matrix.src.points[x+n][y+m].rgb[h];
            }
        }
    m = n;
    m++;
}

(The if's are meant to avoid reading null positions, since it's an image we're reading the origin pixel can be located in a corner. Not relevant to the issue here.)

Now is there a similar generic algorithm which can read ALL the elements around as a square (not just a cross) based on a single parameter, which is the size of the square's side squared? If it helps, the only values we're dealing with are 9, 25 and 49 (a 3x3 5x5 and 7x7 square).

Upvotes: 0

Views: 617

Answers (5)

Jonathan Leffler
Jonathan Leffler

Reputation: 753785

Given:

static inline int min(int x, int y) { return (x < y) ? x : y; }
static inline int max(int x, int y) { return (x > y) ? x : y; }

or equivalent macros, and given that:

  • the x-coordinates range from 0 to x_max (inclusive),
  • the y-coordinates range from 0 to y_max (inclusive),
  • the centre of the square (x,y) is within the bounds,
  • the square you are creating has sides of (2 * size + 1) (so size is 1, 2, or 3 for the 3x3, 5x5, and 7x7 cases; or if you prefer to have sq_side = one of 3, 5, 7, then size = sq_side / 2),
  • the integer types are all signed (so x - size can produce a negative value; if they're unsigned, you will get the wrong result using the expressions shown),

then you can ensure that you are within bounds by setting:

x_lo = max(x - size, 0);
x_hi = min(x + size, x_max);
y_lo = max(y - size, 0);
y_hi = min(y + size, y_max);

for (x_pos = x_lo; x_pos <= x_hi; x_pos++)
{
     for (y_pos = y_lo; y_pos <= y_hi; y_pos++)
     {
          // Process the data at array[x_pos][y_pos]
     }
}

Basically, the initial assignments determine the bounds of the the array from [x-size][y-size] to [x+size][y+size], but bounded by 0 on the low side and the maximum sizes on the high end. Then scan over the relevant rectangular (usually square) sub-section of the matrix. Note that this determines the valid ranges once, outside the loops, rather than repeatedly within the loops.

If the integer types are signed, you have ensure you never try to create a negative number during subtraction. The expressions could be rewritten as:

x_lo = x - min(x, size);
x_hi = min(x + size, x_max);
y_lo = y - min(y, size);
y_hi = min(y + size, y_max);

which isn't as symmetric but only uses the min function.

Upvotes: 2

Vikram Bhat
Vikram Bhat

Reputation: 6246

Here is a generalized code for reading the square centered at (x,y) of size n 

int startx = x-n/2;
int starty = y-n/2;

for(int u=0;u<n;u++) {

  for(int v=0;v<n;v++) {

      int i = startx + u;
      int j = starty + v;

      if(i>=0 && j>=0 && i<N && j<M) {

             printf(Matrix[i][j]);
      }
  }


}

Explanation: Start from top left value which is (x - n/2, y-n/2) now consider that you are read a normal square matrix from where i and j are indices of Matrix[i][j]. So we just added startx & starty to shift the matrix at (0,0) to (x-n/2,y-n/2).

Upvotes: 2

akksy
akksy

Reputation: 1

make use of this:

    while(int i<=0 && int j<=0)
for (i = x-1; i <= x+1; i++) {
for (j = y-1; j <= y+1; j++) {
     int elem = square[i][j];            
    }
}
}

Upvotes: 0

BlackJack
BlackJack

Reputation: 2876

Given the coordinates (x,y), you first need to find the surrounding elements. You can do that with a double for loop, like this:

for (int i = x-1; i <= x+1; i++) {
    for (int j = y-1; j <= y+1; j++) {
         int elem = square[i][j];            
    }
}

Now you just need to do a bit of work to make sure that 0 <= i,j < n, where n is the length of a side;

Upvotes: 1

user1659155
user1659155

Reputation: 1

I don't know whether the (X,Y) in your code is the center of the square. I assume it is.

If the side of the square is odd. generate the coordinates of the points on the square. I assume the center is (0,0). Then the points on the squares are (-side/2, [-side/2,side/2 - 1]); ([-side/2 + 1,side/2], -side/2); (side/2,[side/2 - 1,-side/2]);([side/2 - 1, side/2],-side/2);

side is the length of the square

Upvotes: 0

Related Questions