The FindLineCircleIntersections method shown shortly finds the points where line intersects a circle. It takes as parameters a circle’s center point and radius, and two points on the line. It uses out parameters to return the coordinates of the points of intersection. The method returns the number of points of intersection (0, 1, or 2).
To find the points of intersection, the code considers the line as generated by the equations:
X(t) = x1 + (x2 - x1) * t Y(t) = y1 + (y2 - y1) * t
Where t ranges from 0 to 1 to generate the points on the line segment.
The code plugs those two equations into the following equation for a circle:
(X - Cx)2 + (Y - Cy)2 = radius2
It then solves for t by using the quadratic formula. The result is 0, 1, or 2 real values for t depending on whether the line cuts through the circle, touches it tangentially, or misses it entirely. The method plugs those values back into the equations for the line to get the points of intersection.
Here’s the FindLineCircleIntersections method.
// Find the points of intersection.
private int FindLineCircleIntersections(
float cx, float cy, float radius,
PointF point1, PointF point2,
out PointF intersection1, out PointF intersection2)
{
float dx, dy, A, B, C, det, t;
dx = point2.X - point1.X;
dy = point2.Y - point1.Y;
A = dx * dx + dy * dy;
B = 2 * (dx * (point1.X - cx) + dy * (point1.Y - cy));
C = (point1.X - cx) * (point1.X - cx) +
(point1.Y - cy) * (point1.Y - cy) -
radius * radius;
det = B * B - 4 * A * C;
if ((A <= 0.0000001) || (det < 0))
{
// No real solutions.
intersection1 = new PointF(float.NaN, float.NaN);
intersection2 = new PointF(float.NaN, float.NaN);
return 0;
}
else if (det == 0)
{
// One solution.
t = -B / (2 * A);
intersection1 =
new PointF(point1.X + t * dx, point1.Y + t * dy);
intersection2 = new PointF(float.NaN, float.NaN);
return 1;
}
else
{
// Two solutions.
t = (float)((-B + Math.Sqrt(det)) / (2 * A));
intersection1 =
new PointF(point1.X + t * dx, point1.Y + t * dy);
t = (float)((-B - Math.Sqrt(det)) / (2 * A));
intersection2 =
new PointF(point1.X + t * dx, point1.Y + t * dy);
return 2;
}
}
Click and drag to draw the line segment. The main program uses the FindLineCircleIntersections method to find the points of intersection (if any). It then draws the segment you selected and the points of intersection. If the points don't lie on the segment, it extends the segment through the points with a dashed line.
![[Essential Algorithms, Second Edition]](http://www.csharphelper.com/essential_algs_2e_158_200.jpg)
![[WPF 3d, Three-Dimensional Graphics with WPF and C#]](http://www.csharphelper.com/wpf3d_160_200.png)
![[The C# Helper Top 100]](http://www.csharphelper.com/top100_161_200.png)
![[Interview Puzzles Dissected]](http://www.csharphelper.com/interview_puzzles_161_200.jpg)
Thanks for your solution! It is very helpful for me.
When I set breakpoints in Visual Studio on the return statements, “return 1” never executes. Even if there is logically only one intersection with the circle for a given line segment, the code returns 2 points and the display draws 2.
The problem is that there is one intersection only if the segments is exactly tangent to the circle and the determinant is exactly 0. If it’s even a tiny bit off, then there are either two or zero intersections.
It’s hard to select the points exactly to get that to happen interactively, but you can do it with code. Even then, rounding errors might not make the determinant exactly 0.
If you want to handle a larger number of cases as single intersections, you could change the code to see if Math.Abs(det) < 0.01 or some other small cutoff value. If you do that, then the program should treat two intersections that are close together as one.
Another solution to exclude tangent issues is to calculate the distance between the circle’s center and the line. Then compare the result with the circle radius with a precision parameter:
Point closestPoint; //You can find easily an algorythme for that distFromCircle = FindDistanceToSegment( (Segment)Segment, Circle.Center, out closestPoint); (AreEqualsValues(distFromCircle, Circle.Radius, Precision)) det = 0; //precision = 0.000001If the determinant is 0, then there is only one solution.
here is the comparator:
public static bool AreEqualsValues(double value1, double value2, double precision) { return (Math.Abs(value1 - value2) < precision); }