直線と区分線形曲線の交点を見つける

Question

私は2つの曲線、1つはy = x/4の線、もう1つは線分で結ぶ点の集合です（例：x = [1, 2.5, 3.4, 5.8, 6]、 y = [2, 4, 5.8, 4.3, 4]）は、2つの曲線の間に交差点を見つけるはずです。私はこの区分線形曲線を最初に形成し、交点を見つけなければならない。

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

しかし、今、私は二つのグラフとの交点を見つけるために、これらの係数を使用する方法については本当に混乱しています：幸いなことに、私は以下のように、すべての線分の多項式係数を見つけるためにnumpy.polyfitを使用することができることを発見しました！ ？ （私の主な問題では、私はちょうど5ポイントがなく、私は約200ポイントを持っています！）この問題を解決する一つのアイデアは、（を解決する（）コマンドを使用してラインとラインセグメントこれは非常に時間がかかり、このコマンドは回線（（セグメント）で動作しません）。

Answer 1

正確に1つの交差点が存在する必要はありません。あなたの例では、$ y = 1 $を取っていたら、3つの交差点があります。もし$ y = -2 $を取っていれば、何も持たず、$ y = 0 $を取っていれば無限になりますたくさんの。

これらのすべてを見つけるには、要素を接続する線分をそれぞれxとyから考えて、既に斜面と交差を見つけて、定義する線分を延長します実線。例えば、the procedures in this questionのうちの1つを使用すると、指定された行と拡張された行との間の交差点が見つかります。 0の交差点がある場合、元の未拡張線分も0の交差点を持ち、1つの交差点があれば、未拡張のものは1つの交差点を持ち、x値が線分を定義するx値の範囲内にある場合（0無限大の交差点がある場合、線分上の各点は交差点に位置します。それぞれの線分に対してこのプロセスを繰り返します。

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]