CG DRAWING BOARD 1.0


Introduction

Welcome to the CG Drawing Board. The purpose of this project was primarily an independent study in the Java programming language for a computational geometry course at Rensselaer Polytechnic Institute.
The CG Drawing Board is a standalone Java application. The version you see on this page has been wrapped and initialized by a Java applet and so it appears to be an applet. As you notice though, if you are running a java interpreter, you have a detached window to the CG Drawing Board.
Since this was my first attempt at writing a Java application I was a bit concerned about the possible limitation imposed by the secure environment. How can I write complex algorithms without a dynamically linked list? As it turns out, Java provides some nice classes for dynamic allocation of space. One is the Vector and a descendant of this is the Stack. The data structures are only limited by the amount of space available since they expand and contract as needed.
It can be a bit cumbersome to use the Vector class but it is quite versatile.

Algorithms

So far I have implemented two algorithms for the CG Drawing Board. Each of them computes the Convex Hull of a set of user generated points. The first of these algorithms is the Gift Wrap algorithm. To explain this algorithm most simply imagine that each point has a pin sticking out of it. Then tie a piece of string to one of the points that is definitely in the convex hull. Specifically, the algorithm picks the leftmost point. Then wrap the string around all of outermost the points in a circular fashion. When the string reaches the beginning point again you have completed the convex hull.
The second algorithm I have implemented is the Graham Scan. Although when using the CG Drawing Board it may appear that the two algorithms are the same, you might notice some difference. The Gift Wrap algorithm begins drawing the convex hull after the first point has been entered. The Graham Scan delays until three points have been entered.
The idea behind the Graham Scan is a little more difficult to explain the the Gift Wrap algorithm. Basically there are two phases to this algorithm. The first is a presorting phase where an extreme point is first chosen. After choosing this point, the rest of the points are sorted based on the polar coordinates of each point relative to the initial points. In other words, the points are sorted from 0 to 180 degrees around the initial point. Next, these sorted points are looked at one at a time and a partial convex hull is formed with the points chosen so far. Points that cause the least bend in the convex hull are retained until the process is complete.
The most complex issues of the CG Drawing Board are not so much in these algorithms as in the application environment. But, I will get to those details after I tell you how to use it.

Using CG Drawing Board

Using the CG Drawing Board is simple. The drawing board is the big (hopefully blue) section in the middle of the window. You will notice that when you move the cursor around the drawing board the current coordinates are given to you in the Info window. As you would expect, when you move the scroll bars of the drawing board you are able to access the entire board. You will notice that the coordinates reflect the movement of the scroll bars.
By default you will start out in Gift Wrap mode. When you click a mouse button in the drawing board a dot will show up at that location. When you create a second dot the convex hull of those two points (the straight line connecting them) will be drawn.
If you look at the lower right portion of the CG Drawing Board you will see a selection button that says Gift Wrap. This along with the "info" window when the cursor leaves the drawing board, lets you know that you are in Gift Wrap mode. If you click on this you will notice you have an option of changing to Graham Scan mode.
Since only two points have been entered to this point, when you change to Graham Scan mode the convex hull will disappear. Now, if you enter one more point you will see the convex hull of the three points you have entered. At this point, chaning between modes will seem almost identical.
At any time you can scroll the drawing board and add new points as you wish and watch the convext hull expand. If at any point you want to start over, just click on the Clear button on the bottom left corner of the drawing board.
That is really all there is to using the CG Drawing Board. At some point there will be other algorithms added to the drawing board such as Voronoi Diagrams and Delaunay Triangulation to name a few.

Implementation

All of the code for the CG Drawing Board is being run on your machine when you load it from you Web or Applet browser.
The initial and primary goal of the implementation was to implement a stable and easily extensible environment for showing off graphics related algorithms. I am glad to say that I think I have achieved that. Adding new algorithms at this point is as easy as writing the java implementation of the algorithm and adding a few new events to the event handler: Events.java.
Events.java is an extension of the class I used to do the layout of the CG Drawing Board. This class CG instantiates all of the main elements of the drawing board including Text Fields, Buttons, Drawing Area and is responsible for placing them in their respective locations.
Also in the class CG many of the colors and fonts are set. I am not convinced that these are the best colors for the CG Drawing Board but I wanted to experiment with the use of various colors and fonts.
With respect to fonts I found it lead to fewer unpredictable errors when I specified a font to use. For the CG Drawing Board I used Helvetica-bold-14. In the absence of a font specification, user that used specialized fonts cause unpredictable error to occur in the CG Drawing Board. I believe I have taken care of most of them.
A quirky issue that I have not figured out relates to the color of the algorithm choice button. It is supposed to have a black background and white foreground like the rest of the buttons. When using it standalone with java or as an applet with appletviewer is appears the correct color. When I run the application using Netscape the color reverts to black on grey.
I guess the best thing I can do at this point is give you access to the classes I used for the CG Drawing Board and invite you to ask any questions if you have any. You can reach me at: hulber@cs.rpi.edu.

CG Drawing Board


References

I must give credit to some of my references I found helpful for this project:
  • Laszlo, M.; Computational Geometry and Computer Graphics in C++; 1996, Prentice Hall;
  • Flanagan, D.; Java in a Nutshell; 1996, O'Reilly & Associates, Inc.