resize a quadtree closed

I implemented two solutions, first is for QuadTree case, second for 2D vector (array) case (my second solution was actually my first, I implemented it by mistake, forgot to notice that we need specifically QuadTree structure, but still I leave second one if it will help someone).

First solution using QuadTree structure.

Quad tree is implemented as QuadTree template structure that can store any data type T, by default it stores binary image data as size_t type (0/1, black/white). There are functions CreateQT for creating and filling quad tree of given height, TraverseQT a function that traverses all tree nodes and applies given callback to each of leaf nodes, ResizeQT that actually solves given task – resizes quad tree from current height n to new height m, DumpQT function that dumps quad tree to string for possibility of outputting it to console.

main() function just creates input tree of height n with CreateQT by filling it with random binary data by rand() % 2 calls, then it outputs original image to console by DumpQT call, then resizes from height n to height m by calling ResizeQT, and outputs final resized image to console using DumpQT.

Try it online!

#include <cstdlib>
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <array>
#include <memory>
#include <string>
#include <functional>
using namespace std;

template <typename T>
struct QuadTree {
    typedef T data_t;
    size_t height() const {
        return st[0] ? st[0]->height() + 1 : 0;
    }
    
    T data = T();
    // Sub-trees, in order Top-Left, Top-Right, Bottom-Left, Bottom-Right.
    array< shared_ptr<QuadTree>, 4 > st = {};
};

template <typename T>
static shared_ptr< QuadTree<T> > CreateQT(size_t const height, function<T()> const & filler) {
    shared_ptr< QuadTree<T> > r(new QuadTree<T>());
    if (height <= 0)
        r->data = filler();
    else
        for (size_t i = 0; i < r->st.size(); ++i)
            r->st[i] = CreateQT(height - 1, filler);
    return r;
}

template <typename T>
static void TraverseQT(QuadTree<T> const & qt, function<void(T const &)> const & visitor) {
    if (qt.height() <= 0)
        visitor(qt.data);
    else
        for (size_t i = 0; i < qt.st.size(); ++i)
            TraverseQT<T>(*qt.st[i], visitor);
}

template <typename T>
static void ResizeQT(QuadTree<T> & qt, size_t const m) {
    size_t const n = qt.height();
    if (n == m)
        return;
    if (n > 0 && m > 0) {
        for (size_t i = 0; i < qt.st.size(); ++i)
            ResizeQT(*qt.st[i], m - 1);
    } else if (m > 0) {
        qt.st = CreateQT<T>(m, [&](){ return qt.data; })->st;
        qt.data = T();
    } else if (n > 0) {
        map<T, size_t> cnt;
        TraverseQT<T>(qt, [&](T const & v){ ++cnt[v]; });
        // Find max
        pair<T, size_t> maxv = {{}, 0};
        for (auto const & p: cnt)
            if (p.second > maxv.second)
                maxv = p;
        qt.data = maxv.first;
        for (size_t i = 0; i < qt.st.size(); ++i)
            qt.st[i].reset();
    }
    return;
}

string VecToStr(vector<string> const & a) {
    string r;
    for (size_t i = 0; i < a.size(); ++i) {
        r += a[i];
        if (i < a.size() - 1)
            r += "\n";
    }
    return r;
}

template <typename T>
static vector<string> DumpQT(QuadTree<T> const & qt) {
    if (qt.height() <= 0)
        return {to_string(qt.data)};
    auto JoinH = [](vector<string> const & a, vector<string> const & b) {
        vector<string> r;
        for (size_t i = 0; i < min(a.size(), b.size()); ++i)
            r.push_back(a[i] + " " + b[i]);
        return r;
    };
    auto JoinV = [](vector<string> const & a, vector<string> const & b) {
        vector<string> r = a;
        r.insert(r.end(), b.begin(), b.end());
        return r;
    };
    return JoinV(
        JoinH(DumpQT(*qt.st[0]), DumpQT(*qt.st[1])),
        JoinH(DumpQT(*qt.st[2]), DumpQT(*qt.st[3]))
    );
}

