Language is C. Please read instructions carefully, let me know if any questions/clarification. Thank you.

#include "imgUtils.c"

/** * This is the structure we are going to use to store each individual node of * the BST. Remember that each Quad corresponds to a rectangular area on the * image: * * (tx,ty) w * x------------------------- * | | * | | * | | * | | * h | Quad | * | key = tx+(ty*sx) | * | | * | | * | | * | | * -------------------------x * (tx + w, ty + h) * */ typedef struct quad { int tx, ty; // The (x,y) coordinates of the top-left pixel in the quad int w; // How many pixels wide the quad is int h; // How many pixels high the quad is

int sx; // Width of the original image, this is needed for the key. // This *MUST* be the same for all nodes in the BST

int key; // A unique identifier (remember we discussed BST nodes // should have unique keys to identify each node). The // key identifier here will be created as: // key = tx + (ty * sx) // This means that only one quad can start at a specific // pixel.

int wsplit; // 1 if this quad is supposed to be split along the width // 0 if this quad is supposed to be split along the height

/** * TODO: Complete the definition of the Quad struct */

} Quad;

NOTE: For the remaining functions, you may assume the following: // // (1) All the Quads are valid (None of them go outside the image) // // (2) They don't overlap (A pixel will not be in multiple Quads)

int get_colour(Image *im, Quad *q) { /** * Given an image 'im' and a Quad 'q', get the colour we should be assigning * to the pixels that are in it, and return it. For the sake of this * assignment, we will say this is *average* colour of all the pixels in * the quad. * * The pixel data is stored in a one dimensional array called 'data' in the * image struct. Make sure you look at the definition of this to understand * how the image is stored. Remember that the pixel data is stored in * row-major order, so to get the colour for pixel (x,y) you will look at the * index * * x + (y * sx) * * of the array. * * TODO: Implement this function. You should not be getting any values * outside the range of the pixels [0-255] if you have implemented * this correctly. */

return 0; }

int similar(Image *im, Quad *q, int threshold) { /** * Given an image 'im', check if the colours in the area corresponding to the * Quad 'q' are all similar. If not, we will have to split it. For the * purpose of this assigment, we say the colours in a Quad are similar if * * maxCol - minCol <= threshold * * where maxCol and minCol are the maximum and minimum values respectively * of the pixel colours in the Quad. The threshold is a parameter. This * function should return a 0 if the pixels are not similar enough and the * Quad needs to be split, and 1 otherwise. * * TODO: Implement this function */

return 0; } Quad *split_tree(Image *im, Quad *root, int threshold) { /** * This function traverses the BST, and for each existing Quad, checks if * the pixels in the quad are of a similarcolour using the similar() function * and the given threshold. If they are not, then the Quad needs to be split * into 2 Quads(which will hopefully have pixels that are more similar to * each other). * * To do this, first we need to decide in which direction we are going to * split the Quad. For this, we will use the 'wsplit'field. * * - If wsplit = 1, then we split it along the width (ie, we will now have * 2 quads with the same heightand half the width as the * original one) * * - If wsplit = 0, then we split along the height. * * NOTE: We don't always want to split the Quads in the same direction * every time this function is called, because then we could just * end up with very thin and long/tall quads, which wouldn't be very * helpful to what we are trying to do. So, we need to make sure that * once we split a Quad, that we invert the value of the 'wsplit' * variable in both the new nodes, so they split the other way. * * ------------------------------------------------------------------------- * * For example, if our Quad had the following values: * (tx:ty = 0:0 w = 512, h = 512, wsplit = 1) ---> A * * (0,0) * x------------------------- * | | * | | * | | * | | * | A | * | | * | | * | | * | | * | | * -------------------------x * (512, 512) * * * this pixel is not IN the image, just * represents the 'corner'. The bottom * right pixel, as always, is (511,511) * * it would be split along the width, and the resulting two Quads * we would get would be as follows: * * (tx:ty = 0 :0 w = 256, h = 512, wsplit = 0) ---> B * (tx:ty = 256:0 w = 256, h = 512, wsplit = 0) ---> C * * * (0,0) (256, 0) * x-----------x------------- * | | | * | | | * | | | * | | | * | B | C | * | | | * | | | * | | | * | | | * | | | * -------------------------x * (512, 512) * * - Note that we want to always split it in exactly half, but if the * width/height is an odd number then round down. * * - Further note that 'wsplit' on both of these has now been set to 0. * If they were split again, the resulting Quads would have wsplit = 1. * * -------------------------------------------------------------------------- * * Now, once you know how it needs to be split, carefully form these two * Quads, with the correct positions and sizes, and replace the the original * one with them. * * This function is crunchy - and if you don't think it through before you * start implementing it you'll run into all kinds of trouble. * * It's up to you how to solve this, and if you want an opinion, you can * come to visit us during office hours! The included file `point.pgm` is * a good candidate image to test this function on. * * Expected result: The BST will have at most twice as many Quads * as before, depending on how many of them needed to be * split. * * TODO: Implement this function */

return NULL;

}