Convex Polygon Triangulation

For this assignment, you are to implement a convex polygon optimal triangulation algorithm. You will write a program that accepts as input a description of a polygon and produces as output a description of the polygon along with a description of an optimal triangulation.

File Format

The input your program accepts and output your program produces will follow a strict format. Input files called sample1, sample2 and sample3 are available on the ringer system in ~djimenez/Classes/cs3343/assign4 . An input file is an ASCII file that begins with the word vertices on a line by itself, then followed by lines of pairs of positive integer x, y coordinates listed in counterclockwise order. Here is a sample polygon file: 
vertices
60 90
40 100
100 300
200 200
100 100
It's a good idea to represent each vertex as a C struct something like this: 
typedef struct {
	int	x, y;
} vertex;
The following piece of code, with the above typedef and appropriate #includes, will read in a polygon file, returning the number of elements read: 
int read_vertices_list (vertex v[]) {
	int	i;
	char	s[100];

	fgets (s, 100, stdin);
	if (strncmp (s, "vertices", 8)) {
		fprintf (stderr, "not a vertices file!\n");
		exit (1);
	}
	for (i=0;;i++) {
		fgets (s, 100, stdin);
		if (feof (stdin)) break;
		sscanf (s, "%i %i", &v[i].x, &v[i].y);
	}
	return i;
}
The output file format begins with the same kind of data, followed by the word triangles and then a list of triples of vertex indices. A triangulation program run on the above input file might produce the following output: 
vertices
100 100
200 200
100 300
40 100
60 90
triangles
0 1 3
1 3 0
1 2 3
Each line in the triangles section gives three indices in the array of vertices, e.g., the first line means "the triangle formed by the #0 vertex (100, 100), the #1 vertex (200, 200) and the #3 vertex (40, 100)."

How to do the assignment

Use the memoized algorithm presented in class. Remember to do your arithmetic on array indicies modulo n+1. The whole discussion was based on an n+1 vertex polygon with indices numbered from 0 to n; if you let n be one less than the number returned by read_vertices_list above, you will have this same situation in your program. Use the cost function discussed in class, adding the Euclidean length of the sides of the triangles.

There is a binary executable program called showpoly in the same directory as the sample files. You can use it from an X Window System display such as the Suns in the CS lab to display the sample input files as well as the (properly formatted) output of your program. showpoly takes its input from standard input, so if your programs output is in a file called foo, the following will display it (or crash if your file is bogus :-): 

showpoly < foo
You can quit showpoly by pressing Enter (or CTRL-C) in the window where you started it. Note: It is not hard to make showpoly crash. Make sure the file you give it really does conform to the output file format described above. Try running it on the above example output file. The source code to this program as well as a Makefile and other files required to compile it are in the same directory. The file showpoly.c may be helpful in understanding the assignment and writing your program; feel free to steal code from showpoly.c.

What to turn in

Turn in a printout of your well-documented triangulation code as well as sample output files giving your triangulations. Also include printouts of the graphics showpoly draws for each of the sample files. You can do this by using the graphics program xv (see man xv for details) to grab the window and then print it: