Programming Assignment 7 - Triangulation

See the assignment turn-in page (last modified on 21 January 2003) for instructions on turning in your assignment.

A point is within a valid triangle if it is in the interior, on the edge or coincident with one of the valid triangle's vertices. Every valid triangle has three non-collinear vertices.

typedef std::vector<std::pair<int, int> > ptvec;

struct points {
  ptvec c, g, y;
  };

points triangulations(const points &);

that accepts a set of green, yellow, and clear points and returns a set of greenish (in the g vector), yellowish (in the y vector), and clear points (in the c vector); only those points that are neither greenish or yellowish should appear in the output clear-point vector. Your procedure should be as fast as possible.

ptvec, points, and triangulations() are defined in triangulations.h in the assignment directory /export/home/class/cs-509/pa7.

You can test your procedure by compiling it with the file

where os is either linux, solaris, or stlport-solaris. Running the resulting executable calls triangulations() and compares the answer returned with my answer. If you get no output, then everything's fine; otherwise you'll get an error message indicating a problem.

The test procudre recognizes the following command-line options:

• -mn - Create problem instances in which the number of green, yellow, and clear points each is at most n (that is, the largest number of total points in the problem is 3n.) The default is n = 500.

• -sn - Use the integer argument n as the seed for the random-number generator. You can run your code repeatedly on the same point set by passing in the same value with -s on each execution. The default is to generate a different point set for each execution.

• -t - Print the timings for each test run. The default is to print the timings only when they're too big.

The source file for main() will not be made available because it contains my answer to the problem.

If you use with stlport-solaris-main.o, make sure you compile and link everything with STLPort files; otherwise you'll get link errors.

Your implementation of triangulations() should not exploit any extra properties of the input data; I'll be generating different input data when I test your assignments.

To be correct, your solution must be efficient; that is, you solution should take no more than twice the execution time my solution takes on the same input. The test executable keeps track of execution times. The -t command-line option prints the execution time taken by your version of triangulations().

Remember, your objective for this assignment is to write the fastest implementation of triangulation() that you can. Your objective is not to write an implementation of triangulation() that is as fast as mine, because my implementation may not be the fastest possible.