Lab 4

All problems are to be done using DrRacket. You should be using typed racket, meaning that the first line of your definitions window should be #lang typed/racket. A note on style: your lines of code should not exceed 80 characters in width. See the text for numerous examples of proper indentation and code formatting. Also, note that striking the tab key will move a line of code to its canonical position.

Lab 4 will be collected from your subversion repository on Thursday, July 13 at noon.

You will need to require the following library to work with images in Typed Racket:

(require typed/test-engine/racket-tests)
(require "../include/uchicago151.rkt")
(require typed/2htdp/image)

Binary Space Partitioning Tree

A binary space partitioning tree is a tree used to divide up a space (in our case a 2-dimensional space). Every internal node represents a division of the space in half, either vertically or horizontally.

Write a function show-tree which takes a binary space partitioning tree as input and produces an image of that tree. The show-tree function will also take two Nonnegative-Reals as input, whcih are the width and height of the image to be produced. Use the following definition of a binary space partitioning tree:

(define-struct Rect
  ([color : Image-Color]))
(define-struct Split
  ([dir : (U 'x 'y)]
   [sub1 : BSPT]
   [sub2 : BSPT]))

(define-type BSPT (U Rect Split))

Use the following examples as a guide:

(define t1 (Split 'x (Rect 'red) (Rect 'blue)))
(show-tree t1 300 300)

(define t2 (Split 'x (Split 'x (Rect 'green) (Rect 'red)) (Rect 'blue)))
(show-tree t2 300 300)

(define t3 (Split 'x (Split 'x (Split 'y (Rect 'yellow) (Rect 'orange)) (Rect 'red)) (Rect 'blue)))
(show-tree t3 300 300)