Goals and Overview In this PA (Programming Assignment) you will: ⚫learn about implementing a ternary (3-ary) tree • learn to design more complex recursive algorithms • learn about a possible method of image compression using space-partitioning trees Part 1: The Triple Tree Class A TripleTree is a ternary tree whose nodes represent rectangular regions of a PNG image. The root represents the entire image. The three children (referred to as A, B, and C, if present) of any node nd represent three equal or roughly equal horizontal or vertical partitions of nd's image region. Every node also contains: • a pixel representing the average colour of the pixels in its rectangular region ⚫ the upper-left image coordinates of its rectangular region ⚫ the width of its rectangular region in pixels, and ⚫ the height of its rectangular region in pixels Building a TripleTree The contructor of the TripleTree receives a PNG image of non-zero dimensions. The region for each node is split as equally as possible, and symmetrically, into three (or two) smaller regions along the longer of the two dimensions of the node being split. See the documentation in tripletree.h for details about how to determine the split axis and how to determine the dimensions and coordinates of the split pieces. A freshly constructed TripleTree will have a leaf node corresponding to each individual pixel of the original image. For example, an 8x5 image will be progressively split into the regions shown in the image below: which has the corresponding tree structure below: 1/5 Note that due to required symmetry of splitting, every node in the tree has exactly 0, 2, or 3 children; there will never be a node with only one child. Furthermore, any node that has exactly 2 children will have them attached as children A and C; child B will be null. To complete this part of the assignment, you should complete (or modify) the following functions: In class TripleTree: • TripleTree (PNG& imIn) • void Clear() void Copy (const Triple Tree& other) • PNG Render() const void Prune (double tol) void FlipHorizontal() • void Rotate CCW() • int NumLeaves () const • Node* Build Node (PNG& im, pair<unsigned int, unsigned int> ul, int w, int h) Many of the functions above will require private recursive helpers. It is up to you to add the declarations into tripletree_private.h, giving them appropriate signatures, and implementing them in tripletree.cpp. Advice: The constructor (which will use BuildNode) is critical for all of the other tree functionality. It is recommended to focus your efforts into first correctly implementing Build Node which will be used in all of the testing functions. Part 2: Image compression using TripleTrees As a result of the hierarchical structure of the tree, along with each node storing the average colour of its rectangular region, we can trim away portions of the tree representing areas without fine pixel-level detail. This is achieved by the Prune function, which receives a tolerance parameter. This function attempts, starting near the top of a freshly built tree, to remove all of the descendants of a node, if all of the leaf nodes below the current node have colour within tolerance of the node's average colour. In this way, areas of the image with little colour variability can be replaced with a single rectangle of solid colour, while areas with fine pixel detail can remain detailed. The image quality may be reduced, but fine details will still be visible, and the size of the structure used to store the image data will also be reduced. An example of the pruning effect is demonstrated in the pair of images below. Original image (upscaled): 2/5 1P:2 0007890 Rendered image after pruning at tolerance 0.02 (upscaled): TIME 258 ESOK! TIME 258 1P:2 0007890 ESOK! The tree constructed from the original image contains 57,344 leaf nodes; one for each pixel in the image. The tree obtained after pruning contains 17,494 leaf nodes. To complete this part of the assignment, you should complete (or modify) the following functions: In class TripleTree: It may void Prune (double tol) be helpful to write two recursive helpers for this function. Testing We have provided a file testpa3.cpp which writes your output images to the outputs folder along with some diagnostic prints to console. This is not a complete test of functionality! You are highly encouraged to add your own testing code to this file. The executable can be compiled by typing: make You can run the given tests on different input images by specifying a command-line argument as a number between 1 and 6, e.g.: /testpa3 6 Grading Information The following files are used to grade this PA: 3/5 ⚫ tripletree_private.h ⚫ tripletree.cpp All other files (including any testing files you create) will not be used for grading. Getting the Given Code Download the source files here pa3-20240310-1809.zip and follow the procedures you learned in lab to move them to your home directory on the remote linux machines. Handing in your code Pair work is recommended for this project. Document your group membership using PrairieLearn's groupwork feature. Submit your files for PA3 grading here! These are the only files used for grading. Files ○ tripletree.cpp not uploaded O tripletree_private.h not uploaded Drop files here or click to upload. Only the files listed below will be accepted-others will be ignored. The combined size limit of all uploaded files is 5MB. All other files will not be used for grading. Save & Grade Unlimited attempts Save only Programming Assignment 3 Total points: Score: Question Submission status: unanswered Best submission: History: Total points: -/35 Report an error in this question Personal Notes No attached notes Attach a file Assessment overview 0/35 0% Previous question Next question Auto-graded question 4/5 Add text note 5/5/n