Implement methods for a quadtree representation of bitmap images in Python

Our representation of quadtrees will not have a separate Node class. Instead, a QuadtreeBitmap itself can be thought of as a node. A QuadtreeBitmap is either a leaf, in which case it represents a square region of pixels all of the same colour; or an internal node, in which case it has four child QuadtreeBitmaps, one per quadrant of the bitmap image.

You may implement your submission in either Java or Python. The only file which you need to edit is QuadtreeBitmap.java or quadtree_bitmap.py, which contains a class QuadtreeBitmap, which contains the methods you need to implement:

blackenNorthWestQuadrant() : blacken the entire north-west quadrant.

countPixels(Colour) : count pixels of a given colour in the bitmap represented by the quadtree.

invertColours() : invert the colours in the bitmap represented by the quadtree, i.e. turn every black pixel white and every white pixel black.

setPixel(int x, int y, Colour) : change the colour of a single pixel in the bitmap represented by the quadtree, to the specified colour.

computeOverlay(QuadtreeBitmap bmp1, QuadtreeBitmap bmp2) : construct and return the overlay of the two input images of the same size. In the overlay a pixel is black if either of the input images has a black pixel in the same location. That is, a pixel in the output image is white only when the corresponding pixel in both input images is white, otherwise the output pixel is black. Rather than do the operation pixel by pixel, one can compute the overlay more efficiently by leveraging the quadtree's ability to represent multiple pixels with a single node.

Note: for full marks, the resulting quadtree needs to be in "reduced" form, i.e. any subtree that is entirely one colour needs to be reduced to a single leaf.

Empty method definitions have been provided in the QuadtreeBitmap class for each of the methods you need to implement. They start from line 115 of the Java scaffold, and from line 90 of the Python scaffold.

We have provided a scaffold which includes many helpful things, such as:

A method which constructs a QuadtreeBitmap from a string representation. See below for details on the string representation format expected.

A method which converts a QuadtreeBitmap into a string representation.

Various constructors which you might find helpful, e.g.

A constructor which creates a leaf QuadtreeBitmap for a given location and size.

A constructor which creates a QuadtreeBitmap for a given location and size, with quadrants given by a list of QuadtreeBitmaps provided as an argument.

Convenience methods, e.g.

A method which enumerates quadrants in the following order: northeast, northwest, southeast, southwest.

A method which determines which quadrant an input (x, y) coordinate pair lies within. (If any.)

A convenience method which you may enable, which reads a string representation of a bitmap from standard input and constructs the corresponding QuadtreeBitmap.

Methods which generate string representations of a QuadtreeBitmap, both as a string representation of the bitmap it encodes, and with boxing interspersed to depict its tree structure.

A main method, which will not be tested, has also been provided and may be used by you for experimentation/testing: it's at line 178 of the Java scaffold and at the top of the Python scaffold. If you run the scaffold code in its initial state, you will be asked to enter a string representing a bitmap. Try entering the example from the sheet:

Text

........

.....***

...***..

..**....

..*.....

.**...**

**...***

*....***

We advise against changing the other methods provided in the scaffold. You are allowed to write additional methods, classes, etc., and add additional source files to your assignment workspace as you see fit, though take note of the University's plagiarism policy.

Given code:

import sys from core import Colour from core import is_texture

def main(): # This is here for you to optionally use for your own testing / running. # This function will NOT be tested. Feel free to experment here. print("Enter a string representation for a bitmap, followed by EOF or \"end\".") input_bmp = read_bmp_from_stream(sys.stdin) # print(input_bmp) print(input_bmp.to_tree_string())

# convenience function for constructing quadtrees from string representations of # bitmaps from stdin def read_bmp_from_stream(stream): lines = [] for line in stream: line = line.rstrip(" ") if line == "end": break else: lines.append(line) return quadtree_bitmap_from_string(" ".join(lines))

