如何找到两条线的交点，每条线上有一个点和一个平行向量 [英] How to find the intersection of two lines given a point on each line and a parallel vector

问题描述

我需要一种算法，可以找到两条2D线的交点。每条线将以线上的点和平行向量的dx / dy 的形式出现。我尝试过参数化每一行并求解方程组来解决参数化变量问题，我可以将其重新插入行的参数方程并获得我的x / y，但是我的尝试失败了。有任何想法吗？我使用Python进行编程，但语言并不重要。

解决方案

您基本上必须解决以下等式： / p>

x = x _0，a + dx _a × t

y = y < sub> 0，a + dy × t >>
x = x _0，b + dx × u

y = y _0，b + dy × u

或：

<0> 0，a + dx _a × t = x _0，b + dx _b × u

x _0，a + dx _a × t = x < sub> 0，b + dx _b × u

现在，如果您进行一些代数操作，您会发现：

t = dy b×（x 0，b←-x 0，a （y _0，b -y _0，a ）/ d

u = DY <子>一&倍;（X <子> 0，b -x <子> 0，一个） - DX <子>一&倍;（Y <子> 0，b -y <子> 0，一个）/ 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）的矢量;你得到的结果并不是很令人惊讶：

pre $ $ $
Python 3.5.2（默认，2016年11月17日， 17:05:23）
[GCC 5.4.0 20160609] on linux
输入help，copyright，credits或license以获取更多信息。
>>> （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）
...
>>>相交（1,0,0,1,0,2,1,1）
（1.0，3.0）

I need an algorithm that can find the intersection of two 2D lines. Each line will come in the form of a point on the line and the dx/dy of a parallel vector. I've tried parameterizing each line and solving the system of equations to solve for the parameterized variable which I could plug back into the parametric equation of the lines and get my x/y, but my attempt failed. Any ideas? I'm programming in Python but the language doesn't much matter.

解决方案

You basically have to solve the following equation:

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

Or:

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

Now if you do some algebraic manipulation, you will find that:

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; where
d=dx_a×dy_b-dx_b×dy_a

Now it is thus only a matter to determine either t or u (you do not have to calculate both), and plug then into the formula above. So

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)

If the d in the equation (the denominator) is equal to zero, this means there is no intersection (the two lines are parallel). You can decide to alter the function and for instance return None or raise an exception in such case.

If you test it, for instance with a vector (1,0) offset and direction (0,1); and a vector with offset (0,2) and direction (1,1); you get the not very surprising result of:

$ 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)

这篇关于如何找到两条线的交点，每条线上有一个点和一个平行向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！