Euler Project

November 20, 2008

As pointed out by Wes it has indeed been some time since I posted anything on this blog. About once a week it occurs to me that I would really enjoy writing about this or that, but I just haven’t had the time lately. Part of the reason is how long it actually takes me to get a post up. It typically takes me around 30 to 40 minutes to write something mildly interesting, and then another 10 or 20 to proof read it. It is not as if I couldn’t find that sort of time, but typically I only have it at night, and when I am tried I find it very hard to concentrate on what I am writing πŸ™‚

In any case I want to write about Project Euler today. About a week ago my Professor introduced to to Project Euler. They have a list of computer science and math problems that they ask you to solve, and typically the problem involves you needing to have some sort of mathematical intuition as well as coding skill. One simply makes an account on their site and when you think you have a solution to the problem you submit your answer and the site tells you if you got the right answer or not. So far I have been working on the earlier problems in the list when time permits. For a lot of them I tend to hack together a solution in Python within 5 to 10 minutes. I have heard the later problems get harder, and I await the challenge. Project Euler meets the strange need to write random small computer programs that perform an operation which is “cool” to only a small group of people. I also like the mathematical challenges that some of the problems provide, and it gives me a good test of my problem solving skills, which I think are very important to any computer scientist. The other interesting part to these problems is that Project Euler guarantees that your program should find a solution in under one minute of run time. This adds an extra challenge because you can’t necessarily brute force the answer :).

While writing solutions to these problems I have noticed how much slower Python is than C in certain cases. I have read many different guides to optimizing Python code and applied optimizations everywhere I can, and still the C equivalent to my solutionsΒ  runs drastically faster. I am not suggesting that C is necessarily a better language or something. Certainly, one expects a compiled language to outperform a scripting language, but since I had never done any formal study before I found this quite interesting. I do enjoy the speed at which I can throw together the solutions in Python, and I’m glad I taught myself Python a year or two ago because I have used it many times since then.

Anyway, I have a lot more to write about, and have been keeping a list. Hopefully over Thanksgiving break I will be able to put in an entry or two. At the very least when this semester ends I will have plenty of time to write blog entries and plan to be more active during that time.

Back to C++

September 10, 2008

It has been a while since I have had the time to sit down and write something here so I figured now is as good a time as any. I actually have class in a bit, but I figured I would be able to get something down of mild interest before I leave.

As one of my final computer science classes before I graduate I am taking a class based largely in theory. Mainly we will be studying NP-Complete problems, but we will study some other topics as well, which I may blog about when the time arrives. Until a few days ago we did not actually have any homework assignments which involved programming 😦 .

The assignment we did get, though, was pretty interesting. The basic idea behind it is that you must take the string 123456789 and insert +’s, -‘s, or nothing in between digits. Also, for our class, you could also place a – or + sign in front as well (though the + doesn’t really do anything) . You must generate all possible combinations of this string and find the smallest possible positive integer that you can create in this way. This required us to implement an algorithm (which we learned in class) that can be used to generate all possible combinations of some arbitrary set (i.e. the power set). We were allowed to write this program in any language of our choosing. I joked around saying I would try and write it in MIPS assembly or LISP. I did seriously consider LISP, but I lacked the ambition to relearn it. In the end I decided to write this in C++.

My design of the problem wasn’t anything noteworthy, and that is not really the point of my writing this post. I simply really enjoyed writing C++ code again. It took me a little bit to get back in to the spirit of things, but once I remembered the little syntax quirks and general coding style I was loving every minute of it. This program did not take all that much time to program, nor was it particularly challenging. Perhaps I just have a sentimental feelings for C++ as it was always a language I had aspired to learn since I started programming in the 8th grade. I was extremely pleased that my college offered it as a course. Sadly, the intro level classes are now taught in Python, which I have mixed feelings about. I’m not sure if a language will come along that I will ever like more than C++, but who knows what is on the horizon.

C++ just seems to be the best combination of two worlds of programming that I enjoy. The low level access to memory, variables, other reasources of C, and with support for OO style programming. I know some would argue those should never be combined. For me I just like knowing that if I need to access the low level stuff it is readily available, and that I do not have to jump through hoops to use it. With an OO language I know that you are typically trying to write high level code, and I would say that is true for me most of the time. However, access to pointers can really come in handy in certain circumstances. Yes, I know there are workarounds for other languages, but it is convient to have them right at your finger tips.

Perhaps I am just holding on to my past, but I sure do enjoy coding in C++ πŸ™‚ .

Intersection of Spherical Circles (Finally!)

July 23, 2008