int main() {
    try {
        vector< pair<size_t, size_t> > const nm = {{2, 3}, {3, 3}, {4, 3}};
        srand(0);
        typedef QuadTree<size_t> ImgQT;
        // Iterate through all "nm" tests
        for (size_t t = 0; t < nm.size(); ++t) {
            size_t n = nm[t].first, m = nm[t].second;
            cout << "n = " << n << ", m = " << m << endl;
            // Create/Fill input img of size 2^n with random values.
            ImgQT img = *CreateQT<ImgQT::data_t>(n, []()->size_t{ return rand() % 2; });
            cout << "Original:" << endl << VecToStr(DumpQT(img)) << endl;
            // Solve task, resize to 2^m.
            ResizeQT(img, m);
            cout << "Resized:" << endl << VecToStr(DumpQT(img)) << endl;
        }
        return 0;
    } catch (exception const & ex) {
        cout << "Exception: " << ex.what() << endl;
        return -1;
    } catch (...) {
        cout << "Unknown Exception!" << endl;
        return -1;
    }
}

Console output:

n = 2, m = 3
Original:
0 1 1 1
0 1 1 1
0 0 0 1
1 0 1 1
Resized:
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 1
1 1 0 0 1 1 1 1
1 1 0 0 1 1 1 1
n = 3, m = 3
Original:
1 1 0 1 0 1 1 1
1 0 1 0 1 1 0 1
1 1 1 0 1 0 1 0
1 0 0 0 1 1 0 1
0 0 1 1 0 0 0 0
1 0 0 1 1 0 1 1
1 0 0 0 1 1 1 1
1 0 0 0 0 0 1 0
Resized:
1 1 0 1 0 1 1 1
1 0 1 0 1 1 0 1
1 1 1 0 1 0 1 0
1 0 0 0 1 1 0 1
0 0 1 1 0 0 0 0
1 0 0 1 1 0 1 1
1 0 0 0 1 1 1 1
1 0 0 0 0 0 1 0
n = 4, m = 3
Original:
1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0
1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0
1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1
1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1
1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1
1 1 0 0 1 0 0 1 1 0 1 1 0 0 1 1
0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1
1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1
0 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0
1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1
0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0
1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1
1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1
0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1
Resized:
0 0 0 0 0 0 0 0
1 0 1 0 1 1 0 1
1 0 1 0 0 1 0 1
0 0 0 0 0 1 0 0
1 1 0 1 0 0 0 1
0 1 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1

Second solution using 2D vector.

In the beginning of code add extra tests to nm array with your desired n and m values. Input image is pre-filled with small random integer values, you may change this to read some input if needed.

Each image pixel is represented as a fixed-size array of size equal to number of channels (e.g. 1 for Gray and 3 for RGB). In next code each pixel has 1 channel, just one integer, for simplicity. Number of channels is configured by nchans constant, change nchans to e.g. 3 for testing of RGB image.

Each pixel is filled with random integers, range for random integers is controlled by next expression inside code rand() % (t <= 1 ? 10 : 3), modify value after modulus % to change range size of possible values.

Try it online!

#include <cstdlib>
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <array>
using namespace std;