class QuadtreeBitmap: def __init__(self, size, colour = Colour.WHITE): """Constructs a quadtree bitmap with height and width equal to the specified size, and every pixel initialized to the given colour. The specified size must be a power of 2, and must be greater than zero. If no colour is specified, default colour is white.""" # only supporting power-of-2 dimensions if not _power_of_two(size): raise ValueError("Size not power of 2.") self._x = 0 self._y = 0 self._size = size self._leaf = True self._colour = colour self._north_west = None self._north_east = None self._south_west = None self._south_east = None # specifying location only supported internally @classmethod def _construct_at_location(cls, x, y, size, colour): bmp = QuadtreeBitmap(size, colour) bmp._x = x bmp._y = y return bmp # combining quads to form tree only supported internally, assumes well-positioned @classmethod def _construct_from_quadrants(cls, x, y, size, quads): bmp = QuadtreeBitmap._construct_at_location(x, y, size, Colour.WHITE) bmp._north_west = quads[0] bmp._north_east = quads[1] bmp._south_west = quads[2] bmp._south_east = quads[3] bmp._leaf = False return bmp # for any basic task which needs to be repeated all four quadrants def _quadrants(self): return [ self._north_west, self._north_east, self._south_west, self._south_east ] # retrieves the quadrant within which the specified location lies def _quadrant_of(self, x, y): for quad in self._quadrants(): if quad.contains_point(x, y): return quad return None def contains_point(self, x, y): """Returns True of this QuadtreeBitmap contains the location specified by the input coordinates.""" return self._x <= x \ and self._y <= y \ and x < self._x + self._size \ and y < self._y + self._size def get_size(self): """Returns the height and width of this quadtree bitmap.""" return self._size ######################################################################### ## Assignment questions from here on in ######################################################################### def blacken_north_west_quadrant(self): """Sets the colour of every pixel in the north-west quadrant of this quadtree bitmap to black.""" self._north_west.colour=black pass def count_pixels(self, colour): """Counts the number of pixels of the given colour in the bitmap represented by this quadtree.""" if self._leaf and self._colour==colour: return (self._size)**2 elif self._leaf and self._colour!=colour: return 0 else: total=0 total= total+self._north_west.count_pixels(colour) total= total+ self._north_east.count_pixels(colour) total= total+ self._south_west.count_pixels(colour) total= total+ self._south_east.count_pixels(colour) return total

def invert_colours(self): """Inverts the colours in the bitmap represented by this quadtree, i.e. turns every black pixel white and every white pixel black.""" # TODO: implement this pass def set_pixel(self, x, y, colour): """Sets the colour of a single pixel at the specified location to the given colour.""" # TODO: implement this pass @classmethod def compute_overlay(cls, bmp1, bmp2): """Constructs and returns the overlay of the two given quadtree bitmaps. The overlay of two bitmaps is the bitmap which has a black pixel at every location at which either input bitmap has a black pixel, and a white pixel at every location at which both input bitmaps have a black pixel. Can be thought of as the bitwise or of two bitmaps.""" # TODO: implement this return None ########################################################### ## End of assignment questions ########################################################### ########################################################### ## You do not need to concern yourself with the code beyond this point ########################################################### def to_tree_string(self): """Returns a string representation of the tree structure of this quadtree bitmap. The string representation is similar to the representation returned by __repr__, but with boxing interspersed to indicate the boundaries of the regions represented by leaf nodes in the quadtree.""" canvas = [[" "]*(2*self._size + 1) for _ in range(2*self._size + 1)] self._print_tree_to_canvas(canvas, 2*self._x, 2*self._y) rows = [] for row in canvas: rows.append("".join(row)) return " ".join(rows)

