See where two ellipses intersect in C#, Part 1

See where two ellipses intersect

This example shows how you can see where two ellipses intersect.

Surprisingly, some of the most popular posts on the C# Helper web site are not about C# itself. Instead they are about geometry. I decided to add to this category by writing some examples that find other intersections with ellipses such as finding circle/ellipse and ellipse/ellipse intersections.

Unfortunately it turns out that finding those intersections is fairly hard. There are some special cases where you can find exact solutions reasonably easily, such as when two ellipses are aligned with the X and Y axes and have centers with the same X or Y coordinate, but in general this is pretty hard.

After some digging around, I decided on an approach that would work. It turned out that the approach could solve a more general problem: calculating the points of intersection between two conic sections: ellipses, circles (which are a special kind of ellipse), parabolas, and hyperbolas.

The approach is somewhat long and involved so I’m going to spread it across a few posts rather than making one big long post. (I also don’t have time to write it all at once.) These posts are fairly mathematical so if you’re afraid of equations, you might want to just skim them before your eyes glaze over. In this post, I’ll outline the basic approach.

Approach

The post Calculate the formula for an ellipse selected by the user in C# explains how to get the formula for an ellipse in either this format:




or this format:



This second format is also the general form for the equations for all conic sections. You can determine the kind of the conic section by calculating this equation’s determinant B2 – 4 * A * C. If the conic is non-degenerate (in other words, not something weird like a line or point), then:

If B2 – 4AC is: Then the conic is:
< 0 Ellipse
< and A = 0 and B = 0 Circle
= 0 Parabola
> 0 Hyperbola
> 0 and A + C = 0 Rectangular hyperbola


So here’s the approach:

Two conic sections (such as ellipses) are defined by two equations that involve variables x and y that are set equal to 0. In theory you could solve the two equations for the two unknowns x and y. As you’ll see when we get into the equations, this is difficult in practice because the equations are really ugly.

Instead you can solve one equation for x in terms of y and then plug the result into the other equation. This gives you a horrible mess that you cannot easily solve exactly. You can, however, apply Newton’s method (or some other method) to find the places where this messy equation equals 0. The values of x and y for which the equation is 0 are the points where the conic sections intersect.

The combined messy equation involves taking square roots in two places, so you can get up to four solutions depending on whether you use the positive or negative roots in those two places. This makes sense because two ellipses can intersect in 0, 1, 2, or 4 points as shown in the picture on the right. (Other conic sections can also intersect in at most four places.)

In my next post, time I’ll dig into the math and show you the messy equation.


Download Example   Follow me on Twitter   RSS feed   Donate




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

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

  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 *