[SOLVED] algorithm assembly graph COMP2401 Assignment #4

COMP2401 Assignment #4
(Due: Mon. Mar 11, 2019 @ 12 noon)
In this assignment, you will gain practice dynamically allocating/freeing memory as well as working with pointers to allocated structures. You will also use a makefile to compile the code. You will also get to see an algorithm for tracing borders in an image as well as implement a simple algorithm to simplify a polygon.
Imagine an assembly line with moving parts in which a robot arm must select and pick up a particular part. Assume first that it needs to identify the part from a camera image as the parts move by. We will write a program that processes a simple binary grid image by determining border points of parts in the image and then computing a
polygon that represents its general shape.
We will assume that none of the pars are touching one another and that all parts are completely contained in the image so that no part is touching the outer border of the image as shown in the image here:
In this assignment, you must download the following files:
boundaries.c the program that you will edit
polygonDisplay.c functions for displaying (code completed)
polygonDisplay.h external function call definitions
polygonSet.h struct definitions for vertices, polygons and polygon sets.
Follow the steps below to complete the assignment.
(1) Write a makefile that compiles and links the boundaries.c file into an executable called boundaries. You can use a makefile from the course notes as a template. The makefile should allow make all and make clean commands to work properly. You will need to include the -lX11 library in order for the code to link properly, since we will be using some windows with graphics (described later on in the course).
(2) Once the code compiles and produces an executable. Run it. You should see window like this appearing:
When you press the ENTER key in the terminal window, you will see the border of the parts of the image turn white. That is because the algorithm for computing the border points has already been completed for you. Pressing the ENTER key three more times will move you onto a second image. There are 5 images in total. You can iterate through all of them. At this point, the code should compile and run properly. Do not continue until this works. The remainder of the assignment requires you to modify the boundaries.c file ONLY.

(3) Examine the structs defined in polygonSet.h. Make sure that you understand how they fit together. A Polygon contains vertices where each Vertex links to the next vertex along the polygon boundary. The polygon keeps track of the very first vertex, as well as the last one that was added (as it is being constructed). The polygon also keeps a pointer to the next polygon in the PolygonSet. Lastly, a PolygonSet just maintains a first and last polygon.
You need to adjust the code in the computeBoundaries() function so that it dynamically creates a polygon p each time that it finds a part in the image to start tracing. As seen in the code, this is when it finds a 1 pixel with a 0 to its left. This point, at location [y][x] in the grid, will become the first vertex of the polygon, and it is marked as a 2 in the grid. Note that the grid is arranged as [row][column] that is why the code uses grid[y][x] as opposed to grid [x][y]. The traceWholeBorder() function will require that newly-created polygon p, and it will then trace out the remainder of the parts boundary while adding
vertices to this polygon as it goes. Once the traceWholeBorder() function completes, the polygon should be completed. So, you will need to add this polygon to the polygon set pSet. Make sure to handle the special case where this is the first polygon in the set.
You will also need to go into the traceWholeBorder() function to make sure that you are adding dynamically-allocated vertices to the polygon as each border point in the grid is found (identified by a 2 being placed there).
When this part has been completed, when you run your code, you should see the polygon shown as a connected set of red dots after the second press of ENTER for each of the 5 grids. It should look like what is shown here:
(4) Complete the freePolygonSet() procedure so that it frees up ALL of the memory that you allocated from creating your polygon set. That is, it should free up all the polygons and vertices added but it should NOT free the allocated memory that represents the PolygonSet itself, as you will use this repeatedly for the other 4 grids.
(5) Complete the cleanUpPolygons() function so that it takes the inputSet of polygons and produces an outputSet of polygons. Note that these polygon sets are already allocated in memory, so you should not allocate these. The function should iterate through the inputSet one polygon at a time. It should then attempt to simplify each
polygon by removing vertices that are not required to define the polygon. That is, whenever there are three or more vertices in sequence that share the same x value of share the same y value, then only the two end vertices of that sequence need to be kept.
For example, here is an image that shows an input polygon and its

corresponding output polygon. Your code must create brand new polygons and add them to the output set. As a result, when the code runs, after you press the ENTER key the third time for each grid, you will see the updated polygon set. Below is what you should see for the first grid:
(6) To make sure that your allocated memory has been freed properly, use valgrind when you run your final version:
valgrind leak-check=yes ./boundaries
You should see something like this (process ID will vary) appear at the end of the output:
==3960== HEAP SUMMARY:
==3960==
==3960==
==3960==
==3960==
in use at exit: 0 bytes in 0 blocks
total heap usage: 1,651 allocs, 1,651 frees, 80,016 bytes allocated
All heap blocks were freed no leaks are possible
________________________________________________________________________________
IMPORTANT SUBMISSION INSTRUCTIONS:
Submit all of your c source code files as a single tar file containing:
1. A Readme text file containing
your name and studentNumber
a list of source files submitted
any specific instructions for compiling and/or running your code
2. All of your .c source files and all other files needed for testing/running your programs.
3. Any output files required, if there are any.
The code MUST compile and run on the course VM, which is COMP2404B-W19.
If your internet connection at home is down or does not work, we will not accept this as a reason for handing in an assignment late so make sure to submit the assignment WELL BEFORE it is due !

You WILL lose marks on this assignment if any of your files are missing. So, make sure that you hand in the correct files and version of your assignment. You will also lose marks if your code is not written neatly with proper indentation and containing a reasonable number of comments. See course notes for examples of what is proper indentation, writing style and reasonable commenting).
________________________________________________________________________________