def _print_tree_to_canvas(self, canvas, x_offset, y_offset): CORNER = '+' ; V_WALL = '|' ;H_WALL = '-' ; FILLER = ' ' if self._leaf: # top left is 2x - x_offset, 2y - y_offset canvas[2*self._y - y_offset][2*self._x - x_offset] = CORNER # top right canvas[2*self._y - y_offset][2*self._x + 2*self._size - x_offset] = CORNER # bottom left canvas[2*self._y + 2*self._size - y_offset][2*self._x - x_offset] = CORNER # bottom right canvas[2*self._y + 2*self._size - y_offset][2*self._x + 2*self._size - x_offset] = CORNER # top for i in range(2*self._x + 1,2*self._x + 2*self._size): if canvas[2*self._y - y_offset][i - x_offset] != CORNER: canvas[2*self._y - y_offset][i - x_offset] = H_WALL # left for i in range(2*self._y + 1, 2*self._y + 2*self._size): if canvas[i - y_offset][2*self._x - x_offset] != CORNER: canvas[i - y_offset][2*self._x - x_offset] = V_WALL # bottom for i in range(2*self._x + 1, 2*self._x + 2*self._size): if canvas[2*self._y + 2*self._size - y_offset][i - x_offset] != CORNER: canvas[2*self._y + 2*self._size - y_offset][i - x_offset] = H_WALL # right for i in range(2*self._y + 1, 2*self._y + 2*self._size): if canvas[i - y_offset][2*self._x + 2*self._size - x_offset] != CORNER: canvas[i - y_offset][2*self._x + 2*self._size - x_offset] = V_WALL # fill every even spot in interior for i in range(2*self._y + 1, 2*self._y + 2*self._size, 2): for j in range(2*self._x + 1, 2*self._x + 2*self._size, 2): canvas[i - y_offset][j - x_offset] = self._colour.get_texture() else: for quad in self._quadrants(): quad._print_tree_to_canvas(canvas, x_offset, y_offset) def __repr__(self): """Returns a string representation of this bitmap. The string representation consists of a newline-separated sequence of rows, where each row consists of a sequence of characters which each encode the colour of a pixel. For a string representation which depicts the quadtree structure of this bitmap, see to_tree_string.""" canvas = [[Colour.WHITE.get_texture()]*self._size for _ in range(self._size)] self._print_to_canvas(canvas, self._x, self._y) rows = [] for row in canvas: rows.append("".join(row)) return " ".join(rows)

def _print_to_canvas(self, canvas, x_offset, y_offset): if self._leaf: for i in range(self._y, self._y + self._size): for j in range(self._x, self._x + self._size): canvas[i - y_offset][j - x_offset] = self._colour.get_texture() else: for quad in self._quadrants(): quad._print_to_canvas(canvas, x_offset, y_offset)

def quadtree_bitmap_from_string(bmp_string): """Constructs a quadtree from the bitmap represented by the input string. Fails with a ValueError if the input string does not properly encode a valid bitmap.""" _validate_bmp_string(bmp_string) return _from_row_strings(0, 0, bmp_string.splitlines())

# recursive helper method for fromString def _from_row_strings(x, y, rows): size = len(rows) if not any(Colour.BLACK.get_texture() in row for row in rows): # all white return QuadtreeBitmap._construct_at_location(x, y, size, Colour.WHITE) elif not any(Colour.WHITE.get_texture() in row for row in rows): # all black return QuadtreeBitmap._construct_at_location(x, y, size, Colour.BLACK) else: x_mid = x + size//2 y_mid = y + size//2 # split rows into quadrants nw_rows = _quad_row_strings(0, 0, rows) ne_rows = _quad_row_strings(size//2, 0, rows) sw_rows = _quad_row_strings(0, size//2, rows) se_rows = _quad_row_strings(size//2, size//2, rows) # build each subtree north_west = _from_row_strings(x, y, nw_rows) north_east = _from_row_strings(x_mid, y, ne_rows) south_west = _from_row_strings(x, y_mid, sw_rows) south_east = _from_row_strings(x_mid, y_mid, se_rows) # combine quads = [ north_west, north_east, south_west, south_east ] return QuadtreeBitmap._construct_from_quadrants(x, y, size, quads)

# extracts row strings for quadrant from row strings for bitmap def _quad_row_strings(x_rel, y_rel, rows): size = len(rows) # sublist selects rows, substring selects columns return list(map(lambda row: row[x_rel:x_rel + size//2], rows[y_rel:y_rel + size//2]))

# does nothing if input valid, communicates invalidity via errors def _validate_bmp_string(bmp_string): rows = bmp_string.splitlines() if len(rows) == 0: raise ValueError("Empty bitmap string.") elif not _power_of_two(len(rows)): raise ValueError("Number of rows not a power of 2.") elif not _power_of_two(len(rows[0])): raise ValueError("Row width not a power of 2.") else: # using first row to determine row width width = len(rows[0]) for i in range(1, len(rows)): if len(rows[i]) != width: raise ValueError("Row " + str(i) + " not same width as other rows.") for row in rows: if not all(is_texture(c) for c in list(row)): ic = next(filter(lambda c : not is_texture(c), list(row))) raise ValueError("Illegal character detected: '" + ic + "'") if len(rows) != width: raise ValueError("Number of rows not equal to row width.")

def _power_of_two(n): x = 1 while x < n: x *= 2 if x == n: return True else: return False

if __name__ == "__main__": main()