CSE 101 -- Prog 4

Due before midnight, Sunday, November 28, 2021.
Late submissions will not be accepted/graded.

Changelog:

Nov 27, 2021: Added sample test script and updated grading rubric

Objectives:

Implement a Binary Space Partition (BSP) ADT.

Description:

A BSP is a special type of binary tree that partitions space into two each time. This is commonly used in computer graphics to speed up rendering of complex scenes but have also been used in computer games. This program will focus on how bsp helps finding points in 2D space after partitioning. You can use the functionalities of BSP ADT from hwk4. You will add functionalities to find points (and segments) using BSP.

Details:

We will use the BSP tree you implemented in the hwk4 to find doors. Basically, a door is just a point. Your task for this program is to determine if the door is outside the room, inside the room, or on a wall. If the door is on a wall, return this wall.
If the door is on a corner or at an intersection (by a partitioning wall), return the wall that you examine first i.e. the first wall/sub-wall you find when searching the BSP tree.
If a door is on a wall that was intersected by a partition, return the corresponding sub-wall.
Unlike previous assignments, input will NOT be read in from a single input file via redirection. Instead you will have 2 input files that will be passed as arguments to the command line. These are processed via the arguments of main() You can assume that all input will be well formed, and do not need to do any error handling.
We have two input files:
- Room consists 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.
- Doors consists of a set of doors (points), with each door specified in the form: x y indicating the coordinates of door.
BONUS POINT CASE: Fancy Doors (10 points extra)
For BONUS POINT, the fancy door is a segment. They are either horizontal or vertical. It might be outside the room, inside the room, or on a wall. A room can have all fancy doors (segment) or all regular doors (point) only.
- Outside the room: as long as part of the fancy door is outside the room, including a door intersecting a wall
- Inside the room: the fancy door is totally inside the room, including the case when one endpoint of the fancy door is on the wall.
- On a wall: the fancy door is contained by a wall. Return the coordinates of this wall.
  If the fancy door spans a wall that was split by a partitioning wall, return the sub-wall that you examine first in your BSP tree.
- You do not have to worry about these 2 cases: (a) a door whose endpoints are on opposite walls of a room, and (b) a door whose endpoints are on walls but travels outside the room.
Application:
Your application will read in two files. The first one is a set of walls (no error checks needed) that represent a Room. The second file is a set of Doors. Next, the app will generate a BSP tree representation of the room and find those doors.
Example -- Base case:
The first input for the following example can be found in Room1.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 has the coordinates of the two endpoints of a wall.
The second input can be found in Door.input. The first line of the file is a flag indicating whether it's normal door or Fancy door. 0 means normal door, and 1 means fancy door. For other lines, each line indicates the coordinates of a door.
The corresponding output can be found in sample.output.
Each line indicates the position of a door. IN means the door is inside the room, OUT means the door is outside the room. If the door is on the wall, return the coordinates of two endpoints of this wall/sub-wall.
Here's the illustration.
Example -- BONUS:
Same as base case, first input is for the room. The first input for this exmaple can be found in Room2.input
The second input can be found in FancyDoor.input. The first line of the file is a flag indicating whether it's normal door or Fancy door. 0 means normal door, and 1 means fancy door. For other lines, each line indicates the coordinates of 2 endpoints of a fancy door.
The corresponding output can be found in sample2.output.
Each line indicates the position of a door. IN means the door is inside the room, OUT means the door is outside the room. If the door is ON the wall, return the coordinates of two endpoints of this wall/sub-wall.
Hint: For fancy door, as long as part of the door is outside the room, it's classified as OUT.
So, when searching for the door, you cannot directly return the wall/sub-wall when finding one endpoint of the door the first time. You have to check the other endpoint as well.
Note: both endpoints of a door must be on the same wall/sub-wall for the door to be on that wall/sub-wall.
You don't need to consider these 2 special cases:
1. one endpoint of fancydoor is on one wall, another endpoint is on another wall, and fancydoor spans the interior of the room.
2. one endpoint of fancydoor is on one wall or IN, another endpoint is on another wall or IN, but fancydoor spans outside the room.
That is, as long as one endpoint of fancydoor is IN, the fancydoor is IN. As long as one endpoint of fancydoor is OUT, the fancydoor is OUT.
Here's the illustration.
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. Same as your hwk4.
- BSP.h: Function headers for your BSP implementation. You should not have to modify this file.
- Wall.c: Helper functions for the application. Same as your hwk4.
- 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.
Rooms: room3.input, Doors: door3.input, Output: sample3.output Image: sample3.png
Rooms: room4.input, Doors: door4.input, Output: sample4.output Image: sample4.png
You should be able to verify your program works correctly by running ./prog4 Room.input Doors.input and comparing it to the expected output.

Resources:

Wikipedia

Sample Testing Script:

You can find the testing script along with instructions here: providedTests
NOTE: Getting the correct output on the provided inputs does not guarantee full credit on the assignment. There may additional edge cases that you will have to consider. Additionally, note that tests 6 and 7 are for fancy doors, you are not required to support this type of input. If you choose to handle fancy doors, you can only earn up to 10 bonus points!

Grading:

Rubric:

You begin with 100 points.
You lose credit for incorrect results, poorly documented or formatted code,
or for not following instructions.

Below is a partial list:

- up to 10 points off for not following instructions
- up to 10 points off for special handling to grade your homework (usually
  because you did not check that it runs on the computers in the timeshare first).
- 80 points - Program tests for your prog4 implementation using normal door input 
  (partial credit available for partially correct output)
- 20 points - Code readability and commenting
- Up to 10 bonus points for properly handling fancy door input!

Make sure you:
a.  include the Makefile, .c files, and .h file
b.  generate an executable file called prog4 with your Makefile
c.  have confirmed that it compiles and runs properly on unix.ucsc.edu
d.  followed the general instructions described in overview.html

Who graded your assignment based on your CRUZID first letter :
```
nathan: a*  - ju*
bryan: 	jw* - z*
```

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 prog4 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 prog4 prog4.zip
You can submit as often as you want up until the deadline. We will only look at your most recent submission.