See where two ellipses intersect in C#, Part 2

See where two ellipses intersect


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 ax2 + 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 G1(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 G1(x) = G2(x) or G1(x) – G2(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 0, 1, 2, or 4 points of intersections 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 .

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 G1(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.

   

This entry was posted in algorithms, geometry, mathematics and tagged , , , , , , , , , , . Bookmark the permalink.

One Response to See where two ellipses intersect in C#, Part 2

  1. Pingback: Draw a conic section from its polynomial equation in C# -

Leave a Reply

Your email address will not be published. Required fields are marked *