CS3990 Java Programming Project Report

Table of Contents

Project Description
Project Name : Convex Hull Graph Algorithm Demonstration
Student Name : Jeff ( Cheung ) So
Description :
Convex Hull problem refers to the graph problem that given a set of points and determine which points lie on the "outer perimeter".

Project Objectives
There are many solutions to the Convex Hull problem. The Brute Force Algorithm and Quick Hull Algorithm were chosed to implemented in the program. The main purpose is to compare the speed between two different algorithms in finding the hull. The program also displays detail execution event of the algorithm by showing which lines and which points are being compared.

Program Control Description

Screen Layout :

Menu Options Description

Screen Panel
The main screen panel for user to choose points and display the result. The operation on this screen is interactive. If the user choose a new point during the calculation, the program will restart the calculation all over from the beginning.
Algorithm Choices
This choice list allows the user to choose between Brute Force Algorithm and Quick Hull Algorithm. This is not an interactive option. If the user wants to change to different algorithm, he/she has to make the change before clicking on the GO button or after the execution.
Speed Choices
This choice list allows the user to choose the demo running in Slow speed, Fast Speed or with No Delay. The speed is actually the time delay between 2 consecutive temporary results. Setting the speed in Slow speed allows a more detail observation of how the program finding the hull. This is an interactive option which means the user can change the speed during the calculation. Setting the speed to No Delay simply means to ask the program to calculate the hull without showing any detail. Slow speed is hard-coded as 100 microsecond delay while the Fast Speed is hard-coded as 20 microsecond delay.
Sound Option
This option allows the user to turn on or off of the sound. This is an interactive option.
Clear Button
This button allows the user to clear the screen at any time. This is an interactive button. If the user clicks on the button during the calculation, the program will stop calculating, clear the screen and wait for the next command.
GO Button
After the user has chosen at least 3 points in the Screen Panel, he/she can click on this button to start the calculation of the Convex Hull.
??? Button
When user clicks on this button, the program will display a little help menu.

Encounter Problems and Solutions
Problem with screen repaint
The quickhull algorithm is implemented in a recursive way. However, it seens to be the problem that when calling the repaint() inside these recursive quickhull method, the screen is not updated immediately. Therefore, one of the purpose of the project which trying to show every single step of the calculation cannot be accomplished. The solution is to calculate the result first and at the same time storing all the temporary results in the memory, after the calculation, the program will regenrate the events and display the result in the screen.
Program interruption by loading sound files
In the early stage of the coding, the program is loading the sound clip files in a on-demand base. Since the early stage program was testing in a local file system, therefore, the delay was not significant enough to affect the preformance of program. However, after putting the applet on-line and tested through Internet, significant delay can be noticed when the program is loading these sound clip files. The solution is to load all the sound clip files during the initialization of the applet.
Rounding error problem
Since the applet deals with the Graph theory, so points and lines are the major components of the program. It is also because the program has to do the screen output, therefore the x-y coordinates are in a small range of absolute integer value. That creates problem when calculating the slope for a line with very small difference between either their x-coordinate or y-coordinate (eg. with big difference in x, but y1 is greater than y2 by 1). The solution is to multiply the result with a big integer number ( I use 10000 in the program ), and then compare this multiplied integer value.

Something I Learned from this Project
Basically, this is the first big program I have written with JAVA. I sure learned a lot from this project, especially the real usage of object-oriented programming and multi-thread application.

Since Java is a totally object-oriented lanuage, everything got to do with class ( object ). I was forced to give up many programming habbits from C and considered my whole program from a object-oriented aspect.

The Developer kit of JAVA comes with a huge pre-developed classes, getting familiar with all the pre-developed classes is definitely a good starting for a beginner. There were several time that I created some new classes, and then I found out there are similar pre-developed classes in the library. To have a good understanding of these pre-developed classes, not only we have to known their functions, but also how do they being implemented. Regarding the repaint() problem I discussed above, I am still thinking that it might not be the case about the relationship between repaint() and recursive call, but instead the actual implementation and co-relation between paint(), update() and repaint().

Since Java was developed as a multi-platform language with the support to Internet, we shall pay attention to this particular feature during the programming. Take the Convex Hull applet as an example, after I had finished most of the coding, then I noticed that the program is so heavily CPU-bounded, the performance and the visual effect is closed to a unacceptable level when running the applet in a 486DX PC. The internet is another important area we shall consider during the development. Refer to the Program interruption by loading sound files in the Encounter problems topic for a detail example.

Java also provides the multi-thread feature for programmers. Knowing how to make use of this feature would be a great help in the programming. For example, there are several interactive options and buttons in the convex Hull applet. Actually, there are no special codes to make them interactive, but instead make use of the thread with pre-developed methods like start(), stop() and restart().

Words from Author
Since the documentation is finish in such a rush way, no spell checking or grammar checking has been done with the report. I am sorry about any inconveriences brought to you during your reading. Hopefully, this will help you little bit in understanding the Convex Hull applet and you may as well give me any comment.
My E-mail address : soj3990@cs.uleth.ca
Back to My Home Page