Python

Question

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

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

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

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

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

P.S.: 下面你可以找到我上面描述的系统的插图。

Answer 1

在两个给定数据点之间对每个函数 f1、f2 进行线性插值。使用不需要导数但保持函数评估较低的方法最小化函数 f = abs(f1 - f2)，例如 Brent's method. The location of that minimum is your approximate intersection point. If you don't want to implement the algorithm yourself, use scipy.optimize.minimize_scalar (docs).

Answer 2

感谢大家的回复，尤其是 Dschoni for relevant publication references, and Piinthesky 给了我解决方案想法的评论：

我们将两条直线点的 X 坐标连接到一个公共向量中，然后为两条直线中的每一条插入 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

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

Python - Find intersection between lines spanned by several points

linear-algebra

intersection