Cubic Bezier-Ellipse Intersection and MuPad
The Cubic Bezier-Ellipse intersection has been added to the Intersection object and samples are in the 2D Intersections area in this site. You’ll see separate examples for Quadratic Bezier and Cubic Bezier and then at the end of the list, you’ll see path examples that use all supported path commands.
The Cubic Bezier-Ellipse intersection involves finding the roots of a sixth degree polynomial. There are no closed-form solutions for polynomials over the fourth degree so you have to resort to root finding algorithms. One method that can be used is bisection and this has been added to the Polynomial object. The Cubic Bezier-Ellipse intersection uses Polynomial’s getRootsInInterval() method. I was pleasantly surprised to find that all of this code runs at a tolerable speed even on my Pentium 100 laptop - not fast, but not too slow to be annoying.
From what I’ve read, bisection is not as fast as Newton’s method. I have all of the pieces written to implement Newton’s method (finding deriviatives of a polynomial and evalulating polynomials at a given x), but I’ll wait to write that when I solve the Cubic Bezier-Cubic Bezier intersection since that involves finding the roots of a ninth degree polynomial.
Only 3 intersections remain. The solutions to these intersections involve finding the intersections of two parametric curves. Once I figure out the solution for one of these intersections, I’ll be able to apply the same technique to solve the other two intersections.
Oh yeah, I should mention that I just discovered what I think is some great math software called MuPad They have a free version for individual use. The UI is all ASCII (like a UNIX terminal) so it isn’t as slick as the Pro version’s GUI, but it does everything I need.
I wish I had discovered this software before I started these intersection problems! MuPad solved algebraic problems that took my hours in just seconds. It supports all kinds of math and is friendlier than Maple and Mathematica are to my budget.