python - 给定每条线上的一个点和一个平行向量，如何找到两条线的交点

Question

我需要一个可以找到两条二维线交点的算法。每条线的形式都是线上的一个点和平行矢量的 dx/dy。我已经尝试对每条线进行参数化并求解方程组以求解参数化变量，我可以将其重新插入线的参数化方程并得到我的 x/y，但我的尝试失败了。有任何想法吗？我正在使用 Python 编程，但语言并不重要。

Answer 1

您基本上必须求解以下等式:

x = x_0,a+dx_a×t
y = y_0,a+dy_a×t
x = x_0,b+dx_b×u
y = y_0,b+dy_b×u

或者:

x_0,a+dx_a×t = x_0,b+dx_b×u
x_0,a+dx_a×t = x_0,b+dx_b×u

现在如果你做一些代数运算，你会发现:

t=dy_b×(x_0,b-x_0,a)-dx_b ×(y_0,b-y_0,a)/d
u=dy_a×(x_0,b-x_0,a)-dx_a×(y _0,b-y_0,a)/d;在哪里
d=dx_a×dy_b-dx_b×dy_a

现在只需确定 t 或 u(您不必计算两者)，然后代入上面的公式。所以

def intersect(x0a,y0a,dxa,dya,x0b,y0b,dxb,dyb):
    t = (dyb*(x0b-x0a)-dxb*(y0b-y0a))/(dxa*dyb-dxb*dya)
    return (x0a+dxa*t,y0a+dya*t)

如果等式(分母)中的d 为零，则表示没有交点(两条线平行)。您可以决定更改函数，例如返回 None 或在这种情况下引发异常。

如果您对其进行测试，例如使用向量 (1,0) 偏移量和方向 (0,1)；和一个具有偏移量(0,2)和方向(1,1)的向量；你得到的不是很令人惊讶的结果:

$ python3
Python 3.5.2 (default, Nov 17 2016, 17:05:23) 
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def intersect(x0a,y0a,dxa,dya,x0b,y0b,dxb,dyb):
...     t = (dyb*(x0b-x0a)-dxb*(y0b-y0a))/(dxa*dyb-dxb*dya)
...     return (x0a+dxa*t,y0a+dya*t)
... 
>>> intersect(1,0,0,1,0,2,1,1)
(1.0, 3.0)