1

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)).

fuglede
  • 17,388
  • 2
  • 54
  • 99
Nima Geran
  • 115
  • 1
  • 3
  • 10

1 Answers1

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]
fuglede
  • 17,388
  • 2
  • 54
  • 99
  • thank you . in my problem of course i had not such lines (y = 0 or y = (a number)) . really i have a line which have the same slope as the initial line segments ! infact i should find the yield offset stress from a strain - stress curve which is define such that the line should sketch parallel to the strain - stress curve but have an offset of 0.002 . . . (you could see this definition with a really simple search in google ! for example [click here!](https://en.wikipedia.org/wiki/Yield_(engineering)) ) . . . i want that yield offset stress and all i have done is to find that . – Nima Geran Mar 25 '17 at 15:54
  • So what you seem to be saying is that your piecewise linear function is monotonically increasing with slope less than or equal to the slope of the given line at all points where it is defined; that makes the problem numerically much easier to solve than the general one in OP, but if you just want to do it for a collection of 200 line segments, the method above will work just fine. – fuglede Mar 25 '17 at 16:02
  • i couuld not say that all the line segments exactly have a monotonically increasing slopes ! for example [click here](http://engineering.stackexchange.com/questions/13583/why-does-the-stress-strain-curve-decrease/13595) to see this typical stress-strain curve which have almost 6 regions with different trends of slopes !(my stress-strain curve also is simmilar to this one ! and i also have this variations in slopes !) i just have two more question: because i'm fairly new to programming , could you please say that how your code works and is this working properly for my stress-strain curve ?Thanx – Nima Geran Mar 25 '17 at 16:21
  • The solution in the answer assumes nothing on monotonicity. – fuglede Mar 25 '17 at 16:28
  • thank you so much , i really will use this code , but now i have an idea , could you please compare this one with the code above ? if i consider each line segments as a line and then i write a loop to check the intersection between the y = x/4 and every line segments and then when the x coordinates of intersection of first line segment and the y = x/4 inside the x projection of a line segment , i could conclude that this intersection point is my stress ?(in my idea i just has to find the intersection between two lines but not line segments and a line ! ) – Nima Geran Mar 25 '17 at 21:42
  • Compare it with which code exactly? And yes, if you know from the beginning that you will intersect at most one of the line segments, then you can stop as soon as you have found that one. – fuglede Mar 25 '17 at 22:12