[Beginning Database Design Solutions, Second Edition]

Title: See where a line intersects a conic section in C#

See where a line intersects a conic section

This example shows how you can see where a line intersects a conic section. You can use the more general method described in the post See where two conic sections intersect in C#. This example takes advantage of the simpler equation for a line to calculate solutions directly instead of relying on Newton's method (or binary subdivision) to approximate the solutions.

Left-click to select five points that define a conic section. See the example Select a conic section in C# for information about how that works. Right click to select two points that define the line. When you have selected a conic section and a line, the program draws them and their intersections.

Here's the math that makes it work.

The parameterized equation for a line segment through the points (x₁, y₁) and (x₂, y₂) is:

Where:

And the parameter t ranges over the values 0.0 to 1.0. For example, when t = 0.0, the equations give x = x₁ and y = y₁, so the equations return the first end point. When t = 1.0, the equations give x = x₂ and y = y₂, so the equations return the second end point.

The general equation for a conic section is:

Depending on the values of A, B, C, D, E, and F, this might be an ellipse (possibly even a circle), parabola, or hyperbola.

If you plug the equations for the line into the equation for the conic section, you get:

If you multiply out the things inside parentheses, you get: See where a line intersects a conic section

Now grouping the t², t, and constant terms gives you: See where a line intersects a conic section

This is a quadratic equation of the form: See where a line intersects a conic section

Where:

This may look intimidating, but all of the values in the definitions of a, b, and c are just numeric values that the program knows from the definitions of the particular conic section and line segment. That means you can plug them into the quadratic equation to find the values of t that satisfy the equation: See where a line intersects a conic section

The value inside the radical b² - 4ac is called the determinant. The number of real solutions to the equation depends on whether the determinant is positive, negative, or zero:

determinant < 0: There are no real solutions.
determinant = 0: There is one solution.
determinant > 0: There are two solutions.

That's all there is to it! The example program uses the following code to find the intersection between a conic section with coefficients A, B, C, D, E, and F, and the line containing the points pt1 and pt2.

// Find the points of intersection between // a conic section and a line. private List<PointF> IntersectConicAndLine( float A, float B, float C, float D, float E, float F, PointF pt1, PointF pt2) { // Get dx and dy; float x1 = pt1.X; float y1 = pt1.Y; float x2 = pt2.X; float y2 = pt2.Y; float dx = x2 - x1; float dy = y2 - y1; // Calculate the coefficients for the quadratic formula. float a = A * dx * dx + B * dx * dy + C * dy * dy; float b = A * 2 * x1 * dx + B * x1 * dy + B * y1 * dx + C * 2 * y1 * dy + D * dx + E * dy; float c = A * x1 * x1 + B * x1 * y1 + C * y1 * y1 + D * x1 + E * y1 + F; // Check the determinant to see how many solutions there are. List<PointF> solutions = new List<PointF>(); float det = b * b - 4 * a * c; if (det == 0) { float t = -b / (2 * a); solutions.Add(new PointF(x1 + t * dx, y1 + t * dy)); } else if (det > 0) { float root = (float)Math.Sqrt(b * b - 4 * a * c); float t1 = (-b + root) / (2 * a); solutions.Add(new PointF(x1 + t1 * dx, y1 + t1 * dy)); float t2 = (-b - root) / (2 * a); solutions.Add(new PointF(x1 + t2 * dx, y1 + t2 * dy)); } return solutions; }

This method simply plugs its parameters into the equations shown earlier. Depending on the value of the determinant, the method adds 0, 1, or 2 points to the the solution list and returns the solutions.

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