Week 1 (May 17, 2000 - May 19, 2000)

Introduction to program worked on by J. O'Rourke and Biliana Kaneva. The program is an implementation of an algorithm proposed by Chen & Han for computing Shortest Paths from a source vertex to all other vertices on convex polyhedra.

The final output comes as a result of two programs. First, chull.c computes the necessary output for use in GeomView (geometry software). This output contains the data associated with the polyhedra that will enable GeomView to display the object. The output is as follows in exact order:

  1. Number of vertices, number of faces, and number of edges. All in one line.
  2. Number-of-vertices rows, each row containing the x, y, z coordinates of vertex.
  3. Number-of-faces rows, each row containing the global indices of the vertices of the face. In addition, each row's first data is the number of vertices on the face.

Second, chull.c runs again. This time the output consists of a ".in" file, which contains the necessary data to run sp.c (the shortest path program). The output is as follows in exact order:

  1. nF = number of triangular faces.
  2. nV = number of vertices.
  3. 2D coordinates and indices of vertices for each face.
  4. Gluing instructions for each face.
  5. Source vertex specified by: index of source face, and local index of vertex on face, {0, 1, 2}

Once these files are created, sp.c runs and computes the shortest paths on the polyhedra with the data given. chull.c runs again and outputs a file with the data received from sp.c, that can be used with GeomView, in order to view the shortest paths. At the end, GeomView is launched and both the polyhedra and its shortest paths are displayed.

MY CONTRIBUTION

My task was to modify one of O'Rourke's programs to replace chull.c. The program is polyhedra.c, which takes raw data input on a polyhedron (not necessarily convex), and outputs a file for use in the Mathematica program which would display the polyhedron. Unlike the input for the chull.c program, polyhedra.c takes an image of the polyhedra made up of stars(*) and lines(-) and translates it into the number of vertices, faces, and edges.

The following were changes I made to polyhedra.c:

LOOKING AHEAD

Now that my program outputs the necessary data for use in sp.c, I need to arrange the output to that which sp.c requires.

 


Week 2 (May 22, 2000 - May 26, 2000)

First thing I worked on was getting the ".in" output file with data in the order that sp.cpp needs. As soon as that was done, I ran test polyhedra data through sp.cpp. Some of my tests worked but others failed. The data in the ".in" file crashed sp.cpp. The error messeges produced by sp.cpp were inconclusive, hence Joe and I set out to debug the program.

We settled on the fact that the 2D coordinates of the vertices were accurate, thus the problem must lie in the gluing instructions. In fact, after careful investigation, we discovered that the gluing instructions were inaccurate. In addition, the data we were giving sp.cpp included vertices that were not "used", i.e. vertices that were part of the "box-input diagram" but not part of the actual polyhedra ( the dashes ). We needed to create code that would eliminate from the data those vertices that were not being used. Once these errors were corrected, sp.cpp no longer crashed.

We were now up to the task of using the ".out" file data in conjunction with original data provided by polyhedra.c, to produce a ".vect" file which could be used by GeomView to diplay the shortest paths on the polyhedra. Although complex in the code, the data was available. It was just a matter of organizing it so that the .vect file could be created.

Another smaller task of the week was to set up "command-line" parameters for polyhedra.c. Also, the program received the more precise name of ortho.c.

Click here to view images created by ortho.c.

 


Week 3 (May 29, 2000 - June 2, 2000)

This week's task was to create a program that would compute the xy coordinates of the upper and lower circles on a cone. The program would then use these coordinates as input to convex.sh. The purpose is to see the shortest paths on the surface of a cone or cylinder.

MY CONTRIBUTION

With Joe's guidance, I wrote cone.c, which takes as input on the command-line,
  • radius 1
  • radius 2 (this would be zero, if cone)
  • height
  • number of points to be computed (the greater the number of points, the smoother the circle)

Click here to see images created with cone.c.

 


Week 4 (June 5, 2000 - June 9, 2000)

Due to memory constraints (my memory), I have decided that in order to instill accuracy in this documentation, I will need to document on a daily, as compared to weekly, basis.
MONDAY

The task for this week is to work on sp.cpp, in order to extract information about the shortest paths and use it to create "unfoldings" of polyhedra. We need to determine the xy coordinates of every vertex at the end of a path and the length of said path.