int main() {
    try {
        vector< pair<size_t, size_t> > const nm = {{2, 3}, {3, 3}, {4, 3}};
        size_t const nchans = 1; // Number of channels (colors), e.g. 1 for Gray and 3 for RGB.
        typedef array<size_t, nchans> PixelT;
        srand(0);
        // Iterate through all "nm" tests
        for (size_t t = 0; t < nm.size(); ++t) {
            vector< vector<PixelT> > img;
            size_t n = nm[t].first, m = nm[t].second;
            cout << "n = " << n << ", m = " << m << endl;
            cout << "Original:" << endl;
            // Create/Fill input img of size 2^n with random values.
            // (1 << n) is same as 2^n (power of 2).
            for (size_t i = 0; i < (1 << n); ++i) {
                img.resize(img.size() + 1);
                for (size_t j = 0; j < (1 << n); ++j) {
                    PixelT p = {};
                    for (size_t k = 0; k < p.size(); ++k) {
                        p[k] = rand() % (t <= 1 ? 10 : 3);
                        cout << p[k];
                        if (k < p.size() - 1)
                            cout << ",";
                    }
                    cout << " ";
                    img[i].push_back(p);
                }
                cout << endl;
            }
            // Solve task, resize to 2^m.
            vector< vector<PixelT> > oimg;
            if (n <= m) {
                for (size_t i = 0; i < (1 << m); ++i) {
                    oimg.resize(oimg.size() + 1);
                    for (size_t j = 0; j < (1 << m); ++j) {
                        oimg[i].push_back(
                            img[i >> (m - n)][j >> (m - n)]
                        );
                    }
                }
            } else {
                for (size_t i = 0; i < (1 << m); ++i) {
                    oimg.resize(oimg.size() + 1);
                    for (size_t j = 0; j < (1 << m); ++j) {
                        // Count number of occurances
                        map<PixelT, size_t> cnt;
                        for (size_t k = (i << (n - m)); k < ((i << (n - m)) + (1 << (n - m))); ++k)
                            for (size_t l = (j << (n - m)); l < ((j << (n - m)) + (1 << (n - m))); ++l)
                                ++cnt[img[k][l]];
                        // Find max
                        pair<PixelT, size_t> maxv = {{}, 0};
                        for (auto const & p: cnt)
                            if (p.second > maxv.second)
                                maxv = p;
                        oimg[i].push_back(maxv.first);
                    }
                }
            }
            // Output results
            cout << "Resized:" << endl;
            for (size_t i = 0; i < oimg.size(); ++i) {
                for (size_t j = 0; j < oimg[i].size(); ++j) {
                    auto const & p = oimg[i][j];
                    for (size_t k = 0; k < p.size(); ++k) {
                        cout << p[k];
                        if (k < p.size() - 1)
                            cout << ",";
                    }
                    cout << " ";
                }
                cout << endl;
            }
        }
        return 0;
    } catch (exception const & ex) {
        cout << "Exception: " << ex.what() << endl;
        return -1;
    } catch (...) {
        cout << "Unknown Exception!" << endl;
        return -1;
    }
}

Example output for Gray image (nchans = 1):

n = 2, m = 3
Original:
8 9 8 7 
5 7 5 5 
0 2 3 0 
2 1 7 1 
Resized:
8 8 9 9 8 8 7 7 
8 8 9 9 8 8 7 7 
5 5 7 7 5 5 5 5 
5 5 7 7 5 5 5 5 
0 0 2 2 3 3 0 0 
0 0 2 2 3 3 0 0 
2 2 1 1 7 7 1 1 
2 2 1 1 7 7 1 1 
n = 3, m = 3
Original:
5 5 7 0 6 1 5 6 
7 3 1 0 5 8 6 0 
0 7 7 7 1 7 6 7 
3 8 3 7 7 4 2 1 
8 6 9 4 9 5 8 9 
9 6 1 4 4 6 8 2 
2 4 7 6 8 2 7 3 
3 3 0 2 7 5 1 4 
Resized:
5 5 7 0 6 1 5 6 
7 3 1 0 5 8 6 0 
0 7 7 7 1 7 6 7 
3 8 3 7 7 4 2 1 
8 6 9 4 9 5 8 9 
9 6 1 4 4 6 8 2 
2 4 7 6 8 2 7 3 
3 3 0 2 7 5 1 4 
n = 4, m = 3
Original:
2 2 2 2 2 1 2 2 2 0 1 0 0 0 0 2 
0 0 2 2 2 2 1 2 1 2 1 2 0 1 1 2 
1 0 2 0 1 0 2 1 1 1 1 1 1 1 1 1 
1 0 0 0 0 0 1 1 1 1 1 1 0 2 0 1 
2 1 0 0 2 2 1 1 0 1 1 2 1 1 2 0 
1 1 0 0 1 1 1 2 2 1 2 2 0 2 1 2 
1 0 0 0 1 2 1 0 2 2 0 0 0 2 1 2 
2 1 0 0 1 2 1 0 1 0 2 2 2 0 2 2 
0 1 1 2 2 1 0 2 1 0 1 2 0 2 2 1 
0 0 0 2 0 1 2 2 2 1 1 2 1 1 1 2 
1 1 1 0 2 2 2 1 1 2 1 0 0 0 0 2 
1 0 0 0 2 2 1 1 2 2 0 0 1 1 1 2 
1 2 2 1 1 1 2 2 2 2 0 0 2 2 2 2 
1 2 1 2 2 2 2 2 0 0 2 2 0 0 0 2 
0 0 0 0 2 0 0 1 1 2 2 0 1 1 0 0 
0 0 1 1 0 0 1 1 0 0 1 2 1 2 1 0 
Resized:
0 2 2 2 2 1 0 2 
0 0 0 1 1 1 1 1 
1 0 1 1 1 2 1 2 
1 0 1 0 2 0 0 2 
0 2 1 2 1 1 1 1 
1 0 2 1 2 0 0 2 
1 1 1 2 0 0 0 2 
0 0 0 1 0 2 1 0 

