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

Overview

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(N^1/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).

Finding the distance between a given point and a given line segment
Determining whether a given point is inside a given convex polygon

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:

C X Y

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:

``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
``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
``No warnings'' means that neither of the two warnings are in effect.
``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).

Errors

Your program must detect the following error cases:

Unexpected first line (normally, it must have one integer number)
Insufficient number of lines (fewer than implied by the first line)
Coordinate out of range, (value not between -100 and 100 inclusive).
Invalid first character (First character is not a Y or an S)
Invalid line (Line is not in the "C X Y" format).
Input file does not exist.
There were 2N lines but not N sharks and N yachts.

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

An outline of your algorithm which steps through the major activities of your code which lists the complexity of each of these stages. For most programs there will be 5-10 major activities (read in the input, sort, print out the output, etc.) which can be identified. In addition, for the actual check to see if the convex hulls are within 1 mile of each other, they would like you identify break this down into its various components. (Computing the convex hulls, checking to see if a point lies within the convex hulls, etc.) This outline is to be written in a text file called algorithm.txt
Remember, your implementation should have O(N log(N)) runtime.
An empirical study which times your algorithm on worst-case inputs of varying size. For these cases you should create inputs which have exactly ceiling(N^1/2) vertices in the boundary of both convex hulls. Further, you should be sure that these are reasonably close to the worst-case inputs. You are to provide a postscript file named worstCase.ps in the directory with your program. It should be a one-page graph showing how the run-time varies with N. (The graph must also include your name and unique name!)
A set of ten test cases. Five of them must be test cases which you used to generate your run-time graph (although you may have used more test cases...) These are to be called runtimeTest.x where x varies from 1 to 5. The other five must be non-error test cases which show your program will get the correct answer even for ``corner cases.'' They are to be called cornerTest.x where x again varies from 1 to 5. All of these files should be in a subdirectory named TESTS and none of these tests should contain more than 10,000 points. Note: for the corner cases you are simply supplying test cases you believe do a good job of testing your code for correctness.
Your need to create your own testcases that are different from other students' testcases.

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.

Hints

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.

What to turn in

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
The annotated outline of your algorithm in a file called algorithm.txt.
A postscript graph of your empirical testing showing that the runtime does not grow significantly faster than N. This should be called worstCase.ps
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:

You have deleted all .o files and your executable(s), e.g., by typing make clean.
Your makefile is called Makefile
make clean actually does remove the executable and the tmp files (such as .o files)
Typing the command make will generate an executable called findSharks
You don't have any unneeded files or other junk in that directory or any of its subdirectories.
Go to one level above the the directory with your code (and makefile, etc.). type
/afs/engin.umich.edu/class/perm/eecs380/bin/submit380 2 DIRNAME
where DIRNAME is the name of the directory in question. The program will verify that you wish to turn your code in, and that's it.

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 N₁ in the range from -100 to 99, and then another one N₂ in the range from 0 to 999999. Then you can append the digits of N₂ to N₁ after the decimal point. In other words, the resulting real number will be N₁+N₂/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(N^1/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...

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?)
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 P₀ 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.