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

The parameterized equation for a line segment through the points (x_{1}, y_{1}) and (x_{2}, y_{2}) 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_{1} and y = y_{1} so the equations return the first end point. When `t` = 1.0, the equations give x = x_{2} and y = y_{2} 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^{2}, `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^{2}-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.

Download the example program and look at the code to see how the form’s `Paint` event handler draws the line, ellipse, and intersections.

Hi Rod,

Looks like this algorithm is only valid for an ellipse whose major axis has no slope. How could you make it work for rotated ellipses? Would you need to rotate the ellipse (and line segment & bounding rectangle) about the ellipse center before doing the calculation? Or is there an easier way? For performance reasons, I was hoping to avoid trig functions.

thanks,

Jim

Thanks for the information!

To handle rotated ellipses I used Transform from System.Windows.Media to rotate the points first e.g.

Transform rotate = new RotateTransform(-ellipse.MinorAxisAngle,center.X,center.Y);

pt1 = rotate.Transform(pt1);

pt2 = rotate.Transform(pt2);

To rotate the points to the rectangle rotation

then rotated them back afterwards and that worked like a charm

James

That’s a good solution. I think that’s how you would do it mathematically. You would just do the transformation yourself instead of using a

RotateTransformobject. (Although the object is a lot easier!)I have two buttons (Button A & Button B). They are movable on form, I want to connect them by using arrow. When drag one button the length of the connecting arrow will adjust and keep connecting two buttons. It should be something like connecting two rectangles by using arrow in excel.

This isn’t really a good post for this question.

You should be able to do that. For example, you might just draw a line from the middle of the right edge of one button, to the middle of left edge of the other button. If you want to make the lines only draw vertically and horizontally, draw horizontally halfway, then move vertically to the second button’s mid point, and then finish drawing horizontally.

To draw arrowheads, see the post Draw lines with arrowheads in C#.

See: “2D Collision Detection for Game Programmers: Focus on Ellipse Collisions” on Amazon.com for a detailed answer to this question.

This question is not easily answered. There are 3 types of collision algorithms that may be written: Static, Semi-Dynamic, and Dynamic. Most of the discussions here were for Static collisions. Static collisions are when the algorithm assumes that the two objects are static, or not moving, even it they are actually moving. Semi-Dynamic collision algorithms account for object A moving, but assumes object B is static. Dynamic collision algorithms take into account that both objects are moving.

Static collision algorithms return only if a collision has occurred. The programmer only has the location of the objects to use for collision response. This is limiting, but sufficient for many games. Games like “Space Invaders” may be written using the algorithm. It is important to note that the static algorithms can have issues with small fast moving objects. Care must be taken to insure these objects cannot skip over each other in a single frame.

Semi-Dynamic collision algorithms return if a collision has occurred, The mathematical intersection point, the intersection time, the collision point (Where the two objects touch), and the collision normal. These algorithms take more time to execute, but return more information to allow for a wide variety of collision responses. This is the recommended algorithm I would use for most games. Games like “Break Out” may be written using this algorithm.

Dynamic collision algorithms return if a collision has occurred, the mathematical intersection point, the point where object A is at collision, the point where object B is at collision, the collision point, the collision normal for object A, and the collision normal for object B. This algorithm is the slowest to execute, but gives all the collision response details possible. This algorithm would be suitable to a “Break Out” like game that has multiple ball and if the balls collide they bounce off each other. Typically “Break Out” like game do not have the balls interacting with each other, therefore, the balls can occupy the same location with no response. This is not realistic, but how it is usually done.

The process for building the algorithms is fairly simple, but filled with a lot of repeating detail that make it cumbersome. The algorithms can be broken down into the following steps:

1) Identify the 2 objects to test for a collision

2) Create the collision area.

3) Test if the control point collides with any of the objects that make up the collision area. Divide and conquer decisions should be used to maximize efficiency.

The collision area is a composite of the 2 objects colliding. To create the collision object take object A and transcribe object A around object B. In the case of a circle colliding with an AABB, the collision area will have 4 circles at its corners, and 4 segments connecting the circles at their outer tangent points.

There is insufficient space in this blog give the algorithms in detail, but in the book “2D Collision Detection Algorithms for Game Programmers: Focus on Circle Collisions” will explain all 3 collision types for circles colliding with Points, Lines, Horizontal Lines, Vertical Lines, Rays, Segments, Circles, Ellipses, Axis Aligned Bounding Boxes (AABB), Object Oriented Bounding Boxes (OOBB), Capsules, and Polygons. I highly recommend this book.

You may also be interested in my other books also, they may be found at Amazon.com:

1) “2D Collision Detection for Game Programmers: Focus on Point Collisions”

2) “2D Collision Detection for Game Programmers: Focus on Circle Collisions”

3) “2D Collision Detection for Game Programmers: Focus on Ellipse Collisions”

In print soon:

4) “2D Collision Detection for Game Programmers: Focus on Axis Aligned Bounding Box (AABB) Collisions”

5) “2D Collision Detection for Game Programmers: Focus on Object Oriented Bounding Box (OOBB) Collisions”

6) “2D Collision Detection for Game Programmers: Focus on Capsule Collisions”

7) “2D Collision Detection for Game Programmers: Focus on Polygon Collisions”

8) “2D Collision Detection for Game Programmers: Focus on Collision Response”

Good luck with your game.