Since Joe does not return till Tuesday, I took the day to get a better understanding of sp.cpp. Due to the complexity of sp.cpp, the task is quite challenging.

I was able to successfully make a call to the displaytree() function of the class CTree.h and passed it the root Cone pointer. Not being too sure, I worked under the assumption that root is the first node of the complete tree.

TUESDAY

Initially, Joe and I worked unsuccessfully on sp.cpp. We attempted to pass the root Cone pointer to the "displaytree( )" method of the ctree.h class. Our assumption was that root was the first cone of the tree and that "displaytree( )" would then give us the desired output (xy coordinates of all vertices at the end of each path, in order). For unknown reasons, this was not the case.

MY CONTRIBUTION

I informed Joe that I had attempted to pass the head pointer to the last level of the clevel array, thinking that there was the information we needed. However, the outputwas not what was expected. It was here that Joe noticed that, in fact, passing the head was a good idea, however, the "display( )" function would need to be changed. The change that was needed was a for loop that would run through the entire list. When I was using it, it would simply output the head, and not the rest of the list.


Despite our changes, the output was still not what we needed. At this point, Joe decided this needed further studying.

The next project at hand was to create 2D images of some of my GeomView images using Mathematica® to view them as an Adobe Illustrator file. These images were for Joe & Biliana's paper. For the images created by convex.sh, this was straight foward, since chull.c allows for Mathematica® outputs. I just needed to get the mma (Mathematica® output file) and run it on Mathematica®, then get a nice angle of the picture and save it.

For the images created by ortho.sh, I am currently completing a new function for ortho.c that will create a Mathematica® output.

WEDNESDAY

Ortho.c received a new function, MathOut( ), which creates a Mathematica® output file. Having completed ortho.c, I created a couple of output files for use in Mathematica®. When Joe viewed them, he discovered that, an existing Mathematica® bug was causing some of the shortest paths to "disappear". They were not actually disappearing, but were being drawn just barely underneath the surface of the polyhedra, thereby not visible from the exterior. This was occuring in both, the images produced by ortho.c and chull.c.

After some inspection, Joe's solution was to use a Mathematica® function called AffineShape, which reduces the size of the polyhedra by some factor (in this case, 0.999). This function could be used directly by the chull.c output, since chull.c draws convex polyhedra around a center point (AffineShape reduces an image by bringing it closer to the center point by some factor). The AffineShape function was simply called with the "face" info.

For ortho.c, this was not straightfoward. Ortho.c does not have a center point. It was necessary to:

  • select one,
  • translate the image using the TranslateShape function,towards the point,
  • shrink it there,
  • then translate it back to its original position.

MY CONTRIBUTION

I used a Mathematica® file that we created manually to edit both ortho.c and chull.c. I added a function to ortho.c that computes a center point, and simply edited chull.c to include the proper call to AffineShape. I created some neat images for Joe to view tommorow and need to simply re-code chull.c for a minor 'comma' elimination.

Also, I created a new orthogonal image, boxring, that is a sort of cube skeleton. Joe requested this image, and with ortho.c working so well, it was very simple to create.

THURSDAY

The orthogonal images created yesterday had a flaw. For these particular type of orthogonal images (the spiral and the boxring), shrinkage was not necessary. Joe manually altered these. In addition, I re-coded chull.c to eliminate the extra comma mentioned yesterday.

After the images were done, Joe instructed me on a new task. His work on folding and unfolding requires a proof, for which he would like to see some evidence. He has two conjectures to prove and feels that proof of the second conjecture, might help him with the first.

The motivation is as follows:
   If a convex polygon is unfolded into a chain C,
   with restrictions on the range of angle-turning, then
   then the new chain, C1, does not self-cross.

   In addition, the length of the fixed segment, L0,
   will always be  ≤  the length of C1.

My contribution is to be the following:

  • Create a program that will generate random points creating a convex polygon.
  • Compute the lengths of all segments.
  • Compute all the interior angles of the polygon in order to compute the angle (to the horizontal) exterior to each interior angle. This angle will indicate the restriction of the turn.
  • Check conjecture 1.
  • Check conjecture 2.
  • Display these checks graphically.

While I struggled to determine how best to approach this task, it occured to me that, since I would best display these pictures in Mathematica®, why not use Mathematica® to compute all the other data needed?

