See where two ellipses intersect in C#, Part 3

See where two ellipses intersect

This post summarizes the method you can use to see where two ellipses intersect. (Or any two conic sections, for that matter.) It also explains the example program.

To find the points of intersection:

  1. Get the equations for the ellipses.
  2. Solve the equations for y in terms of x. Call the resulting equations G(x). There are four such equations, two per ellipse, depending on whether you take the positive or negative square roots in the equations.
  3. Subtract each pair of equations for one ellipse from those of the other ellipse and set the result equal to 0. I call the resulting four equations the problem’s “difference equations.”
  4. Use Newton’s method or some other method to find the zeros (roots) of the difference equations.
  5. Use equations for the ellipses and the x coordinates given by Newton’s method to find the points of intersection.

To use the example program, click and drag the left and right mouse buttons to select two ellipses.

In the text box, the program displays the coefficients used by the ellipses’ equations.

Below the text box the program draws the four difference equations in different colors. The horizontal black line is y = 0 so the places where the curves intersect that line are the roots of the difference equations (what Newton’s method gives you). Those points give the X coordinates for the ellipses’ points of intersection.

Newton’s method requires you to calculate the derivative of the difference equations. The derivative at a point gives a curve’s slope at that point. To check that my derivative equations are correct, you can click on the picture of the difference equations. The program uses the derivative function to draw the lines tangent to the curves for that X coordinate. If the derivative equations are correct (and they seem to be), then the lines should really be tangent to the curves.

Notice that the circled roots in the bottom picture line up with the points of intersection in the top picture. That’s because they have the same X coordinates.

Take some time to experiment with the program to see how it works. I think the shapes of the difference curves for different numbers of points of intersection are fairly interesting. For example, the picture on the right shows the case where the ellipses have four points of intersection.

See the post Use Newton’s method to find the roots of equations in C# for information about Newton’s method.

In my next post (the last one in this series), I’ll talk a bit about why Newton’s method may not be the best way to find the roots of the difference equations.

Download Example   Follow me on Twitter   RSS feed   Donate

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

Leave a Reply

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