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

This post explains why Newton's method may not be the best way to find the roots of the difference equations used to see where two ellipses intersect.

The final step in finding the points of intersection between two ellipses (or conic sections in general) is using Newton's method to find the roots of some difference equations. The way Newton's method works is you start with an X coordinate. You evaluate the function and its derivative for that X value to find a line tangent to the equation's curve. You determine where the tangent line intersects the X axis and you use that point of intersection as a new estimate of where the root is. You repeat this step a bunch of times until the point you are considering is sufficiently close to the root.

The picture on the right shows the process. The point x0 is the initial guess for the root. You find the tangent line and determine where it intersects the X axis at point x1. The point x1 becomes the next guess for the root's value.
Often Newton's method quickly converges on a root, but sometimes it produces some strange behavior. For example, suppose the function has a negative second derivative (curvature) so its tangent lines have decreasing slope as you move to the right along the curve, as shown in the picture on the right. In that case, the tangent line used by Newton's method may lead to a new X coordinate where the curve isn't defined. In this situation, Newton's method doesn't find the root.

Unfortunately this situation seems to arise fairly often with the difference curves used to find the points of intersection between conic sections. If you look at the difference curves in the picture at the top of this post, you'll see that the red curve has this sort of shape. The orange curve has a fairly small second derivative so Newton's method may find that root, but it may not find the root where the red curve intersects the X axis.
An alternative to Newton's method is binary subdivision. Here you pick two X coordinates x0 and x1 that you think surround a root of the equation. You evaluate the function at those x coordinates. If a root lies between them, then the value for one of those coordinates should be positive and the other should be negative. If that's the case, then you calculate x2 = (x0 + x1) / 2 in the middle of the other points and you evaluate the function there. You then repeat the process using the middle point and whichever of the original values lies on the opposite side of the line y = 0.

In the picture on the right, F(x0) < 0 and F(x1) > 0, so there should be a root between those points. For the middle point, F(x2) > 0, so the root lies between x0 and x2.

You repeat this process until the function's value at the points you are considering is close enough to 0.

Newton's method usually converges more quickly than the binary subdivision method when it works, but binary subdivision handles cases such as negative curvature better than Newton's method does.
However, there are still some odd cases to consider. For example, suppose the curve is vertical at the root as shown in the picture on the right? In that case, there is no point on the curve to the left of the root that you can use for point x0. Unless your guess for x0 happens to hit the root exactly, you won't find the root.

You can modify the method to handle this situation if you consider undefined values to be on the opposite side of the X axis for any other defined value. In the picture on the right, you would assume there is a root between points x0 and x1 because the function is undefined for one of the points and not for the other. (If the function is undefined for both points, then you assume they are both off the left or right side of the curve and there is no root between them.)

Click the Download button below to download an example that uses binary subdivision instead of Newton's method. Look at the code to see the details of how it works.

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