python - Finding the intersection point between line and piecewise linear curves

Question

I have two curves, one is a line, for example y = x/4 and another one is the set of points which I connect with line segments (for example : x = [1, 2.5, 3.4, 5.8, 6], y = [2, 4, 5.8, 4.3, 4] which forms 5 points in 2D plane that forms a piecewise linear curve), and I should find the intersecting point between this two curves. I should first form this piecewise linear curve and then find the intersection point. Fortunately, I found that I could use numpy.polyfit to find the polynomial coefficients of every line segment as below:

import numpy as np
import matplotlib.pyplot as plt
x = [0, 1, 2, 4, 6]  # in my primary problem i dont have just 5 points and i have approximately 200 points !
y = [0, 0, 3, -1, 2]
x = np.array(x)
y = np.array(y)
a = [np.polyfit(x[i:(i+2)], y[i:(i+2)], 1) for i in range(len(x)-1)]
plt.plot(x, y, 'o')
plt.show()

But now I am really confused about how to use these coefficients to find the intersecting point between the two graphs!? (in my primary problem i don't have just 5 points and i have approximately 200 points !) One idea to solve this problem is to use ((solve)) command to check the intersection of the line and line segments but this is very time consuming and this command doesn't work with line ((segment)).

Answer 1

There is no reason that there should be exactly one intersection point. For your example, if you had taken $y = 1$, you would have three intersections, if you had taken $y = -2$, you would have none, and if had taken $y = 0$, you would have infinitely many.

To find them all, one way to proceed would be to consider each of the line segments connecting elements from x and y, and for which you have already found the slopes and intersects, and extend the line segment to be defined on the real line. Now, using for instance one of the procedures in this question find the intersections between your given line and the extended one. If there are 0 intersections, then the original unextended line segment also has 0 intersections, if there is 1 intersection, the unextended one will have 1 intersection if the x-value lies within the range of x-values defining the line segment (and 0 otherwise), and if there are infinitely many intersections, then every point on the line segment will lie in the intersection. Repeat the process for each of your line segments.

def get_intersection(line1, line2):
    """Returns the intersection, if any, between two lines, None if the lines are equal, and
    the empty array if the lines are parallel.

    Args:
        line1 (numpy.array): [slope, intercept] of the first line.
        line2 (numpy.array): [slope, intercept] of the second line.

    Taken from https://stackoverflow.com/a/42727584/5085211.
    """
    if (np.array_equal(line1, line2)):
        return None
    if line1[0] == line2[0]:
        return np.empty(0)
    l1 = np.insert(line1, 1, -1)
    l2 = np.insert(line2, 1, -1)
    x, y, z = np.cross(l1, l2)
    return np.hstack([x, y]) / z

line_of_interest = [0.25, 0]  # y = x/4

for i in range(len(x)-1):
    p = get_intersection(a[i], line_of_interest)
    if np.array_equal(p, []):
        continue
    elif np.array_equal(p, None):
        print('Entire line segment between {0} and {1}'.format(x[i], x[i+1]))
    elif x[i] <= p[0] and p[0] < x[i+1]:
        print(p)

# Prints:
# [ 0.  0.]
# [ 1.09090909  0.27272727]
# [ 3.11111111  0.77777778]
# [ 5.6  1.4]