Code written by tado-mi for CSC 284: advanced algorithms class at the University of Rochester. It is made public to demonstrate a code sample by the author, and for learning. We trust it will not be used to violate academic honesty policies.
The included code implements the Graham Scan to solve the Convex Hull problem. It outputs the steps of the algorithm on the input in a text format, and will soon have an implementation of step-by-step execution of the algorithm on a GUI.
Is a work in progress.
Simple class representing a point in R^2. Of interest are the comparator methods, angleComparator
in particular, which allows to sort points for the Graham Scan.
The most involved class both implementing the algorithm (computeHull
method), maintaining the execution steps (through log
method), and dealing with graphics.
- finish
log
method - decide whether GrahamScan should be involved with graphics
Snipped from a code originally written by Michael Scott (see here for details, if interested). Included here as a source of inspiration.
- improve graphics: scaling & translating the points
- highlight the 'focal' points and lines
- enhance interactivity on the GUI: allow the user to { insert the filename / choose to see a random example } in the GUI; { set pace } in the GUI
- display text explanation as steps are being executed
Where the main
resides.
There is an included makefile for convenience. To run the code on a random input set, hit on the terminal:
make
make random
or, to run the code on the provided test/small.txt
test case, hit:
make test
or, to run the code on a custom test case, run:
java main path/to/file
to free your computer from the bytes occupied by the .class:
make clean