查找直线和分段线性曲线之间的交点 [英] Finding the intersection point between line and piecewise linear curves
问题描述
我有两条曲线，一条是一条线，例如y = x / 4，另一条是我与线段连接的一组点（例如： x = [1，2.5 ，3.4，5.8，6] ， y = [2，4，5.8，4.3，4] 在2D平面中形成5个点分段线性曲线），我应该找到这两条曲线之间的相交点。我应该首先形成此分段线性曲线，然后找到相交点。幸运的是，我发现可以使用 numpy.polyfit 来找到每个线段的多项式系数，如下所示：
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()
但是现在我真的很困惑如何使用这些系数可以找到两个图之间的交点！ （在我的主要问题中，我只有5分，而我大约有200分！）解决此问题的一种方法是使用（（ solve ））命令检查线段与线段的交点，但这非常耗时，此命令不适用于线段（（ segment ））。
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)).
推荐答案
没有理由应该恰好有一个交点。以您的示例为例，如果您采用了$ y = 1 $，则将有三个交集；如果您采用了$ y = -2 $，则将不会有交集；如果您采用了$ y = 0 $，则将无穷大。许多。
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.
要找到全部，一种方法是考虑连接 x 和 y ，并且已经找到了它们的斜率和相交点，并扩展了要在实线上定义的线段。现在，使用此问题中的过程之一，查找给定线与扩展的。如果有0个交集，则原始未扩展线段也有0个交集；如果有1个交集，则如果x值位于定义该线段的x值范围内，则未扩展的那个线段将具有1个交集。否则），并且如果有无限多个相交，则线段上的每个点都将位于相交处。对每个线段重复该过程。
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]
这篇关于查找直线和分段线性曲线之间的交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
