Title: Calculate where a line segment and an ellipse intersect in C#

Finding the intersection between a line segment and an ellipse requires a lot of mathematics. It's not particularly hard mathematics, but if you'd rather skip it, you can use the following links to jump to the other parts of this post.

• Mathematics
• Intersection Code
• Selecting Lines and Ellipses

Mathematics

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

where 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 following is the equation for an ellipse centered at the origin:

Here a and b are lengths of the semimajor axis (half the width) and semiminor axis (half the height) respectively.

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

You can multiply this out to get:

Grouping the t², t, and constant terms gives you:

This is a quadratic equation of the form:

Where:

Note that 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 line segment and ellipse. That means you can plug them into the quadratic equation to find the values of t that satisfy the equation:

The value B²-4AC is called the determinant and 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 (the line and ellipse do not intersect)
• determinant = 0: There is one solution (the line and ellipse are tangent)
• determinant > 0: There are two solutions (the line crosses the ellipse)

This program simply uses these equations. It plugs numbers into the equations for A, B, and C, calculates the determinant, and then finds whichever solutions are possible.

Intersection Code

The FindEllipseSegmentIntersections method shown in the following code finds intersections between line segments and ellipses.

// Find the points of intersection between // an ellipse and a line segment. private PointF[] FindEllipseSegmentIntersections( RectangleF rect, PointF pt1, PointF pt2, bool segment_only) { // If the ellipse or line segment are empty, return no intersections. if ((rect.Width == 0) || (rect.Height == 0) || ((pt1.X == pt2.X) && (pt1.Y == pt2.Y))) return new PointF[] { }; // Make sure the rectangle has non-negative width and height. if (rect.Width < 0) { rect.X = rect.Right; rect.Width = -rect.Width; } if (rect.Height < 0) { rect.Y = rect.Bottom; rect.Height = -rect.Height; } // Translate so the ellipse is centered at the origin. float cx = rect.Left + rect.Width / 2f; float cy = rect.Top + rect.Height / 2f; rect.X -= cx; rect.Y -= cy; pt1.X -= cx; pt1.Y -= cy; pt2.X -= cx; pt2.Y -= cy; // Get the semimajor and semiminor axes. float a = rect.Width / 2; float b = rect.Height / 2; // Calculate the quadratic parameters. float A = (pt2.X - pt1.X) * (pt2.X - pt1.X) / a / a + (pt2.Y - pt1.Y) * (pt2.Y - pt1.Y) / b / b; float B = 2 * pt1.X * (pt2.X - pt1.X) / a / a + 2 * pt1.Y * (pt2.Y - pt1.Y) / b / b; float C = pt1.X * pt1.X / a / a + pt1.Y * pt1.Y / b / b - 1; // Make a list of t values. List<float> t_values = new List<float>(); // Calculate the discriminant. float discriminant = B * B - 4 * A * C; if (discriminant == 0) { // One real solution. t_values.Add(-B / 2 / A); } else if (discriminant > 0) { // Two real solutions. t_values.Add((float)((-B + Math.Sqrt(discriminant)) / 2 / A)); t_values.Add((float)((-B - Math.Sqrt(discriminant)) / 2 / A)); } // Convert the t values into points. List<PointF> points = new List<PointF>(); foreach (float t in t_values) { // If the points are on the segment (or we // don't care if they are), add them to the list. if (!segment_only || ((t >= 0f) && (t <= 1f))) { float x = pt1.X + (pt2.X - pt1.X) * t + cx; float y = pt1.Y + (pt2.Y - pt1.Y) * t + cy; points.Add(new PointF(x, y)); } } // Return the points. return points.ToArray(); }

The method first makes sure the ellipse and line segment are not empty. If the ellipse has zero width or height, or if the line segment's points are identical, then the method returns an empty array holding no points of intersection.

Next the code makes sure that the rectangle defining the ellipse has a positive width and height. If it doesn't, the code replaces it with a new rectangle that does have a positive width and height. For example, the rectangle with upper left corner (0, 10), width -30, and height -20 is equivalent to one with upper left corner (-30, -10), width 30, and height 20.

