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:
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:
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.
The following were changes I made to polyhedra.c:
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.
Week 4
(June 5, 2000 - June 9, 2000)
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.
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:
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:
In addition, the length of the fixed segment, L0,
My contribution is to be the following:
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:
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:
Week 9 (July 10, 2000 - July 14, 2000)
MY CONTRIBUTION
With Joe's guidance, I wrote cone.c, which takes as input on the command-line,
Click here to see images created with cone.c.
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
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.
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.
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.
will always be ≤ the length of C1.