Python - 查找由多个点跨越的线之间的交点

Question

我有一个我认为是相当基本的问题，我无法找到一个优雅的解决方案。想象一下，我在二维空间中有两条相当复杂的线(例如 B 样条曲线)，由两个维度 (n,2) 的矩阵跨越，其中 n(行)是沿线的点数，两列分别对应x和y坐标。更多信息:

• 两个连续点之间的距离相似，但不是恒定的。
• 交点不一定是跨越直线的点。
• 可能(理论上)有任意数量的交叉路口

我想找到这些线相交的点。出于我的目的，将每两个连续点之间的线视为线性就足够了。

不幸的是，到目前为止，我能想到的每一个解决方案都非常低效(例如，使用两个嵌套的 for 循环并检查一条线上两点的每个线段与另一条线上的每个线段)。必须有一种更优雅的方式来做到这一点。

是否有任何类型的函数可以简化此类例程的实现？

P.S.:您可以在下面找到我上面描述的系统的图示。

Answer 1

感谢大家的回复，尤其是Dschoni相关出版物引用，以及Piinthesky对于给我解决方案想法的评论:

我们将两条直线点的 X 坐标连接到一个公共(public)向量中，然后为两条直线中的每一条插入 Y 坐标。因为我们现在在相同的 X 位置有点，所以我们可以从彼此中减去 Y 值。在差值符号移动的点之间，线相交。感谢大家的帮助!

这是我的解决方案代码:

import pickle
import numpy as np
from scipy.interpolate import interp1d
import matplotlib.pyplot as plt

# Load data series
X1 = pickle.load(open("X1.p","rb"))
Y1 = pickle.load(open("Y1.p","rb"))
X2 = pickle.load(open("X2.p","rb"))
Y2 = pickle.load(open("Y2.p","rb"))

# Convert X vectors to lists, and merge them
X1_list = list(X1)
X2_list = list(X2)
in_first = set(X1_list)
in_second = set(X2_list)
in_second_but_not_in_first = in_second - in_first
result = X1_list + list(in_second_but_not_in_first)
X_joint = np.asarray(result) # Revert to array

# Create interpolated functions
line_1 = interp1d(X1, Y1, kind='linear', fill_value='extrapolate')
line_2 = interp1d(X2, Y2, kind='linear', fill_value='extrapolate')

# Create joint Ys
Y1_joint = line_1(X_joint)
Y2_joint = line_2(X_joint)

# Calculate difference in Y
difference = Y1_joint-Y2_joint

# Plot the original data series
f, axarr = plt.subplots(2)
axarr[0].plot(X1, Y1,'b')
axarr[0].plot(X2, Y2,'r')

# Plot the difference values
axarr[1].plot(X_joint,difference)
axarr[1].plot([min(X_joint),max(X_joint)],[0,0],'k')

# The intersections are where the difference graph dips below or rises above zero