CODEWITHSUNDEEP
c++algorithmmath
Phorce
Phorce

Reputation: 4642

Method to split a matrix into blocks of the small matrix

I have a problem and would like to know if anyone could offer an ideal solution.

Basically (small data) but, if I have a matrix like this:

     0 1 0 0
     1 1 1 0
     0 0 0 0
     1 1 0 0

I then need to split this matrix into blocks that are of the same size as the second matrix, in this case 2x2:

0 1
1 1

I know it has something to do with the offsetX/Y values and these change depending on the size of the (small) matrix, I just don't know the calculation to calculate such results. I'm going to be passing the offsetX/Y to a function (with the vector) so I can calculate the sum of the particular block.

Does anyone have any advice?

Thanks

Upvotes: 2

Views: 7716

Answers (3)

Cybercartel
Cybercartel

Reputation: 12592

Mathematically you can split the matrix with a curve for example a z curve or a peano curve. That way you would also reduce the dimensional complexity. A z curve uses 4 quads to split a plane and resemble a quadtree.

Edit: I just learned that it's z-order curve and not z curve: http://en.wikipedia.org/wiki/Z-order_curve. A z curve is something 3d in bionformatics http://en.wikipedia.org/wiki/Z_curve??? LOL! I'm not a bioinformaticians nor am I in wikipedia but that sound to me like nonsense. A z-ordered curve can also cover a 3d area. Maybe wikipedia wants to say this? Here is a big picture of a 3d z-order curve http://en.wikipedia.org/wiki/File:Lebesgue-3d-step3.png. It's even on the wikipedia article?????

Upvotes: 1

comingstorm
comingstorm

Reputation: 26117

In order to split your matrix in situ (that is, without copying it), you want a representation that can handle both the original and the split pieces -- which will make it easier to define recursive algorithms, and so forth:

template <class elt> class MatRef {
    elt* m_data;
    unsigned m_rows, m_cols;
    unsigned m_step;

    unsigned index(unsigned row, unsigned col)
    {
        assert(row < m_rows && col < m_cols);
        return m_step * row + col;
    }

public: // access
    elt& operator() (unsigned row, unsigned col)
    {
        return m_data[index(row,col)];
    }

public: // constructors
    MatRef(unsigned rows, unsigned cols, elt* backing)  // original matrix
        : m_rows(rows)
        , m_cols(cols)
        , m_step(cols)
        , m_data(backing)
    {}
    MatRef(unsigned start_row, unsigned start_col,
           unsigned rows, unsigned cols, MatRef &orig) // sub-matrix
        : m_rows(rows)
        , m_cols(cols)
        , m_step(orig.m_step)
        , m_data(orig.m_data + orig.index(start_row, start_col))
    {
        assert(start_row+rows <= orig.m_rows && start_col+cols <= orig.m_cols);
    }
};

The original matrix constructor assumes its backing argument points to an array of data elements which is at least rows*cols long, for storing the matrix data. The dimensions of the matrix are defined by data members m_rows and m_cols.

Data member m_step indicates how many data elements there are from the start of one row to the start of the next. For the original matrix, this is the same as m_cols. Note that the m_cols of a sub-matrix may be smaller than that of the original matrix it refers to -- that's how a sub-matrix "skips" elements of the original matrix that are not part of the sub-matrix. For this to work properly, m_step will necessarily be the same as in the original matrix.

Regardless of whether the matrix is skipping elements, data member m_data always points to the first element of the matrix. The assert() in the sub-matrix constructor ensures that each new sub-matrix fits inside the matrix it is derived from.

I'm not sure if this counts as an "interesting algorithm", but it is an efficient and convenient way to define and access submatrices.

Upvotes: 3

Jean-Bernard Pellerin
Jean-Bernard Pellerin

Reputation: 12670

import std.stdio : writeln;
void main(string[] args)
{
    int m=4, n=4;
    int[][] matrix = [[0, 1, 0, 0], [1, 1, 1, 0], [0, 0, 0, 0], [1, 1, 0, 0]];
    int mm=2, nn=2;
    int sum;
    for(int x=0; x<m; x+=mm)
      for(int y=0; y<n; y+=nn)
        sum += summation(matrix, x, y, mm, nn);
    writeln(sum);
}    
int summation(int[][] matrix, int offsetx, int offsety, int m, int n)
{
  int sum;
  for(int x=offsetx; x<offsetx+m; x++)
    for(int y=offsety; y<offsety+n; y++)
      sum += matrix[x][y];
  return sum;
}

Unless you're looking for something else? your question is vague when it comes to explaining what you're asking for.

(this compiles in D, since it's the only thing I have access to atm, use it as a guide to convert to C++)

Upvotes: 4

Related Questions