polygonDisplay.c #include  #include  #include  #include "polygonSet.h" #define SCALE 25 XPoint pVertices[500]; //This is a fixed array that will hold the polygon vertices to be displayed. XArc pPoints[500]; //This is a fixed array that will hold the polygon vertices to be displayed. // These are display-related variables Display *display; Window win; GC gc; // Draw the polygon set on the window. This code assumes a maximum of 500 points per polygon void drawGrid(char grid[30][30]) { // First erase background XSetForeground(display, gc, 0xFFFFFF); XFillRectangle(display, win, gc, 0, 0, 750, 750); XFlush(display); // Draw the grid for (int y=0; yfirstPolygon; int numVertices; // Draw the grid for (int y=0; yfirstVertex; while (v != NULL) { pVertices[numVertices].x = v->x*SCALE + SCALE/2; pVertices[numVertices].y = v->y*SCALE + SCALE/2; pPoints[numVertices].x = v->x*SCALE-SCALE/4 + SCALE/2; pPoints[numVertices].y = v->y*SCALE-SCALE/4 + SCALE/2; pPoints[numVertices].width = 10; pPoints[numVertices].height = 10; pPoints[numVertices].angle1 = 0; pPoints[numVertices].angle2 = 360*64; v = v->next; numVertices++; } if (numVertices > 2) { XSetForeground(display, gc, 0x000000); XDrawLines(display, win, gc, pVertices, numVertices, CoordModeOrigin); XFlush(display); XSetForeground(display, gc, 0xFF0000); XFillArcs(display, win, gc, pPoints, numVertices); XFlush(display); } poly = poly->next; } getchar(); } int openDisplayWindow() { // Opens connection to X server display = XOpenDisplay(NULL); // Create a simple window win = XCreateSimpleWindow(display, // our connection to server RootWindow(display, 0), // parent window (none in this example) 0, 0, // x,y (w.r.t. parent ... ignored here) 750,750, // width, height 0, // border width 0x000000, // border color (ignored in this example) 0xFFFFFF); // background color = WHITE // Set the name of the window XStoreName(display, win, "Polygon Displayer"); // Get the graphics context gc = XCreateGC(display, win, 0, NULL); // Make it visible XMapWindow(display, win); XFlush(display); usleep(20000); // sleep for 20 milliseconds. } int closeDisplayWindow() { // Clean up and close the window XFreeGC(display, gc); XUnmapWindow(display, win); XDestroyWindow(display, win); XCloseDisplay(display); } 

polygonDisplay.h

#include  // Draw the polygon set on the window. extern void drawGrid(char grid[30][30]); // Draw the polygon set on the window. extern void drawPolygonSet(char grid[30][30], PolygonSet *pSet); // Open a display window extern int openDisplayWindow(); // Close a display window extern int closeDisplayWindow(); 

polygonSet.h

// This struct represents a single vertex of a polygon typedef struct vert { int x; int y; struct vert *next; } Vertex; // This struct represents a polygon composed of a chain of several vertices typedef struct poly { Vertex *firstVertex; Vertex *lastVertex; struct poly *next; } Polygon; // This struct represents a sequence of polygons typedef struct { Polygon *firstPolygon; Polygon *lastPolygon; } PolygonSet; 

boundaries.c