I am now in the process of reading up on Mathematica® (with which, for unknown reasons, Im having so much fun) in order to complete the task. Joe has written a Mathematica® function to compute the angles and before leaving, I wrote a small function to compute the length between two points. I will now identify how to program this, so that it will find the lengths of all the segments on the polygon.

FRIDAY

Unfortunately, most of my morning was spent getting the code to store the lines (two points/line) on a list. I realized later that in order to compute the lengths of the lines, I would need the points, not the line. Nevertheless, I now have a working function to check the length (distance) between two points.

I integrated Joe's TriAngle function. Now the program computes lengths and angles.

Next week, I will begin by modifying Joe's TriAngle function to eliminate the Print statements and, attempt to store these angles in a list. Once stored, I can subtract them all from 180° to get the "turn" angles.

 


Week 5 (June 12, 2000 - June 16, 2000)

After storing the polygon angles in a list, I computed the "turn" angle by subtracting each angle from Pi. After which I computed new turn angles for all the polygon angles by using the Random[] function.

With the help of various other functions, I was able to compute all new point values for the "unfolded" polygon.

Further tests are necessary now to determine if my numbers are correct.

UPDATE SUNDAY THE 18th

For the rest of the week, I struggled trying to figure out why I was getting angles that did not appear to be correct. I finally gave up and decided to wait for Joe to return.

Once Joe returned, he quickly realized that the formula he gave me to compute the angles was inaccurate. He was working under the assumption that L1 ( the first line ) would be on the x-axis and that P1 ( the first point ) would be at the origin. This of course was what was causing my faulty angles, since is not necessarily on the x-axis. Having corrected the problem, the focus now is to create the program within a Do loop, in order to let it run many examples. However, as I was cutting and pasting to a new Mathematica® notebook, the Mac crashed. Since the work that Joe did earlier was not saved, I had to attempt to replicate his ArcTan function for computing the proper first angle. I will need to ask Joe on Monday because what I wrote is again, not printing the right picture.

 


Week 6 (June 19, 2000 - June 24, 2000)

This week I focused on learning Java. My project, in addition to learning Java, was to implement the Mathematica project into a Java applet. Much of the material I read in the beginning of the week, was written in pre-ver1.2 Java, which means that it did not incorporate the Model-View-Controller.

In order to learn the latest Java, I focused on MVC and have written my classes according to the "Listener" implementation.

The program is not yet finished. You can see the unfinished applet here

 


Week 7 (June 26, 2000 - June 30, 2000)

This week, as I became more comfortable with Java, the program grew into 5 files. It now looks something like this:

PolygonUnfolding.java
This file extends applet. The buttons are placed here and the user can place points on the browser. These points are followed by "connecting" segments once the second point is placed. Once the polygon is finished, the user is able to select a point on the polygon. The selected point and every point and segment after the selected point (up to n-1), will turn red, indicating that that chain may be moved by draggin on the browser. In addition, the "forbidden circle" is displayed.
DoMath.java
Mathematical formulas to compute angles and points are in this class.
MouseController.java
This class implements MouseListener and MouseMotionListener to respond to user mouse activity.
ButtonController.java
Class implements ActionListener and responds to all button activity by calling the pertinent methods from the Point class.
Point.java
This class takes care of most of the polygon manipulations. The data arrays are here along with all functions that work on them, including handling of the input from mouseDrag event.
As per Joe, the applet will now take on a more "professional" appearance by making more GUI manipulations available for the user.

 


Week 8 (July 3, 2000 - July 7, 2000)

Added utilities to the applet have expanded my program to 11 files. The 6 new files area:

PolygonApplet.java
This is now the file that extends applet. The need to establish modality to the applet in the case of an input error, forced me to create 'Frame' class which now holds a Canvas (for drawing the chain) and Panel (for buttons). With this implementation, the error box (Dialog) can now be set to true, in order to prevent further input to the Canvas.
checkWindow.java
This file extends WindowAdapter and implements the windowClosed method to allow user to close the frame.
ErrorFrame.java
A misnomer. Actually this is the class that extends Dialog which is responsible for the error boxes.
CanvasArea.java
The only method present here in the paint().
FrameHelp.java
Displays a frame with TextArea. Information on the use of the applet is displayed when user presses help button.
ForbiddenCircles.java
The class I am currently working on. Computes data necessary for display of all concentric forbidden circles for each chain 'joint'.

 


Week 9 (July 10, 2000 - July 14, 2000)