For the past two weeks I have been pondering on and off how I would calculate the location of the intersection of two spherical circles. I really want Spheriosity to be as complete as possible and having the intersection tool only work on Spherical lines/line segments seems like a real lame idea. So I have finally devised an algorithm which can correctly determine the intersection points. I will give a brief overview of it here. I will leave out details about different parts of the algorithm which I feel are either trivial or would need their own blog post to explain ;).

So we start with two circles… What are the possibilities for their arrangements in terms of intersections:

  1. The most simple is if the circles are not anywhere near each other and don’t intersect.
  2. One circle could be “inside” the other. In this case the circles obviously do not intersect.

    One circle inside the other

    One circle inside the other

  3. The two circles could intersect only in one spot. This could happen in a number of ways:
    • Case 1:

      First Intersection Case

      First Intersection Case

    • Case 2:

      Intersection Case 2

      Intersection Case 2

  4. Then there is the case where the circles intersect twice. This is perhaps the most common case in terms of what users will see, but since the other cases are easy to construct we must also deal with them.

So that loosely describes my problem and the different scenarios that need to be considered. So… on to the solution! Much of this boils down to finding the intersection of two planes. Each circle on the sphere defines it’s own plane which basically slices the sphere, and the intersection of that plane and the sphere could also be used to form the circle. So the intersection of the planes formed by both circles forms a line which, if it goes through the sphere, can be used to find our points of intersection.

Defining that line of intersection turned out to be the largest problem. It was easy enough to get a vector going in the correct direction but I still needed a point to form the line and perform any sort of calculation on it. Here are the steps I take to find the intersection and make sure one actually exists:

  1. Consider two circles AB and CD (defined by center point and radius point).
  2. Find the normal vector to the planes formed by each circle. We will call these vectors a and c
  3. Take a x c if the magnitude squared of the resulting vector is 0 you can stop now because the planes are parallel, and the circles could not possibly intersect (or are coincident).
  4. Form an axis of rotation, r, between points A and C.
  5. For both circles form lines by rotating their respective center points forward and back by the angle formed between their center points, the center of the sphere, and their radius points. (call these lines l and m.
  6. Find the intersection of lines l and m and call this point I
  7. Find the intersection of the line formed by using point I and the cross product of a and c with the sphere.
  8. Consider the following cases:
    • Case 1: Line does not intersect the sphere: no intersection points
    • Case 2: Line intersects once with the sphere: one intersection point
    • Case 3: Line intersects twice with the sphere: two intersection points

There you have it! I know I left some details out, but writing out every single step would make this a really long post ;).

Spheriosty and Parallel Transport on the Sphere

July 11, 2008

Today I was writing some unit tests for Spheriosity and I discovered a flaw with the code that currently handles parallel transported lines. For those of you who are unfamiliar with the concept of parallel transport I will do my best at describing this to you.

Basically start with any two intersecting lines:

Two intersecting lines

Two intersecting lines

Now, slide the first line along the second keeping the angle between the two lines the same. You have just parallel transported your first line! By definition parallel transport merely keeps the angle between those two lines the same as they move.

Parallel transported line

Parallel transported line

Why is that so dang special? But wait! Isn’t that just a fancy way to say “keep the lines parallel”? Well, on the Euclidean plane, yes. However on a sphere there is no such thing as parallel. Two straight lines [known as great circles on a sphere] will always intersect. If you don’t believe me you can always try it out for yourself. Any true mathematician probably doesn’t believe me, as I have not provided a proof πŸ™‚ .

Parallel transport of a great circle

Parallel transport of a great circle

Notice in the above picture that we have transported along the horizontal line. It is obvious that the original line (right line) and the transported line (left line) will intersect.

It is also interesting to note that on a sphere parallel transport is really the same as rotation! (Awesome… I know!) So where to rotate… well you can probably figure it out by simply looking at the sphere, but we want to try and put it in writing.Β  In order to find the axis to rotate on we have to imagine vectors going from the center of our sphere to the two end points that define our line of transport. Lets call those vectors a and b. Then, we take do: a x b (a cross b) and get some vector c. If we place vector c at the center of the sphere then we get our axis of rotation. Let call this primary axis just so we have name for it