The equation for an ellipse shown earlier assumes the ellipse is centered at the origin. The code now subtracts the coordinates to the ellipse's center from the X and Y coordinates of the points and rectangle to center the ellipse at the origin. (Later the code needs to undo this to move everything back.)

Next the code plugs in values. It finds the semiminor and semimajor axes, and plugs those values plus the points' coordinates into the equations for A, B, and C.

The program then creates a list to hold the values for t that it finds. In the end, this list should hold zero, one, or two values.

The code now calculates the discriminant. Depending on whether the discriminant is equal to or greater than zero, the program adds one or two values to the list. (If the discriminant is less than 0, it doesn't add any values to the list.)

Having found the values for t, the program loops over them to convert them into points of intersection. If the final parameter to the method segment_only is true, then the program should only returns points of intersection that are on the segment, not those that are on the extension of the segment. For example, if the segment points towards the ellipse but isn't long enough to touch it, then those points of intersection are not on the segment. A point will be on the segment if its t value is between 0.0 and 1.0.

For a particular value of t, the program converts it into a point and adds it to the points list if segment_only is false (so all points should be part of the output) or if the point lies on the line segment.

After converting all of the t values into points, the method uses the point list's ToArray method to convert the list into an array and returns it.

Selecting Lines and Ellipses

There's one more interesting piece to this example. When you click the Select Line or Select Ellipse button, the program changes the form's cursor to a cross hair and lets you click and drag to select a line or ellipse. Clicking and dragging to select a line, ellipse, or other shape is covered by other blog posts. You use the MouseDown and MouseMove events to track the progress of the click and drag, and you save the selected shape in the MouseUp event.

The difference here is that the program must be able to let you select either a new line or a new ellipse, so you can't simply assign mouse event handlers at design time. Instead the code includes two sets of MouseDown, MouseMove, and MouseUp event handlers. It then installs and uninstalls them as needed at run time.

When you click the Select Line button, the following code starts the line selection process.

// Let the user select a line. private bool SelectingLine = false; private void btnSelectLine_Click(object sender, EventArgs e) { btnSelectLine.Enabled = false; btnSelectEllipse.Enabled = false; this.MouseDown += SelectLine_MouseDown; this.Cursor = Cursors.Cross; }

This code disables the buttons so the user can't click them both or click one more than once while already selecting a line. It then installs the SelectLine_MouseDown method as the form's MouseDown event handler and sets the form's cursor to a cross hair. The following code shows the mouse event handlers used to select a line.

private void SelectLine_MouseDown(object sender, MouseEventArgs e) { SelectingLine = true; this.MouseDown -= SelectLine_MouseDown; this.MouseMove += SelectLine_MouseMove; this.MouseUp += SelectLine_MouseUp; LinePt1 = e.Location; LinePt2 = e.Location; } private void SelectLine_MouseMove(object sender, MouseEventArgs e) { LinePt2 = e.Location; Refresh(); } private void SelectLine_MouseUp(object sender, MouseEventArgs e) { SelectingLine = false; this.MouseMove -= SelectLine_MouseMove; this.MouseUp -= SelectLine_MouseUp; this.Cursor = Cursors.Default; btnSelectLine.Enabled = true; btnSelectEllipse.Enabled = true; Refresh(); }

If you've seen other code for letting the user select a line, this should look familiar. The MouseDown event handler sets a boolean variable indicating that the user is currently selecting a line and records the mouse's position. The MouseMove event handler updates the mouse's position and refreshes the form so it can draw the new selection. The MouseUp event handler sets the boolean value to false to stop the selection process.

That's the basic strategy but there are some new features in this version. The MouseDown event handler installs the MouseMove and MouseUp event handlers. It also uninstalls the MouseDown event handler because the user cannot press the mouse down again when it is already down. The MouseUp event handler uninstalls the MouseMove and MouseUp event handlers and re-enables the Select Line and Select Ellipse buttons.

The Paint event handler draws the line, ellipse, and intersections.

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