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

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为零，则表示没有交点（两条直线平行）。您可以决定更改函数，例如 return 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)

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

How to find the intersection of two lines given a point on each line and a parallel vector

python

algorithm

math

graphics

intersection