Determine where two lines intersect in C#

This example determines whether two segments intersect and where the lines that contain them intersect. There are several ways you can approach this problem. This example uses lines defined by parametric equations where 0 <= t1, t2 <= 1. If the first segment has end points (x11, y11) and (x12, y12), and the second segment has end points (x21, y21) and (x22, y22), then the line segments are defined by the following functions:

```X1(t) = x11 + dx1 * t1
Y1(t) = y11 + dy1 * t1
X2(t) = x21 + dx2 * t2
Y2(t) = y21 + dy2 * t2```

In other words, as the value of t1 varies from 0 to 1, (X1(t), Y1(t)) give the points along the first segment.

When the two segments intersect, the points (X1(t1), Y1(t1)) and (X2(t2), Y2(t2)) are the same. Setting the equations for the points equal gives:

```x11 + dx1 * t1 = x21 + dx2 * t2
y11 + dy1 * t1 = y21 + dy2 * t2```

You can rearrange those equations to get:

```x11 - x21 + dx1 * t1 = dx2 * t2
y11 - y21 + dy1 * t1 = dy2 * t2```

And then:

```(x11 - x21 + dx1 * t1) *   dy2  = dx2 * t2 *   dy2
(y11 - y21 + dy1 * t1) * (-dx2) = dy2 * t2 * (-dx2)```

```(x11 - x21) * dy2 + ( dx1 * dy2) * t1 +
(y21 - y11) * dx2 + (-dy1 * dx2) * t1 = 0```

Now solving for t1 gives:

```t1 * (dy1 * dx2 - dx1 * dy2) =
(x11 - x21) * dy2 + (y21 - y11) * dx2```
```t1 = ((x11 - x21) * dy2 + (y21 - y11) * dx2) /
(dy1 * dx2 - dx1 * dy2)```

You can solve for t2 similarly.

Notes:

• If 0 <= t1 <= 1, then the point lies on the first segment.
• If 0 <= t2 <= 1, then the point lies on the second segment.
• If dy1 * dx2 - dx1 * dy2 = 0, then you can’t calculate t1 or t2 (it would require dividing by 0), and the lines are parallel.
• If the point of intersection is not on both segments, then this is almost certainly not the point where the two segments are closest.

The FindIntersection method shown in the following code finds the intersection between the lines that contain the segments p1 --> p2 and p3 --> p4.

```// Find the point of intersection between
// the lines p1 --> p2 and p3 --> p4.
private void FindIntersection(
PointF p1, PointF p2, PointF p3, PointF p4,
out bool lines_intersect, out bool segments_intersect,
out PointF intersection,
out PointF close_p1, out PointF close_p2)
{
// Get the segments' parameters.
float dx12 = p2.X - p1.X;
float dy12 = p2.Y - p1.Y;
float dx34 = p4.X - p3.X;
float dy34 = p4.Y - p3.Y;

// Solve for t1 and t2
float denominator = (dy12 * dx34 - dx12 * dy34);

float t1 =
((p1.X - p3.X) * dy34 + (p3.Y - p1.Y) * dx34)
/ denominator;
if (float.IsInfinity(t1))
{
// The lines are parallel (or close enough to it).
lines_intersect = false;
segments_intersect = false;
intersection = new PointF(float.NaN, float.NaN);
close_p1 = new PointF(float.NaN, float.NaN);
close_p2 = new PointF(float.NaN, float.NaN);
return;
}
lines_intersect = true;

float t2 =
((p3.X - p1.X) * dy12 + (p1.Y - p3.Y) * dx12)
/ -denominator;

// Find the point of intersection.
intersection = new PointF(p1.X + dx12 * t1, p1.Y + dy12 * t1);

// The segments intersect if t1 and t2 are between 0 and 1.
segments_intersect =
((t1 >= 0) && (t1 <= 1) &&
(t2 >= 0) && (t2 <= 1));

// Find the closest points on the segments.
if (t1 < 0)
{
t1 = 0;
}
else if (t1 > 1)
{
t1 = 1;
}

if (t2 < 0)
{
t2 = 0;
}
else if (t2 > 1)
{
t2 = 1;
}

close_p1 = new PointF(p1.X + dx12 * t1, p1.Y + dy12 * t1);
close_p2 = new PointF(p3.X + dx34 * t2, p3.Y + dy34 * t2);
}```