#include  #include  #include "polygonSet.h" #include "polygonDisplay.h" #define WIDTH 30 #define HEIGHT 30 // Trace out a single boundary from the grid, starting at the given (xs,ys) location. Mark the boundary // locations with a 2 in the grid. Assume that the polygon p has been created and has a single vertex at // location (xs, ys). The procedure will complete the polygon by adding the remaining boundary points it // finds in sequence. void traceWholeBorder(char grid[HEIGHT][WIDTH], int xs, int ys, Polygon *p) { int xOffset[8] = {1, 1, 0, -1, -1, -1, 0, 1}; int yOffset[8] = {0, 1, 1, 1, 0, -1, -1, -1}; int xc = xs, yc = ys; // The current point is the start point int d = 7; char notDone = 1; while(notDone) { int dp; if (d%2 == 0) dp = (d+7)%8; else dp = (d+6)%8; int i; for (i=0; ifirstPolygon = NULL; pSet->lastPolygon = NULL; } // This is where it all begins int main() { // Allocate a PolygonSet to store the original traced border points PolygonSet *initPolygons = malloc(sizeof(PolygonSet)); initPolygons->firstPolygon = NULL; initPolygons->lastPolygon = NULL; // Allocate a PolygonSet to store the simplified/processed polygons PolygonSet *finalPolygons = malloc(sizeof(PolygonSet)); finalPolygons->firstPolygon = NULL; finalPolygons->lastPolygon = NULL; char grids[5][HEIGHT][WIDTH] = { {"000000000000000000000000000000", "000111111111111111111111110000", "000111111111111111111111110000", "000111111110000000111111110000", "000111111110000000111111110000", "000111111110000000111111110000", "000111111110000000111111110000", "000111111110000000111111110000", "000111111110000000111111110000", "000111111111111111111111110000", "000111111111111111111111110000", "000011111111111111111111100000", "000001111111111111111111000000", "000000111111111111111110000000", "000000011111111111111100000000", "000000001111111111111000000000", "000000000000111110000000000000", "000000000000111110000000000000", "000000000000111110000000000000", "001111111111111111111111111100", "001111111111111111111111111100", "001111111111000000111111111100", "001111111111000000111111111100", "001111111111000000111111111100", "001111111111000000111111111100", "000011111000000000000111000000", "000011111000000000000111000000", "000011111000000000000111000000", "000000000000000000000000000000", "000000000000000000000000000000"}, {"000000000000000000000000000000", "000000000000000000000000000000", "000000000111111000000000000000", "000000011111111111110000000000", "000001111111111000000000110000", "000001111111000000000001110000", "000001111111000000000000111000", "000000011111000000000000000000", "000000011111111000000000000000", "000000000111111110000000000000", "000000111111111111111100000000", "000111111111111111111111000000", "001111111111111111111000000000", "000111111100011111111110000000", "011111100000111111111000000000", "001111110000000011111111000000", "001111110000000011111100000000", "000011110000000111111000000000", "000001110000000111000000000000", "000000010000000110000000000000", "000000000000000000000000110000", "000000000000000000000000000000", "000000011111111110000000000000", "001000000011111111110000001000", "001000000000011111111000000000", "001000000000001111111100000000", "001000000001111110000000001000", "001111000000011110000000011000", "000000000000000110000000000000", "000000000000000000000000000000"}, {"000000000000000000000000000000", "001110001110000110001000100100", "001110001110000110001000100000", "001110001110000110001000000000", "000000000000000000000000000000", "001111111111111111111111111100", "000000000000000000000000000000", "000000000000000000000000000000", "000000011111111111111100000000", "000000010101010101010100000000", "000000010101010101010100000000", "000000010101010101010100000000", "000000000000000000000000000000", "000000100000000000000010000000", "000000010000011100000100000000", "000000001000001000001000000000", "000000000100001000010000000000", "000000000010000000100000000000", "000000000001000001000000000000", "000000000000100010000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000001111111111111111111100000", "000001111110000000000000000000", "000000111111111100000000000000", "000000001111111111110000000000", "000000000001111111111110000000", "000000000000000111111111100000", "000000000000000000001111110000", "000000000000000000000000000000"}, {"000000000000000000000000000000", "001111111111111111111111111100", "001111111111111111111111111100", "001111111111111111111111111100", "001110000000000000000000000000", "001110111111111111111111111110", "001110111111111111111111111110", "001110111111111111111111111110", "001110111000000000000000001110", "001110111011111111111111101110", "001110111011111111111111101110", "001110111011111111111111101110", "001110111011100000000011101110", "001110111011101111111011101110", "001110111011101111111011101110", "001110111011101111111011101110", "001110111011101110111011101110", "001110111011100000111011101110", "001110111011111111111011101110", "001110111011111111111011101110", "001110111011111111111011101110", "001110111000000000000011101110", "001110111111111111111111101110", "001110111111111111111111101110", "001110111111111111111111101110", "001110000000000000000000001110", "001111111111111111111111111110", "001111111111111111111111111110", "001111111111111111111111111110", "000000000000000000000000000000"}, {"000000000000000000000000000000", "000001100000000000000000111000", "000011110000000000000011110000", "000111111000000000011111100000", "000111111000000111111110000000", "000001111000001111111000000000", "000000011000111111000000000000", "000000001000001111000000000000", "000000000000000011000000000000", "000111100000000000000000000000", "000111000000000000000000000000", "000111000001111111111111110000", "000111000000111111111111110000", "000011000001111111111111110000", "000011000000001111111111110000", "000011000001111111111111110000", "000010000001111100000000000000", "000010000001111100000000000000", "000010000000111110000000000000", "000011000000011111111111100000", "000011100000000011111111100000", "000001100000000000111111100000", "000001111000000000000111100000", "000000111000000000000111000000", "000000011000000000000111000000", "000000000000011111111111000000", "000000000000011111111100000000", "000000000000000000111000000000", "000000000000000000000000000000", "000000000000000000000000000000"}}; // Open a display window openDisplayWindow(); // Run the tests on the 5 grids for (int i=0; i  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 -1x11 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 [yl[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 part's 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 v 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 input polygon output polygon 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: 00 Polygon Displayer (6) To make sure that your allocated memory has been freed properly, use valgrind when you rur 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: 3960HEAP SUMMARY ==3960== in use at exit: 0 bytes in 0 blocks 3960l heap usage: 1,651 allocs, 1,651 frees, 80,016 bytes allocated 3960 3960 All heap blocks were freedno leaks are possible  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 -1x11 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 [yl[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 part's 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 v 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 input polygon output polygon 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: 00 Polygon Displayer (6) To make sure that your allocated memory has been freed properly, use valgrind when you rur 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: 3960HEAP SUMMARY ==3960== in use at exit: 0 bytes in 0 blocks 3960l heap usage: 1,651 allocs, 1,651 frees, 80,016 bytes allocated 3960 3960 All heap blocks were freedno leaks are possible