CS213 Assignment 3-Quad-trees Solution

This assignment is to implement a tree structure to represent images, which is particularly useful for some kinds of images. An image is considered to be a 2n × 2n matrix, each of whose entries is 0 (white) or 1 (black). Each entry is called a pixel. Instead of storing the whole matrix, different data structures are used to reduce the size. The quad-tree is one such.
A quad-tree is a rooted tree in which every node has either 0 or 4 children. Every node in the tree corresponds to some submatrix of the whole matrix, with size 2i × 2i for some 0 ≤ i ≤ n. The root node is the entire matrix. If all entries in a submatrix corresponding to a node are equal, the node is a leaf node, and it stores the value of the pixels in the submatrix. If there are distinct entries in the submatrix, divide it into 4 submatrices of size 2i−1 × 2i−1, called top-left, top-right, bottom-right, bottom-left, and recursively construct the subtrees corresponding to the 4 submatrices.
The size of the tree can be much smaller than the size of the matrix when there are large regions in the image with the same colour, which happens in many cases. This is true when rectangular windows of large size are used to set the colours of the pixels.
You have to implement a class called quad tree to represent such images. Only a header file that contains the class definition should be submitted. The operations to be performed are specified below.
1. quad tree(int n): a constructor that initializes to a matrix of size 2n×2n with all pixels 0. The value of n will be at most 20, and is called the height of the quad tree.
2. ~quad tree() : the destructor that destroys the tree.
3. quad tree(quad tree const &Q) : copy constructor.
4. void set(int x1, int y1, int x2, int y2, int b) : set all pixels in the submatrix with rows x1 to x2 and columns y1 to y2 (inclusive) to the value b. It can be assumed that 0 ≤ x1 ≤ x2 < 2n and 0 ≤ y1 ≤ y2 < 2n, if the tree has height n.
5. int get(int x1, int y1) const : return the value of the pixel (x1,y1).
6. int size() const : return the height n.
7. void overlap(quad tree const &Q): the new value of the matrix is the pixel-wise boolean OR with the matrix corresponding to Q. It can be assumed that Q has the same height as the image to which the operation is applied.
8. void intersect(quad tree &Q) : same as the previous except that the boolean AND of the two images is computed.
9. void complement() : complement all the entries in the matrix.
1
10. void resize(int m): Change the size of the matrix to 2m × 2m. This is done as follows. If m ≥ n, replace each pixel of the original image by a 2m−n ×2m−n matrix with all values equal to the original pixel. If m < n, divide the matrix into 2m ×2m submatrices, each of size 2n−m ×2n−m, and replace each submatrix by a pixel whose value occurs more often in the submatrix. If equal, choose 1.
11. void extract(int x1, int y1, int m) : the new value is the 2m×2m submatrix with rows from x1 to x1+2m −1 and columns y1 to y1+2m −1. It can be assumed that the submatrix is well-defined.
Submit a single file named RollNo 3.h . Make sure that you include any header files that are needed, and do not write any main function. Write a separate main program and check that it works correctly using, g++ -include headerfile.h mainprogram.cpp .
2