So in the context of Spheriosity I want to take a line of transport, a line to transport and a cursor location and transport the ‘line to transport’ to where the cursor is, but making sure it is with respect to the ‘line of transport’. Translating the cursor location to a line parallel transporting is not a one step process, sadly. Since I don’t know where the cursor will be I had to find a way to map out the cursor location to the line being transported. [A big thanks to my professor who figured this one out]

  1. We use the point provided by the user and the axis of rotation for the line of transport to give us a new axis of rotation. Just to have some order here lets call the user point U, the first axis of rotation primary axis, the line of transport line AB, original line we are transporting line CD, and the new axis of rotation secondary axis
  2. Next we measure the angle between the primary axis and the vector defined from the center of the sphere to point C
  3. Now plot the point which is the intersection of the axis of rotation with the sphere. There are two poential points, so plot whichever one you wish. We will call this point E. Rotate point E with the secondary axis by the angle computed from step 2
  4. Now the first point is in place. We will call this point F. We measure the angle between the vectors defined by going from the center of the sphere to point F and point C.
  5. Using the angle from step 4 we rotate point D using the primary axis
  6. Enjoy the glory of seeing the line parallel transported

There are actually some problems with that method. The first of which is figuring out which direction to rotate point D. The .angle() function of the Vector3f class in Java3D only returns an angle from 0 to PI. The way I figure this out is actually by use of tangent vectors and dot products. To get the tangent vector I actually cheat and only approximate the angle vector by rotating the point C a very small amount (.0001 radians) with the primary axis and use the original point C and the rotated point C to make my vector (vector t). Yes, a crude trick, but it’s quick and easy. Next I define a vector from the center of the sphere to the point the cursor is at (vector c). I take the dot product of t and c,Β  and if the dot product is negative I know to take the angle from .angle() and rotate that in the opposite direction. Perhaps I will write a separate entry and how the dot product is my hero, but for now you will have to trust that it makes sense πŸ™‚ .

The last issue, which I just discovered today, is that if the line we want to transport has one of it’s endpoints as the axis of rotation the aforementioned method does not work. So I simply special case this, and rotate the end point which isn’t the axis of rotation(point D) by the angle formed by the vectors made from the center of the sphere to the cursor point, and point D. Then I use the same tangent vector trick to figure out which way to rotate.

That’s all for now. Hopefully you at least understand parallel transport a little better :). Please let me know if some of that was unclear and I will do my best to make it sound better.

Spheriosity Alpha 2 Finally Released

July 4, 2008

For at least the next month or so there will be quite a few articles that at least mention Spheriosity. I’m not sure if I’ve mentioned this, but it is my project for the summer. I am trying to make it the best application that I can, given my time frame. I have to say that I have made it further in development than I ever thought I would. I find this quite pleasing and I hope to keep up the pace for the rest of the summer. I have a vacation in there and I imagine that development will slow, or stop, during that time. That is a bit of a shame, but I think it is probably for the best. It will be good for me to take a break and not have to work on ANYTHING. Hopefully I will be able to enjoy that as I sometimes find it rather difficult to truly enjoy free time.

At any rate, this post is about Spheriosity. So… what is new in this version? Basically loads of new features and one giant memory leak. Yes yes, a memory leak in Java. I know, it’s not possible! IT IS. I will talk about that some other time. So here is a rough list of the new features I have added:

  • Parallel Transport
  • Point Rotation
  • Full support for saving files (not supported in applet, because it can’t be)
  • Point moving
  • Small interface improvements
  • Ability to measure triangle area as a % of total spherical area.

There are even more features than I listed, but I would consider those the main and most notable features. I have to say that I was a little reluctant to release Spheriosity in alpha status, but I want it to be out there for people to try and test. I one heard the saying ‘release early and release often’. As long as users are willing to put up with the bugs I think it is better to get their feedback. After all… who is using your software? Though Spheriosity is small and I wouldn’t say it even has a real user base I care immensely about what users think about it. I don’t even know if it would be possible for me to use the program to its fullest potential. As such I want to know what others think about it.

In terms of the documentation I wrote about yesterday. I finished that all up and released that as a rough draft under the GNU FDL. I must admit that I didn’t really want to license the documentation mainly because I find it to be quite a hassle. However it is only a one time cost so I figure it is for the best. I really want to make sure people can use the program πŸ™‚ Funny how I think that right?

I got to do a little shell scripting and made myself a little bash script to collect the files from the repository and build all of the .zip and .tar.gz files that I need to post on SourceForge. That was one of those times that I was soooooo glad I had thought ahead to write a script. This time around all I had to do was make some minor changes and it was so nice to just run a small script and it do 90% of the work for me.

I leave now with a screen shot I made from the new application. To make the screen shot I used the parallel transport and rotate point features that are included in the new version. You can’t tell from just looking at the picture, but if you move point B both ‘eyes’ move the same way. I thought it was a real cool example of what the work I have done is capable of. Granted… it is not a very practical use of the software, but that is another story. Maybe some day I will write about parallel transport and how we (my professor and I) were able to achieve this in Spheriosity πŸ™‚ At any rate here is that screen shot:

Screenshort From Spheriosity Alpha 2

Screenshort From Spheriosity Alpha 2