|Posted by Craig on April 23, 2013 at 3:30 AM|
I'm waiting for a 20-hour simulation to finish, which should be finished in about half-an-hour.
In the meantime, I thought I'd put up some code people might be interested in. If you don't much care, or you're not mathmatically inclined, don't worry.
Recently I wanted to write a program that could determine if two ellipses intersected. I had to do a bunch of reading and math and coding. By coding, I mean translating a sixty-year-old computer algorithm into modern C++. That is actually very difficult.
The result was a C++ class called Polynomial. This allows you to solve polynomials upto the 4th degree. Remember quadratic equations in high-school? That's a polynomial of the 2nd degree. And you had the quadratic formula to find the roots of the equation - roots being values you put into the equation such that it equals zero. The quadratic formula is easy to remember. Seriously, teach a primary school kid the basics of algebra and they'll be able to memorise the quadratic formula and not ever forget it.
Now what about the others? 1st degree polynomials are easier. You can do it in your head really. But 3rd and 4th degree, not so much.
Polynomials of 3rd degree are called cubic equations. They take the form ax3+bx2+cx+d (the 3 and 2 are both powers). The cubic formula, for finding roots of these equations, are much more complex than the quadratic one. And let's not get started on quartic equations, polynomials of the 4th degree. The quartic formula would take five pages to write!
You might ask what does this have to do with intersecting ellipses. Well, basically if two ellipses have intersected, there will be at least one point the two ellipses have in common. So, you have the equations for the two ellipses. You have to find points where the two equations are equal. You solve the two simultaneous equations, and you end up with a single quartic equation. Then the question becomes, how do you solve the quartic if the solution formula is so massive and complex?
I had to look around for an algorithm to solve quartic equations, finding one in a journal from 1969, not long before the Apollo 11 landing. Not much explanations to it though. It just had the algorithm and not much else. So I had to translate it into C++, which took me about a week to do, even though the algorithm was only twenty lines long. Ugh! Lots of effort.
So now I have a nice ellipse geometry class that I'm using in a game I'm working on. But I also have an extremely useful class that solves polynomials up to the 4th degree. Above that, that is 5th and up, there is no general formula such polynomials. Even still, this would be very useful for programmers. So I'm putting it up here. It should work just fine with any compiler, since it's pure C++ code using a bit of STL.