Objectives:

Description:

Details:

• We will use the BSP to represent a single room. However, the room can be pretty complex e.g. can be like a maze. There is a long list of simplifying assumptions below to make this manageable though. Your task for this homework is to generate the BSP representation of the room, and to print out the walls (in the specified order below) of the room. You will also be provided with code that will provide a visual representation of the room.
• Just as with previous assignments, input will be from stdin and output will be to stdout. You can assume that all input will be well formed, and do not need to do any error handling. The input consist of a series of walls, with each wall specified in the form:
  x1 y1 x2 y2
  indicating the coordinates of the start and end points of a wall.
• All the walls are connected end-to-end with the last wall connecting back to the first wall of the first room. Walls do not cross each other. There will be a minimum of 4 walls to a room, but a room can have an arbitrarily large number of walls. A room could like more like a maze of corridors. But these corridors do not form loops i.e. rooms do not contain "courtyards" (like an O-shaped or 8-shaped room). Walls can only be horizontal or vertical. Coordinates are integer values.
• BSP Tree:
  Each node in a BSP tree is a wall. Internal nodes are partitioning walls. A BSP tree representation of a room can be constructed using the following procedure. Initially, all the walls are kept in a list. Assume that the walls in the list are in the same order as the input list.
  • Select a wall to partition the room into 2 sets. The partitioning wall should be the middle element of the list. That is, the wall at the position floor( numwalls/2 ).
    e.g. If the wall in the list is A,B,C, then we should pick the wall A which is the floor( 3/2 ) = 1 wall in the list.
  • The partitioning wall becomes a node in your BSP tree. The rest of the walls become part of the left and right subtrees of this node. Additional walls may be introduced if the partitioning wall divides a wall in two (see illustration in example below).
  • Recursively partition both subtrees until there is just one wall or no wall in subtree.
• Left vs Right subtrees:
  If a wall is above or to the left of the partitioning wall, then that wall becomes part of the left subtree.
  If a wall is below or to the right of the partitioning wall, then that wall becomes part of the right subtree.
  e.g. a wall being above the partitioning wall means that Wall->y <= PartitionSeg->y. Since we are using cairo and for cairo y increases downward

  The walls in the subtrees should be in the same order as before the split.

  If a wall is aligned (co-linear) with the partitioning wall, classify that wall as above or left i.e. place it in the left subtree.

• Splitting a wall:
  A horizontal partitioning wall can split vertical walls into two pieces if the y-component is between the y-components of a vertical wall. For example, a vertical wall (x y1 x y2) is split into two vertical walls: (x y1 x y) and (x y2 x y) where x is the x-component of the vertical wall, and y is the y-component of the partitioning wall.

  Likewise, a vertical partitioning wall can split horizontal walls into two pieces if the x-component is between the x-components of a horizontal wall.

  The two pieces of a wall that has been split end up on the left and right subtrees of the partitioning wall.

• Application:
  Your application will read in a set of walls (no error checks needed) that represent a room. Next, the app will generate a BSP tree representation of the room and verify using both a textual printout (see PrintBSP in BSP.h) and a graphical output (see in DrawBSP in BSP.h).
• Example:
  The input for the following example can be found in sample.input. The first line of the file will hold a string to use for the name of the output file. For other lines, each line indicate the coordinates of two endpoints of a wall.
  The corresponding output can be found in in sample.output.
  Note that the two endpoints of a wall can be written in any order. e.g. 50 50 50 100 and 50 100 50 50 denote the same wall, and both are accepted.
  Here's the illustration of how the room is partitioned and converted into a BSP tree.
• Files for this program:
  The following files are provided to you, and should all be submitted with your work.
  • Makefile: default Makefile.
  • room.c: This is where you would implement the application code.
  • BSP.c: Your implementation of the BSP ADT goes here.
    
  • BSP.h: Function headers for your BSP implementation. You should not have to modify this file.
    
  • Wall.c: Helper functions for the application. You will need to add to this file
    
  • Wall.h: Header file for the helper function file. You should not have to modify this file.
    
  • List.c: A working implementation of a List ADT. You should not have to edit this file, it is used by room.c.
    
  • List.h: Header file for the provided list implementation. You should not have to modify this file.
• The following files are provided for the purposes of testing your application. You should be able to verify your program works correctly by running `./hwk4 < input1.txt` and comparing it to the expected output.
  • Input: input1.txt Expected output: sampleOutput1.txt Image: output1.png
  • Input: input2.txt Expected output: sampleOutput2.txt Input: output2.png
  Note: coordinates here are consistent with the coordinate system of cairo, which means y-axis is downwards.

Resources:

• Wikipedia

Submission:

• Make sure that you've compiled and tested your code on the campus unix timeshare before submitting. On the unix timeshare, put materials in a folder named hwk4 and zip it up. Note that you should not include any sample input or sample output files in your submission.

  Submit on unix timeshare. Use the command: submit cse101-ap.f21 hwk4 hwk4.zip

  You can submit as often as you want up until the deadline. We will only look at your most recent submission.

Last modified: 11/13/2021