Project 2 -- EECS380 -- Winter 2001

Convex hull --- ``Elvis needs boats''

Assigned Tue March 6, 2001
Due Thu March 22, 2001
Extended to Fri March 23 at 10pm


For this project you will write and test a C++ program which notifies racing yachts about potential shark-infested waters.

Part 1. Convex hull

Implement a sorting-based algorithm for finding the boundary of the convex hull of N points in the plane in O(N log N) time --- we have handed out the relevant algorithm from the CLR book (pp. 898-908). You can get additional copies during office hours. It is also available on-line.

Your code must make only one call to STL's sort() per convex hull and have overall complexity O(N log N). Everything else is up to you.

Your implementation must show good programming style and be reusable.

Part 2. "Shark-proximity warning"

You are managing a regatta in the South Pacific. Every 30 seconds, your computer receives updated locations of N yachts from the radar and updated locations of N sharks from the sonar. Your job is to report if the sharks and the yachts are getting too close to each other.

Your program must check the following formal condition that addresses all of the above concerns. The distance from the convex hull of the yacht locations to the convex hull of the shark locations should be more than 1 mile. Note that the convex hull includes the interior and the boundary. Therefore, if one convex hull is completely surrounded by the boundary of the other convex hull, the distance between the two hulls is zero.

One potentially helpful fact is that if the two convex hulls are within 1 mile of each other, it is also the case that at least one the points on the boundary of one of the convex hulls is within 1 mile of the other convex hull.

You are to write a program that, given the 2N locations, can determine in O(N log(N)) time whether you should warn all skippers. Your program may terminate as soon as it processed enough data to conclude that the the convex hulls are closer than one mile. For example, when a shark is found half a mile from a yacht, the program may signal "shark-proximity warning" and stop so that all skippers can be warned right away. For complexity analysis, you can assume that the boundary of the convex hulls of both the yachts and sharks contain O(N1/2 ) vertices.

Point-to-segment distance and point-inside-polygon test

The following two primitives from computational geometry must be used in this project (make sure you implement them in a reusable way). Those are explained in handouts (you need "Solution 3" for the polygon test). If you would like to use additional computational geometry primitives see Paul Bourke's site (scroll down past pretty pictures), but that should not be necessary.

Input and output formats

Your program must read the following input: N on the first line, and then 2N input lines of the following form:
where C is a character (`Y' for Yacht or `S' for shark) and X and Y are real valued coordinates measured in miles. The real numbers will be in the range from -100.0 to 100.0. Having too many lines is not an error, but everything beyond the 2N expected lines should be ignored.

sample input files are available

The command-line argument -Inputfile will indicate the name of the input file. If no input file is specified, the file elvis.txt should be used.

Based on those inputs, your program must generate exactly one of the following messages to standard output:

  1. ``A shark is too close: '' if at least one shark is closer than one mile from the convex hall of yachts. This message must be followed by the shark's location. (X location then Y location) Example:
    A shark is too close: 3.4000 -2.4554
  2. ``A yacht is too close: '' if at least one yacht is closer than one mile from the convex hall of sharks. This message must be followed by the yacht's location. Example:
    A yacht is too close: -8.11 -2.4010
  3. ``No warnings'' means that neither of the two warnings are in effect.
  4. ``Error: '' indicates that something went wrong and the program could not reliably complete. This might be due to an input error or some other error condition. This message must be followed by an explanation of the error. See the section below for a list of errors for which you need to check. You may use any descriptive message here.

For the first three cases, nothing else should be printed to standard output and the program must exit(0). In the case of an error the program must print an error message to standard output and to the standard error, then terminate with exit(1).

It is possible that it may be appropriate to print both message 1 and message 2. However, you are to print out just one of them (your choice).


Your program must detect the following error cases: Include the input line number in the error messages, when relevant.

Guarantees you can count on

It is guaranteed that no two objects of the same type will be closer than .005 miles.

Part 3: Proof and testing

Clearly it is very important that your program respond quickly, even in the worst case. As such, the regatta's sponsors have asked that you provide two pieces of evidence that your code will respond quickly. They want

Note that the very operation of receiving data typically takes at least linear time, and N log(N) is a "near-linear" function. Therefore, if your implementation requires O(N log(N)) time, you can say that even in the worst case you can process radar/sonar data almost as fast as they arrive.


You will likely find it useful to be able to visualize the locations of the sharks and yachts. We suggest, but do not require, that you use gnuplot to show the convex hull and the vertices (the script used to produce the picture above is posted as a handout). This will make it much easier to identify errors.

More hints will be posted as handouts

What to turn in

  1. Complete code to the autograder, as in project 1. The command make should build your program. The command make clean should remove all temporary files and the executable. Your executable should be called findSharks
  2. The annotated outline of your algorithm in a file called algorithm.txt.
  3. A postscript graph of your empirical testing showing that the runtime does not grow significantly faster than N. This should be called
  4. Ten test cases that you generated should be in the subdirectory TESTS and named as described above.
All of this will be turned in via the autograder. There is no need for paper copies.

Note that in the overall worst-case, the boundary of the convex hull of N points can contain all of them. However, for the purpose of this project, we assume a "reasonable" distribution with fewer points lying on the boundary of the convex hull. Therefore, we consider worst cases under this assumption.

How to turn it in

This is pretty much the same as project 1. Do all of your work, with all needed files, in some directory other than your home directory. Before you turn in your code be sure that:

Appendix A: Random coordinate generation

In order to test your implementation for large numbers of sharks and yachts, you need to generate random coordinates in the range from -100 to 100. An acceptable way of generating one such coordinate is to first generate a random integer N1 in the range from -100 to 99, and then another one N2 in the range from 0 to 999999. Then you can append the digits of N2 to N1 after the decimal point. In other words, the resulting real number will be N1+N2/1000000.

Also note that if you generate a large number of sharks and a large number of yachts in the square [-100,100]x[-100,100], then most likely, the convex hulls will intersect. You need to come up with ways to generate configurations where convex hulls can be far apart. Otherwise, you will not be able to empirically evaluate worst-case performance and your tests for correctness will be weak.

Finally, you may find it difficult to generate test cases of size N with exactly ceiling(N1/2) vertices in the boundary of the convex hull. Our suggestion is to use a circle and place the needed points on the circle and then place the remaining points well inside of the circle (maintaining the required spacing). This part is not supposed to be hard, if you have problems figuring out how to do it, ask. Discussions (but not code) on this topic are welcome on the newsgroup.

Appendix B: Additional development resources

See newsgroup postings about purify and gdb. We've been told that all enrolled 380 students have been given access to Purify. (Thanks Ken!)

Appendix C: Misc fun stuff

If the project looks too easy so far, or you just get bored, here are some questions Mark and Igor came up with while working on this problem. This is not for credit or anything...
  1. Consider N dots that are (uniformly) randomly placed inside a given circle. What will be the average percentage of dots that are in the boundary of the convex hull? Why? (The percent seems to drop as N increases, but at what rate?)
  2. Same as above but for a square.
We may add things to this list as other questions arise.

Appendix D: Fan club

A picture of Ron Graham (August 2000, UCLA). Ron Graham is a Professor of Computer Science at UCSD.

These animations (implemented in Java) may illustrate how Graham's scan works...some aren't exactly the same as in the handout (i.e., using the topmost point as P0 instead of the bottommost point, etc.), but they're pretty close:

From Alejo Hausner at Princeton: Graham, Graham Scan

From Mandar Gokhale at U of Illinois: GrahramAlgo

From Connie Peng at U of Maryland (allows you to specify the points): convex hull_anim

Thanks to Brett Allen for finding those.