[Beginning Database Design Solutions, Second Edition]

Title: See where two ellipses intersect in C#, Part 2

This post shows The Ugly Math that you can use to see where two ellipses intersect. Brace yourself! Here it comes!

First recall the quadratic formula. If ax² + bx + c = 0, then:

Now consider the formula for a conic section:

You can rewrite this to group terms of x like this:

Plugging the terms into the quadratic formula gives the following equation, which we'll call G₁(y):

(Starting to get messy, isn't it?)

Notice that the equation contains a square root that can be positive or negative. Let be the equation with the positive root and let be the equation with the negative root.

Now consider a second conic section defined by:

The equation for this conic section is:

Again define two equations

and

to represent this equation with the positive and negative square roots.

The two curves intersect where they have the same x and y values. In other words, those points have x coordinates where G₁(x) = G₂(x) or G₁(x) � G₂(x) = 0.

Considering all four combinations of positive and negative roots in the equations gives these four equations:

If you solve these four equations for x, you'll find between zero and four points of intersection for the ellipses.

Note that some of the equations may contain square roots of negative numbers and in those cases they don't have real solutions. Note also that one of the equations might have more than one root. For example, in the picture on the right, the bottom of the red ellipse overlaps the top of the blue ellipse. If the red ellipse is ellipse number 1, then the bottom of the red ellipse is generated by equation and the top of the blue ellipse is generated by equation . That means both points of intersection are generated by the equation .

Note also that one or both of the equations might have duplicate roots. In other words, it might use the same value for both of its roots. For example, imagine two ellipses that intersect at four points. Now slowly pull one to the side. Two of the points of intersection grow closer and closer until they coincide. At that point, one of the equations has two roots and the other has a repeated root.

Unfortunately the four equations that define the points of intersection are really messy. For example, equation (1) is:

I don't know of a closed-form solution to this equation, but all is not lost! You can use Newton's method to find an approximation for the values of x that solve the equation.

To use Newton's method to find the roots (zeros) of an equation, you need to find the derivative of that equation. The derivative of G₁(x) is given by:

The derivative of the difference of two functions is the difference of the derivatives. For example, the following equation shows the derivative of equation (1).

Now you can use equations (1) through (4) and their derivatives to apply Newton's method and look for roots.

Simple isn't it? Well... not really. See the post Use Newton's method to find the roots of equations in C# for information about Newton's method.

In the next post, I'll summarize this method for finding intersections between conic sections and explain what the program shown in the picture at the top of this post actually does.

Download the example to experiment with it and to see additional details.