Example output for RGB image (nchans = 3):

n = 2, m = 3
Original:
8,9,8 7,5,7 5,5,0 2,3,0 
2,1,7 1,5,5 7,0,6 1,5,6 
7,3,1 0,5,8 6,0,0 7,7,7 
1,7,6 7,3,8 3,7,7 4,2,1 
Resized:
8,9,8 8,9,8 7,5,7 7,5,7 5,5,0 5,5,0 2,3,0 2,3,0 
8,9,8 8,9,8 7,5,7 7,5,7 5,5,0 5,5,0 2,3,0 2,3,0 
2,1,7 2,1,7 1,5,5 1,5,5 7,0,6 7,0,6 1,5,6 1,5,6 
2,1,7 2,1,7 1,5,5 1,5,5 7,0,6 7,0,6 1,5,6 1,5,6 
7,3,1 7,3,1 0,5,8 0,5,8 6,0,0 6,0,0 7,7,7 7,7,7 
7,3,1 7,3,1 0,5,8 0,5,8 6,0,0 6,0,0 7,7,7 7,7,7 
1,7,6 1,7,6 7,3,8 7,3,8 3,7,7 3,7,7 4,2,1 4,2,1 
1,7,6 1,7,6 7,3,8 7,3,8 3,7,7 3,7,7 4,2,1 4,2,1 
n = 3, m = 3
Original:
8,6,9 4,9,5 8,9,9 6,1,4 4,6,8 2,2,4 7,6,8 2,7,3 
3,3,0 2,7,5 1,4,3 2,9,4 9,6,4 7,3,5 3,3,0 4,3,1 
4,5,9 0,7,6 9,6,9 7,0,3 2,4,1 2,5,1 9,7,0 0,4,8 
4,7,6 1,8,2 0,4,1 5,7,0 4,2,6 7,3,4 8,4,4 1,7,6 
6,3,0 2,7,0 7,8,3 3,9,3 1,4,1 3,2,1 4,0,9 4,1,2 
0,2,8 6,1,5 6,9,8 5,7,0 4,3,5 1,4,7 6,6,1 7,4,1 
3,9,4 6,4,9 5,7,0 2,5,0 6,0,2 3,5,7 8,7,5 1,0,7 
3,1,6 2,7,2 1,3,2 5,5,6 5,9,7 3,3,7 2,2,1 4,6,5 
Resized:
8,6,9 4,9,5 8,9,9 6,1,4 4,6,8 2,2,4 7,6,8 2,7,3 
3,3,0 2,7,5 1,4,3 2,9,4 9,6,4 7,3,5 3,3,0 4,3,1 
4,5,9 0,7,6 9,6,9 7,0,3 2,4,1 2,5,1 9,7,0 0,4,8 
4,7,6 1,8,2 0,4,1 5,7,0 4,2,6 7,3,4 8,4,4 1,7,6 
6,3,0 2,7,0 7,8,3 3,9,3 1,4,1 3,2,1 4,0,9 4,1,2 
0,2,8 6,1,5 6,9,8 5,7,0 4,3,5 1,4,7 6,6,1 7,4,1 
3,9,4 6,4,9 5,7,0 2,5,0 6,0,2 3,5,7 8,7,5 1,0,7 
3,1,6 2,7,2 1,3,2 5,5,6 5,9,7 3,3,7 2,2,1 4,6,5 
n = 4, m = 3
Original:
1,1,0 1,0,0 1,0,1 1,0,0 0,1,0 1,0,1 0,1,0 0,0,1 0,1,1 1,1,0 1,0,0 0,1,1 1,1,0 0,1,0 1,1,0 0,0,0 
0,1,0 1,1,1 1,0,1 0,1,0 0,1,0 0,0,0 1,0,0 0,0,1 1,1,0 1,0,1 0,1,0 0,1,1 0,0,1 1,1,0 0,0,1 1,0,1 
0,0,1 1,0,1 0,1,0 1,0,0 0,1,0 0,1,0 1,0,1 1,1,0 0,0,1 1,0,0 0,1,0 0,1,1 1,0,1 1,0,0 0,1,0 1,1,1 
1,1,1 1,1,1 1,1,1 0,0,1 1,1,1 0,0,0 1,0,0 0,0,0 1,1,1 1,1,0 1,1,0 1,1,0 0,1,0 1,0,0 0,1,1 0,1,0 
0,1,1 0,0,0 0,1,1 0,0,1 1,1,0 1,0,1 0,1,0 1,0,1 1,1,0 0,0,1 1,1,0 1,0,0 1,0,0 0,0,1 1,1,1 1,0,0 
1,1,1 0,1,1 1,1,0 0,0,1 1,0,1 1,0,0 0,1,1 0,1,1 0,1,1 1,1,1 1,1,1 1,1,1 1,1,0 0,1,1 0,0,0 0,1,0 
0,1,0 1,0,0 1,1,1 0,1,1 0,0,0 0,0,0 1,0,0 1,0,0 1,0,1 1,0,1 0,0,1 1,0,0 0,1,1 1,1,0 0,1,0 1,1,1 
0,1,0 1,0,0 1,0,0 0,1,0 1,1,1 1,0,0 1,1,0 0,0,1 1,1,1 1,1,0 1,1,0 0,1,0 0,1,0 1,1,1 1,1,1 1,0,1 
1,0,0 0,0,1 1,0,1 0,1,1 1,1,1 1,0,1 0,1,0 0,1,1 0,1,0 0,1,0 1,1,1 1,0,1 1,0,1 1,0,0 1,1,0 0,1,1 
0,1,0 1,0,1 1,1,0 0,1,1 0,0,1 0,0,1 0,0,1 1,1,1 1,1,1 1,1,0 1,0,0 0,1,1 0,0,0 0,1,1 1,0,0 1,0,1 
0,1,1 0,1,0 0,0,0 1,0,1 1,0,1 1,0,0 1,0,0 0,1,1 1,1,1 1,0,0 1,0,1 0,0,0 1,0,0 0,1,1 0,1,0 0,1,0 
0,1,0 0,0,0 1,0,1 0,0,1 0,1,0 1,0,0 1,0,1 0,0,0 1,1,1 1,1,0 0,0,0 0,0,1 0,0,1 1,1,0 1,1,1 0,1,1 
1,1,1 1,0,0 0,1,0 1,0,0 0,0,1 0,1,0 0,0,0 0,0,1 0,1,0 0,1,0 1,1,1 0,1,0 0,0,0 0,1,0 0,1,1 1,0,0 
1,1,1 0,0,0 0,1,0 0,0,0 0,1,1 1,0,1 0,1,0 1,1,1 0,0,1 0,0,0 0,0,0 1,0,1 1,1,0 1,0,1 1,1,0 1,1,0 
1,0,1 1,1,1 0,1,0 1,1,0 1,0,1 1,1,0 1,0,1 1,0,0 0,0,1 0,0,1 1,1,0 0,1,0 1,0,1 0,1,0 1,0,0 0,1,0 
0,1,1 0,0,0 0,1,0 0,0,0 0,1,0 0,1,1 1,1,0 1,0,1 1,1,1 0,0,1 0,0,1 1,1,1 0,1,1 0,0,0 0,0,0 0,0,0 
Resized:
0,1,0 1,0,1 0,1,0 0,0,1 1,1,0 0,1,1 1,1,0 0,0,0 
1,1,1 0,0,1 0,1,0 0,0,0 0,0,1 1,1,0 1,0,0 0,1,0 
0,1,1 0,0,1 1,0,1 0,1,1 0,0,1 1,1,1 0,0,1 0,0,0 
0,1,0 0,1,0 0,0,0 1,0,0 1,0,1 0,0,1 0,1,0 1,1,1 
0,0,1 0,1,1 0,0,1 0,0,1 0,1,0 0,1,1 0,0,0 0,1,1 
0,1,0 1,0,1 1,0,0 0,0,0 1,1,1 0,0,0 0,0,1 0,1,0 
1,1,1 0,1,0 0,0,1 0,0,0 0,1,0 0,0,0 0,0,0 1,1,0 
0,0,0 0,1,0 0,1,0 1,0,1 0,0,1 0,0,1 0,0,0 0,0,0 

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top