如何找到一条直线和一组类似曲线的二维点的交点？

Question

假设我们有：

由近似描述高阶多项式曲线的二维数据集描述的曲线。
由两点定义的线。

这是示例图片：

假设直线和曲线相交，如何找到直线和数据集的交点？

Answer 1

由于曲线数据看起来密集而不分散（例如数值求解微分方程的结果），因此对整个曲线数据集进行插值或近似是多余的。在下文中，我假设数据集的点沿曲线排序（就好像它们是对参数曲线进行采样的结果）。

首先，进行坐标变换 A(x,y) 平移和旋转，使红线与 x 轴匹配。
将变换后的曲线与x轴相交，即从曲线数据集中取出y坐标绝对值较小的所有点（并记住它们在数据集中的索引） .为描绘的曲线尝试y < 0.05。
使用2中选择的点的索引来检测相邻曲线点的范围，每个范围类似于曲线的一小部分。

马虎版

对于每个范围，取 x 坐标的平均值 x_mean。逆坐标变换 A_inv(x_mean, 0) 将为您提供该范围交点的近似值。根据您的用例和潜在曲线的复杂性，近似值可能已经足够好了。

精进版

用直线或低阶多项式曲线逼近每个范围<= 4。
- 将范围的索引映射到单位区间，例如[103, 104, 105, 106, 107] 变为 [0.0, 0.25, 0.5, 0.75, 1.0]
- 将范围数据拆分为 x 和 y 坐标范围。
- 将x和y数据分别逼近为一维函数，将曲线数据表示为参数函数(x(t), y(t))，t来自[0, 1] （使用上面的映射索引作为插值结）。
- 使用多项式求解器求解y(t) == 0。
- 对于 [0, 1] 内的每个零 t_zero，计算 t_zero 处的逼近函数 x(t)。逆坐标变换 A_inv(x(t_zero), 0) 为您提供原始坐标中 t_zero 交点的近似值。

如果您可以确认此解决方案可能适合您的问题，我可能会提供一个相应的 numpy 示例。

Answer 2

根据我上面的评论

import numpy as np

A = np.random.random((20, 2))
A[:,0] = np.arange(20)
A[:,1] = A[:,1] * (7.5 + A[:,0]) # some kind of wiggly line
p0 = [-1.0,-6.5] # point 0
p1 = [22.0, 20.0] # point 1

b = (p1[1] - p0[1]) / (p1[0] - p0[0]) # gradient
a = p0[1] - b * p0[0] # intercept
B = (a + A[:,0] * b) - A[:,1] # distance of y value from line
ix = np.where(B[1:] * B[:-1] < 0)[0] # index of points where the next point is on the other side of the line
d_ratio = B[ix] / (B[ix] - B[ix + 1]) # similar triangles work out crossing points
cross_points = np.zeros((len(ix), 2)) # empty array for crossing points
cross_points[:,0] = A[ix,0] + d_ratio * (A[ix+1,0] - A[ix,0]) # x crossings
cross_points[:,1] = A[ix,1] + d_ratio * (A[ix+1,1] - A[ix,1]) # y crossings

print(ix, B, A, cross_points)

如何找到一条直线和一组类似曲线的二维点的交点？

How to find the intersection points of a straight line and a curve-like set of two dimensional points?

python

numpy

set-intersection