CISC 829 - Homework 1 Programming Assignment

Bryan Youse, Yuqi Wang, Christopher Thorpe

Brief description of solution in (hopefully) plain language:
Our solution uses OpenGL for rendering its graphics and is written in C++. As described below, it uses a simple interface for adding, editing, and clearing points. There exists an input mode where Melkman's algorithm is used to compute the convex hull as points are added. The fact that Melkman's algorithm is an on-line algorithm allows us to do this. Basically, each time a point is added, a routine is called that re-computes the hull (if necessary). It starts out by computing the simplest possible convex hull, consisting of the first three points entered. A doubly-connected queue, or deque is used to store the order of these points, which is necessary information for the rest of the algorithm. As each point is added, a check is made to determine if it is already inside the convex hull region. In this case, obviously no alterations to the hull need be made. Otherwise, modifications to the convex hull are made. Essentially, using the ordering properties of the deque, we simply check for which vertices currently in the convex hull are made obsolete by the new vertex in question (that is, which vertices will no longer be part of the convex hull once the new vertex is added). Getting rid of these vertices, we add the new vertex to the convex hull and store it at the top/bottom of our deque. This process is repeated until after the vertex just entered by the user of the program, which was the last vertex! The convex hull is now final (until a new vertex is entered). If a vertex is entered which makes the polygon no longer a simple polygon, it is ignored by our solution. However, future vertices that are entered can still add to the convex hull if added in the right place! Our solution is available in various formats:
Runnables:
Melkmanx86 - a pre-compiled version of our program for x86 GNU/Linux (dynamically linked with GL and glut libraries)
Melkman.zip - a zipped folder with a running win32 executable build of our program inside (dynamilcally linked with glut32.dll - included)
(if neither of these run or are suitable, please contact us)
More:
Melkman.tar.gz - a gzipped tarfile containing our program's source files and a makefile for GNU/Linux (needs GL and glut libraries to build)
MelkmanVS.zip - a zipped folder with a Visual Studio C++ project containing our program inside (needs GL and glut libraries to build)
Source directly linked:
Melkman.cpp
Melkman.h
Instructions for using our application:
Points are added by clicking anywhere on the "canvas". Hold the SHIFT key while adding points in order to add a point directly horizontally (if the mouse position is within a 45 degree cone to the left or right of the last point) or vertically (if the mouse position is in the complement cone). The points are displayed in red, with the exception of the last point, which is white. This is so when you are using the SHIFT modifier to create a point directly horizontally or vertically from the last point entered, you know which point you're referencing. The default mode is "points-only" mode. The following keys provide access to different modes or functions: That's it! We hope you find our program easy to use. If there are any questions, please contact us.