c++ - Method to split a matrix into blocks of the small matrix

Question

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

Answer 1

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++)

Answer 2

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.

Answer 3

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