This method takes as parameters the points that define the segments and the following output parameters to return results:

• lines_intersect – True if the lines containing the segments intersect
• segments_intersect – True if the segments intersect
• intersection – The point where the lines intersect
• close_p1 – The point on the first segment that is closest to the point of intersection
• close_p2 – The point on the second segment that is closest to the point of intersection

First the code calculates dx12, dy12, and the other values that define the lines. It then plugs the values and the points’ coordinates into the equation shown earlier to calculate t1. If the results is infinity, then the denominator is 0 so the lines are parallel.

Next the code uses the values of t1 and t2 to find the points of intersection between the two lines.

If t1 and t2 are both between 0 and 1, then the line segments intersect.

The code then adjusts t1 and t2 so they are between 0 and 1. Those values generate the points on the two segments that are closest to the point of intersection. Finally the code uses the adjusted values of t1 and t2 to find those closest points.

To use the example, click two points to define the first segment. Then click two more points to define the second segment. The program draws the segments. It draws the “close” points in blue and the point of intersection in red. (In the figure above, one of the close points is below the point of intersection so you can’t see it.)

This entry was posted in algorithms, geometry, graphics, mathematics and tagged , , , , , , , , , , , , . Bookmark the permalink.

21 Responses to Determine where two lines intersect in C#

1. Luis Fernando Forero says:
` /// Cordenada X del punto de intersecci`
2. Rod Stephens says:

This is a nice solution. I think the original is somewhat similar, at least in complexity, if you strip out the extra code that handles segments that don’t intersect.

One of the things the example does (which actually I needed when I originally worked on this) is it finds the closest points on the two segments. For example, if the segments don’t intersect, then the closest points on the segments might be at one of the segment’s end points and in the middle of the other segment. (That’s why this example goes through all the trouble of parameterizing the two segments and finding t1 and t2.)

3. sizy458 says:

This function ‘FindIntersection’ work good!

4. David says:

Thanks for this c# method! It really works!

5. Daniele says:

How can I substitute the “float.IsInfinity(t1)” check to use it with decimal type? I’m porting the code to use decimal and that function is missing, please help

• RodStephens says:

If you divide by zero with the float data type, the program does not throw an exception but instead just sets the result to infinity. The program throws an exception if you try to divide a decimal by zero.

So what you need to do is protect the code that could divide by zero with a try-catch block.

6. Carlos says:

Supah Doopah! Works great. Thanking you!

7. Dale O Hays says:

Thanks a bunch . . . exactly what I was looking for. I especially like the “closest points” addition. Nice work!

8. Steve Harrison says:

Great, that was a big help. My maths skills let me down!

9. vicky says:

it’s perfectly suits to 2d lines well , wowwww
But i want the same in 3d lines is it possible? then how to do it?

• RodStephens says:

It should be basically the same calculation except you have (x1, y1, z1) and (x2, y2, z2). You still solve for t1 and t2.

Note that it is much less likely that two “random” lines will intersect in 3D. In 2D two lines will intersect unless they are parallel. In 3D one can pass “under” the other so they are likely to not intersect.

10. Clint Phillips says:

Is there a way to use this to determine if a line (based on a grid) is over another line and split the line. Say a line goes (0,0) to (0,3) and then draw a line (1,0) to (2,0) to delete the middle part. To include diagonal lines. Trying to find a way to erase portions of lines.
Thanks!

• RodStephens says:

Do you mean to make a gap so it looks like the lower line goes under the upper one? You should be able to do that.

Find the point of intersection. Then make a vector pointing in the direction of the lower line and give it length equal to half of the amount that you want to remove. Move that distance away from the point of intersection in both directions.

It may be easier to just draw the upper line using the background color to erase the part of the upper line where they cross and then draw the upper line again normally.

11. Clint Phillips says:

I really liked your article and its an awesome feature. Its not what I’m trying to do though.
Many Thanks!

• Clint Phillips says:

Edit: The lines with gaps article. This one too! And your whole blog!

• RodStephens says:

Rats! Can you explain a bit more about what you want to do? Or perhaps post a picture? (Or email a picture if that’s easier.)