Title: Determine where two lines intersect in Python

[The picture shows where the two line segments' extensions intersect]

This example determines whether two line 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)) gives 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)

Adding the equations gives:

(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

Or:

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 find_intersection method shown in the following code finds the intersection between the lines that contain the segments p1 --> p2 and p3 --> p4.

def find_line_intersection(p1, p2, p3, p4): ''' Find the point of intersection between the lines p1 --> p2 and p3 --> p4. ''' # Get the segments' parameters. dx12 = p2[0] - p1[0] dy12 = p2[1] - p1[1] dx34 = p4[0] - p3[0] dy34 = p4[1] - p3[1] # Solve for t1 and t2 denominator = dy12 * dx34 - dx12 * dy34 try: t1 = ((p1[0] - p3[0]) * dy34 + (p3[1] - p1[1]) * dx34) / denominator except ZeroDivisionError: # The lines are parallel (or close enough to it). lines_intersect = False segments_intersect = False intersection = None close_p1 = None close_p2 = None return lines_intersect, segments_intersect, intersection, \ close_p1, close_p2 except Exception as ex: print(f'Unexpected error, {type(ex).__name__}: {ex}') raise lines_intersect = True t2 = ((p3[0] - p1[0]) * dy12 + (p1[1] - p3[1]) * dx12) / -denominator # Find the point of intersection. intersection = (p1[0] + dx12 * t1, p1[1] + dy12 * t1) # The segments intersect if t1 and t2 are between 0 and 1. segments_intersect = ((t1 >= 0) and (t1 <= 1) and (t2 >= 0) and (t2 <= 1)) # Find the closest points on the segments. if t1 < 0: t1 = 0 elif t1 > 1: t1 = 1 if t2 < 0: t2 = 0 elif t2 > 1: t2 = 1 close_p1 = (p1[0] + dx12 * t1, p1[1] + dy12 * t1) close_p2 = (p3[0] + dx34 * t2, p3[1] + dy34 * t2) return lines_intersect, segments_intersect, intersection, \ close_p1, close_p2

This method takes as parameters the points that define the segments.

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 result causes a ZeroDivisionError, then the denominator is 0 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 (but not necessarily closest to the other line). Finally the code uses the adjusted values of t1 and t2 to find those closest points.

To use the example, click and drag to define the first segment. Then click and drag again to define the second segment. When you release the mouse, the program 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.)

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